Máquinas de Turing
Teoria da Computação
0
0
0
2
1
4
q
0
2
B
B
B
B
0
0
0
2
1
4
q
0
2
B
B
B
B
Definição
M = (Q, Σ, Γ, δ, q0, qa, qr)
ESTADOS
SIMBOLOS
DE INPUT
TRANSIÇÃO ESTADO
DE ESTADOS INICIAL
SIMBOLOS
DA FITA - inclui o simbolo B (branco)
BΣ
Estado de
Aceitação
Estado de
Rejeição
Configuração
0
0
0
2
1
q
q0 0 0 0 2 1 0 2
0
2
B
B
B
0002q102
Configuração Inicial
0 0 0 2 qa 1 0 2
Configuração de Aceitação
0 0 0 2 qr 1 0 2
Configuração de Rejeição
B
Um passo de cálculo
Configuração 1  Configuração 2
0
0
0
2
1
4
0
2
B
B
q
0002q102
000q2402
B
B
Um passo de cálculo
Configuração 1  Configuração 2
0
0
0
2
1
4
0
2
B
q
0002q102
0 0 0 2 4 q0 2
B
B
B
Linguagem Aceita
• M = Máquina de Turing
• w = 010001 string sobre alfabeto de M
• w é aceito por M se existe uma sequência
finita de passos de cálculo
qo 010001  C1  ….  Ca
Configuração
inicial
Configuração de Aceitação
Linguagem Aceita
• M = Máquina de Turing
• L(M) = conjunto dos strings construidos
sobre o alfabeto de input e que são
aceitos por M
Exemplo : M1
•
•
•
•
•
•
δ(q0,0) = (q0,0,R)
δ(q0,B) = (qa,B,R)
δ(q0,1) = (q2,1,R)
δ(q2,1) = (q2,1,R)
δ(q2,0) = (qr,0,R)
δ(q2,B) = (qa,B,R)
• L(M) = {0n 1m | n≥0, m≥0}
• Pergunta:
Dado w ϵ {0,1}* quais as possibilidades para M1(w) ?
Exemplo: M2
•
•
•
•
•
•
δ(q0,0) = (q0,0,R)
δ(q0,B) = (qa,B,R)
δ(q0,1) = (q2,1,R)
δ(q2,1) = (q2,1,R)
δ(q2,0) = (qr,0,R)
δ(q2,B) = (q2,B,R)
• L(M) = {0n | n≥0}
Pergunta:
Dado w ϵ {0,1}* quais as possibilidades para M2(w) ?
Exemplo: M3
•
•
•
•
•
•
•
•
•
δ(q0,0) = (q0,0,R)
δ(q0,B) = (qa,B,R)
δ(q0,1) = (q2,1,R)
δ(q2,1) = (q2,1,R)
δ(q2,0) = (q3,0,R)
δ(q2,B) = (qa,B,R)
δ(q3,B) = (q3,B,R)
δ(q3,0) = (q3,0,R)
δ(q3,1) = (q3,1,R)
• L(M) = {0n 1m | n≥0, m≥0}
Pergunta:
Dado w ϵ {0,1}* quais as possibilidades para M3(w) ?
Linguagem Turing Decidível
• Linguagem aceita por alguma Máquina de Turing
que sempre pára (para qualquer input)
Exemplo: L = {0n 1m | n≥0, m≥0}
L = L(M1)
Repare que L = L(M3), mas M3 nem sempre
pára.
Linguagens Turing Decidíveis
• Uma linguagem pode ser aceita por uma
máquina que nem sempre pára e mesmo
assim ser Turing decidível.
• Pois pode ser aceita por uma outra
máquina que pára sempre.
Linguagem Turing Reconhecível
• Linguagem L aceita por uma máquina que
nem sempre pára.
• A Máquina pára em qa somente para os
strings da linguagem L.
• Quando acionada para os strings fora de
L, a máquina pára em qr ou simplesmente
não pára.
qa
w
M
L é aceita por M
M sempre pára
M decide L
L é Turing Decidível
qr
Se w pertence a L
Se w não pertence a L
qa
w
M
Se w pertence a L
qr
Se w não pertence a L
L é aceita por M
M nem sempre pára
Loop
M não decide L
L é Turing Reconhecivel
Isto não implica que L não é Turing Decidivel
Resumo
• Linguagem Turing Decidível : Aceita por
uma MT que sempre pára
• Linguagem Turing Reconhecível : Aceita
por uma máquina de Turing (pode ser que
não páre sempre)
• Linguagem Não-Turing Reconhecível : não
é aceita por nenhuma máquina de Turing
Propriedade: Se L é Turing decídivel então L é Turing Decídivel
qa
w
M
Se w pertence a L
qr
Se w não pertence a L
Se w pertence a L
w
M’
Se w não pertence a L
M’ decide L
Propriedades
• Turing decidível  Turing Reconhecível
• Turing Reconhecível  Turing Decidível
• Se L é Turing Reconhecível e L é Turing
Reconhecível  L é Turing Decidível
qa
w
M1
Se w pertence a L
qr
Se w não pertence a L
Loop
qa
w
M2
Se w não pertence a L
qr
Se w pertence a L
Loop
qa
qa
M1
w
w pertence a L
OU
qa
M2
qr
w não pertence a L
M”