Máquinas de Turing
1
A Hierarquia de Linguagens
n n n ?
a b c
ww ?
Linguagens Livres de Contexto
n n
R
a b
ww
Linguagens Regulares
a*
a *b *
2
Linguagens aceitas por
Máquinas de Turing
ww
n n n
a b c
Linguagens Livres de Contexto
n n
R
a b
ww
Linguagens Regulares
a*
a *b *
3
Fita
......
Máquina de Turing
......
Cabeça de leitura-escrita
Unidade de Controle
4
A Fita
Sem limites – comprimento infinito
......
......
cabeça de leitura-escrita
A cabeça move para a esquerda ou direita
5
......
......
cabeça de leitura-escrita
Em cada transição (passo de execução) :
1. Lê um símbolo
2. Escreve um símbolo
3. Move para a esquerda ou direita
6
Exemplo:
Instante 0
......
a b a c
Instante 1
......
1. Lê
a b k c
......
......
a
2. Escreve
k
3. Move para a esquerda
7
Instante 1
......
a b k c
Instante 2
......
1. Lê
a f
k c
......
......
b
2. Escreve
f
3. Move para a direita
8
O String de Entrada
string de entrada
......
  a b a c
símbolo branco
  
......
cabeça
A cabeça inicia na posição mais à esquerda
do setring de entrada
9
Estados & Transições
Escreve
Lê
q1
a  b, L
Move p/ Esq.
q2
Move p/ Dir.
q1
a  b, R
q2
10
Exemplo:
Instante 1
......
  a b a c
  
......
q1
estado corrente
q1
a  b, R
q2
11
......
Instante 1
  a b a c
  
......
q1
......
Instante 2
  a b b c
  
......
q2
q1
a  b, R
q2
12
Exemplo:
......
Instante 1
  a b a c
  
......
q1
......
Instante 2
  a b b c
  
......
q2
q1
a  b, L
q2
13
Exemplo:
......
Instante 1
  a b a c
  
......
q1
......
Instante 2
  a b b c
g  
......
q2
q1
  g, R
q2
14
Determinismo
Máquinas de Turing são deterministas
Não permitido
Permitido
a  b, R
q2
a  b, R
q2
a  d, L
q3
q1
q1
b  d, L
q3
Transições lambda não são permitidas
15
Função de Transição Parcial
Exemplo:
......
  a b a c
  
......
q1
a  b, R
q2
q1
b  d, L
q3
Permitido:
Nenhuma transição
para o símbolo c
16
Parada
A máquina pára em um estado se
não existe transição a seguir.
17
Parada - Exemplo 1:
......
  a b a c
  
......
q1
q1
Nenhuma transição de q1
PÁRA!!!
18
Parada - Exemplo 2:
......
  a b a c
  
......
q1
a  b, R
q2
b  d, L
q3
q1
Nenhuma transição
de q1 com símbolo c
PÁRA!!!
19
Estados de Aceitação
q1
q2
Permitido
q1
q2
Não permitido
•Não há transição saindo de estado de aceitação
•A máquina pára e aceita
20
Aceitação
Aceita string
de entrada
Não aceita string
de entrada
Se a máquina pára
em estado de aceitação
Se a máquina pára
em estado que não é
de aceitação
ou
Se a máquina entra
em loop infinito
21
Observação:
Para aceitar um string de entrada,
não é necessário ler todos os
símbolos do string
22
Máquina de Turing - Exemplo
Alfabeto de entrada
  {a , b }
Aceita a linguagem:
a*
a  a, R
q0
  , L
q1
23
Instante 0
  a a a  
q0
a  a, R
q0
  , L
q1
24
Instante 1
  a a a  
q0
a  a, R
q0
  , L
q1
25
Instante 2
  a a a  
q0
a  a, R
q0
  , L
q1
26
Instante 3
  a a a  
q0
a  a, R
q0
  , L
q1
27
Instante 4
  a a a  
q1
a  a, R
q0
Pára & Aceita
  , L
q1
28
Exemplo de Rejeição
Instante 0
  a b a  
q0
a  a, R
q0
  , L
q1
29
Instante 1
  a b a  
q0
Nenhuma transição possível
a  a, R
q0
Pára & Rejeita
  , L
q1
30
Máquina mais simples para a mesma linguagem
mas para alfabeto de entrada
Aceita a linguagem:
  {a }
a*
q0
31
Instante 0
  a a a  
q0
Pára & Aceita
q0
Não é necessário ler a entrada
32
Exemplo de Loop Infinito
Uma máquina deTuring
para a linguagem a * b(a  b) *
b  b, L
a  a, R
q0
  , L
q1
33
Instante 0
  a b a  
q0
b  b, L
a  a, R
q0
  , L
q1
34
Instante 1
  a b a  
q0
b  b, L
a  a, R
q0
  , L
