Variantes de Máquina de
Turing
Teoria da Computação
Máquinas de Turing com
Várias Fitas
Definição :
Mk = (Q, Σ, Γ, δ, q0, qa, qr)
k = número de fitas
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
δ : Q x Γk  Q x Γk x {L,R}k
δ(q,(s1,s2,...,sk)) = (q’,(s’1,s’2,...,s’k),(L,R,R,L...,R))
δ(q0,(0,B,B)) = (q1,(1,0,1),(R,R,R))
Fita 1
0
0
0
2
1
0
2
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
qo
Fita 2
B
qo
Fita 3
B
qo
δ(q1,(0,B,B)) = (q2,(0,0,0),(L,R,L))
1
0
0
2
1
0
2
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
q1
0
B
q1
1
B
q1
δ(q1,(0,B,B)) = (q2,(0,0,0),(L,R,L))
1
0
0
2
1
0
2
B
B
B
B
0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
q2
0
q2
1
q2
0
B
Linguagem aceita
• M = máquina de Turing com k fitas
• L(M) = conjunto dos strings aceitos por M
• String aceito por M = a partir da
configuração inicial é possível chegar
numa configuração de aceitação (estado
final qa).
Teorema
• Seja M uma máquina de Turing com k fitas.
Então existe uma máquina de Turing S simples
(com uma fita) tal que :
L(M) = L(S)
Isto é: Toda máquina de Turing com k fitas é
equivalente a uma máquina de Turing simples
(com 1 única fita)
Como simular uma configuração de
M’ numa máquina com 1 fita:
1
0
B
B
B
B
B
B
B
B
B
0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
#
0
0
#
q2
0
q2
1
0
B
q2
#
1
0
0
B
#
1
Construção da Máquina Simples S
S = No input w faça:
1. Transforme o input w no correspondente input w’ que
simula w na fita 1 de M’.
2. Para simular um movimento de S:
1.
2.
3.
4.
Varra a fita de S, a partir do primeiro # até o (k+1) – ésimo, e
“memorize” os k simbolos com pontinhos.
Aplique a transição de M’ correspondente.
Varra a fita de S novamente a partir do primeiro #, aplicando
as modificações ditadas pela transição de M’ correspondente
à sequência de simbolos memorizada.
Caso um pontinho deva ser colocado em cima de um #,
escreva B com pontinho neste lugar, e dê um shift na fita para
a direita a partir desta posição.
Máquinas de Turing Não
Deterministas
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
Árvore 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
L(M) = Linguagem aceita pela máquina não-determinista M
= conjunto dos strings para os quais existe um caminho na árvore
de execução que termina em qa
qa
qr
qr
looping
qr
M aceita w, w pertence a L(M)
M não aceita w
qr
qr
looping
M não aceita w
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).
Equivalência: Máquinas
deterministas e não-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 máquina não-derminista
• Seja N = número máximo de escolhas
possíveis 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 máquina determinista
M de 3 fitas equivalente a M’
FITA DE INPUT
0
0
1
1
FITA DE CÁLCULO
FITA DAS POSSIBILIDADES
1
1
2
Serão executados 3 passos de M’
Passo 1 : opção 1
Passo 2 : opção 1
Passo 3 : opção 2
• Ordena-se todos os strings finitos sobre o
alfabeto {1,2,…,N}
– cada string indica o número 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
1
B
δ(q1,0) = {(q1,0,R)}
δ(q1,1) = {(q1,1,R)
δ(q1,B) = {(qr,B,R), (q1,B,R)}
B
0
q0
0
0 q00
1
1
B
B
1 q0
B
1
1
B
q0 q0 q0
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
1
B
δ(q1,0) = {(q1,0,R)}
δ(q1,1) = {(q1,1,R)
δ(q1,B) = {(qr,B,R), (q1,B,R)}
B
0
q0
0
0 q00
1
1
B
B
1
B
1
2
B
q0 q0 q1
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
1
B
δ(q1,0) = {(q1,0,R)}
δ(q1,1) = {(q1,1,R)
δ(q1,B) = {(qr,B,R), (q1,B,R)}
B
0
q0
0
0 q00
1
1
q0 q0 q0 q0
B
B
1 q0
B
1
1
1
q0 q0 q0 q0
B
q0 qa
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