Máquinas de Turing Não
Deterministas
Teoria da Computação
Exemplo
δ(q0,0) = {(q0,0,R),(q1,1,R)}
δ(q0,1) = {(q0,1,R)}
δ(q0,B) = {(qa,B,R), (q1,B,R)}
0
0
1
1
B
δ(q1,0) = {(q1,0,R)}
δ(q1,1) = {(q1,1,R)
δ(q1,B) = {(qr,B,R), (q1,B,R)}
B
0
q0
q0 q0 q0 q0
q0 qa
0
1 q0
B
qa
B
qr
0
q1
0
0
q1
q1
1
q1
q0
1
q0
q0
q1
B
q1
B
q1
B
qr
1
Exemplo
δ(q0,0) = {(q0,0,R),(q1,1,R)}
δ(q0,1) = {(q0,1,R)}
δ(q0,B) = {(qa,B,R), (q1,B,R)}
0
0
1
1
B
δ(q1,0) = {(q1,0,R)}
δ(q1,1) = {(q1,1,R)
δ(q1,B) = {(qr,B,R), (q1,B,R)}
B
0
q0
q0 q0 q0 q0
q0 q1
qr
0
1 q0
B
qa
B
qr
0
q1
0
0
q1
q1
1
q1
q0
1
q0
q0
q1
B
q1
B
q1
B
qr
1
Exemplo
δ(q0,0) = {(q0,0,R),(q1,1,R)}
δ(q0,1) = {(q0,1,R)}
δ(q0,B) = {(qa,B,R), (q1,B,R)}
0
0
1
1
q0 q0 q0 q0
B
δ(q1,0) = {(q1,0,R)}
δ(q1,1) = {(q1,1,R)
δ(q1,B) = {(qr,B,R), (q1,B,R)}
B
0
q0
q0 q1
q1
0
1 q0
B
qa
B
qr
0
q1
0
0
q1
q1
1
q1
q0
1
q0
q0
q1
B
q1
B
q1
B
qr
looping
1
Arvore de execução
• A cada string w está associada uma árvore
de execução Aw da máquina M.
• Possibilidades:
– Existe um ramo que termina em qa
– Nao existem ramos que terminam em qa
• Todos os ramos terminam em qr
• Existem ramos infinitos
qa
qr
qr
looping
M aceita w, w pertence a L(M)
M não aceita w
qr
qr
looping
M não aceita w
qr
qr
Se para qualquer string w, sua árvore de execução é
finita, então M decide L(M)
Se existe string w tal que a árvore de execução de M é
infinita, então M não decide L(M)
L(M) é a linguagem aceita por M mas M não decide L(M).
Equivalencia: Maquinas
deterministas e nao-deterministas
• Seja M’ uma máquina de Turing
não-determinista.
Então, existe uma máquina de Turing M
DETERMINISTA tal que
L(M) = L(M’)
Isto é, os strings aceitos por M são
exatamente aqueles aceitos por M’.
Prova
• Seja M’ uma maquina nao-derminista
• Seja N = numero maximo de escolhas
possiveis para os comandos de M’
• Exemplo :
δ(q0,0) = {(q0,0,R),(q1,1,R)}
δ(q0,1) = {(q0,1,R)}
δ(q0,B) = {(qa,B,R), (q1,1,R)}
δ(q1,0) = {(q1,0,R)}
δ(q1,1) = {(q1,1,R)
δ(q1,B) = {(qr,B,R), (q1,B,R)}
N =2
Vamos construir uma maquina determinista
M de 3 fitas equivalente a M’
FITA DE INPUT
0
0
1
1
FITA DE CALCULO
FITA DAS POSSIBILIDADES
1
1
2
Serao executados 3 passos de M’
Passo 1 : opcao 1
Passo 2 : opcao 1
Passo 3 : opcao 2
• Ordena-se todos os strings finitos sobre o
alfabeto {1,2,…,N}
– cada string indica o numero de passos da máquina M’
que serão executados e as opções consideradas em
cada passo.
• Para cada um destes strings z :
– Coloca-se z na terceira fita
– Coloca-se o string de input w na primeira fita
– Utiliza-se a segunda fita para efetuar os passos
indicados na terceira fita em cima do input w da
primeira fita
• Se a máquina M’ aceita w então em algum
momento um destes cálculos termina em qa
δ(q0,0) = {(q0,0,R),(q1,1,R)}
δ(q0,1) = {(q0,1,R)}
δ(q0,B) = {(qa,B,R), (q1,B,R)}
0
0
1
B
1
δ(q1,0) = {(q1,0,R)}
δ(q1,1) = {(q1,1,R)
δ(q1,B) = {(qr,B,R), (q1,B,R)}
B
0
0
q0
0 q00
1
1
B
B
1 q0
B
1
q0
1
qa
q0
B
qr
0
q1
0
0
q1
q1
1
q1
q0
1
q0 q0 q0
q0
q0
q1
B
q1
B
q1
B
qr
1
δ(q0,0) = {(q0,0,R),(q1,1,R)}
δ(q0,1) = {(q0,1,R)}
δ(q0,B) = {(qa,B,R), (q1,B,R)}
0
0
1
B
1
δ(q1,0) = {(q1,0,R)}
δ(q1,1) = {(q1,1,R)
δ(q1,B) = {(qr,B,R), (q1,B,R)}
B
0
0
q0
0 q00
1
1
B
B
1
B
1
q0
2
qa
q0
B
qr
0
q1
0
0
q1
q1
1
q1
q0
1
q0 q0 q1
q0
q0
q0
q1
B
q1
B
q1
B
qr
1
δ(q0,0) = {(q0,0,R),(q1,1,R)}
δ(q0,1) = {(q0,1,R)}
δ(q0,B) = {(qa,B,R), (q1,B,R)}
0
0
1
B
1
δ(q1,0) = {(q1,0,R)}
δ(q1,1) = {(q1,1,R)
δ(q1,B) = {(qr,B,R), (q1,B,R)}
B
0
0
q0
0 q00
1
1
q0 q0 q0 q0
B
B
1 q0
B
1
q0
1
1
qa
q0
B
qr
0
q1
0
0
q1
q1
1
q1
q0
1
q0 qa
q0
q0
q1
B
q1
B
q1
B
qr
1
Exercicio
Seja M’ máquina de Turing não-determinista
B = número de comandos de M’
N = número máximo de possibilidades para cada
comando de M’
Considere o conjunto W de todos os strings FINITOS de
comprimento B sobre o alfabeto {1,…,N}.
Construa uma máquina determinista M” da mesma
maneira como foi construida a máquina M
anteriormente, só que na fita 3 entra-se os strings de W.
Pergunta-se: Esta máquina M” determinista é
equivalente à máquina não-determinista M’ ?