q1
35
Instante 2
  a b a  
q0
b  b, L
a  a, R
q0
  , L
q1
36
Instante 2
  a b a  
q0
  a b a  
q0
Instante 4
  a b a  
q0
Instante 5
  a b a  
q0
loop infinito
Instante 3
37
Como a máquina entra em loop infinito:
• O estado de aceitação não será atingido
•A máquina nunca pára
•O string de entrada não é aceito
38
Outro Exemplo de Máquina de Turing
n n
Máquina deTuring para a linguagem {a b
n 1
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
a  a, R
a  x, R
q1
}
y  y, L
a  a, L
b  y, L
q2
x  x, R
39
Idéia básica:
Casar a’s com b’s:
Repita:
substitua o a mais à esquerda por x
encontre o b mais à esq. e substitua por y
Até que não existam mais a’s ou b’s
Se existir algum a ou b restante, rejeite
40
 a a b b  
Instante 0
q0
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
a  a, R
a  x, R
q1
y  y, L
a  a, L
b  y, L
q2
x  x, R
41
 x a b b  
Instante 1
q1
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
a  a, R
a  x, R
q1
y  y, L
a  a, L
b  y, L
q2
x  x, R
42
 x a b b  
Instante 2
q1
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
a  a, R
a  x, R
q1
y  y, L
a  a, L
b  y, L
q2
x  x, R
43
 x a y b  
Instante 3
q2
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
a  a, R
a  x, R
q1
y  y, L
a  a, L
b  y, L
q2
x  x, R
44
 x a y b  
Instante 4
q2
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
a  a, R
a  x, R
q1
y  y, L
a  a, L
b  y, L
q2
x  x, R
45
 x a y b  
Instante 5
q0
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
a  a, R
a  x, R
q1
y  y, L
a  a, L
b  y, L
q2
x  x, R
46
 x x y b  
Instante 6
q1
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
a  a, R
a  x, R
q1
y  y, L
a  a, L
b  y, L
q2
x  x, R
47
 x x y b  
Instante 7
q1
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
a  a, R
a  x, R
q1
y  y, L
a  a, L
b  y, L
q2
x  x, R
48
 x x y y  
Instante 8
q2
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
a  a, R
a  x, R
q1
y  y, L
a  a, L
b  y, L
q2
x  x, R
49
 x x y y  
Instante 9
q2
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
a  a, R
a  x, R
q1
y  y, L
a  a, L
b  y, L
q2
x  x, R
50
 x x y y  
Instante 10
q0
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
a  a, R
a  x, R
q1
y  y, L
a  a, L
b  y, L
q2
x  x, R
51
 x x y y  
Instante 11
q3
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
a  a, R
a  x, R
q1
y  y, L
a  a, L
b  y, L
q2
x  x, R
52
 x x y y  
Instante 12
q3
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
a  a, R
a  x, R
q1
y  y, L
a  a, L
b  y, L
q2
x  x, R
53
 x x y y  
Instante 13
q4
Pára & Aceita
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
a  a, R
a  x, R
q1
y  y, L
a  a, L
b  y, L
q2
x  x, R
54
Observação:
Se modificarmos a
máquina para a linguagem
n n
{a b }
podemos facilmente construir
n n n
uma máquina para a linguagem {a b c }
55
Definições Formais para
Máquinas de Turing
56
Função de Transição
q1
a  b, R
q2
 (q1, a)  (q2 , b, R)
57
Função de Transição
q1
c  d, L
q2
 (q1, c)  (q2 , d , L)
58
Máquina de Turing:
Estados
Alfabeto
de entrada
Alfabeto
da fita
M  (Q, , ,  , q0 , , F )
Função de
transição
Estado
inicial
Estados de
aceitação
branco
59
Configuração
  c a b a  
q1
Descrição instantânea:
ca q1 ba
60
Instante 4
 x a y b  
q2
Movimento:
Instante 5
 x a y b  
q0
q2 xayb  x q0 ayb
(resulta em um passo)
61
Instante 4
 x a y b  
Instante 5
 x a y b  
q2
q0
Instante 6
 x x y b  
Instante 7
 x x y b  
q1
q1
uma computação
q2 xayb  x q0 ayb  xx q1 yb  xxy q1 b
62
q2 xayb  x q0 ayb  xx q1 yb  xxy q1 b

Noatação equivalente:
q2 xayb  xxy q1 b
63
Configuração inicial:
q0 w
string de entrada
w
 a a b b  
q0
64
A Linguagem Aceita
Para qualquer Máquina de Turing M
L( M )  {w :

q0 w  x1 q f x2 }
Estado inicial
Estado de aceitação
65
Se uma linguagem L é aceita
por uma máquina de Turing M
dizemos que L é:
•Turing Reconhecível
Outros nomes usados:
•Turing Aceitável
•Recursivamente Enumerável
66