Máquina de turing
476 palavras
2 páginas
Máquina de TuringFita infinita para ambos os lados
Rodolfo M. Favaretto
Teoria da Computação PPGC - UFPel
A modificação da máquina de Turing permitindo que a fita seja infinita para os dois lados não aumenta o seu poder computacional.
Fita Infinita à Esquerda e à Direita
... a-3 a-2 a-1 a1 a2 a3 ...
Fita Infinita à Esquerda e à Direita
... a-3 a-2 a-1 a1 a2 a3 ... ❂ Símbolo de início da fita não faz sentido
Na realidade, a fita infinita à esquerda e à direita pode ser facilmente simulada pela fita tradicional da máquina de Turing.
As células pares representam a parte direita da fita e as células ímpares a esquerda.
0 1 2 3 4 5 6
❂ a1 a-1 a2 a-2 a3 a-3 ...
O símbolo ❂ representa o marcador de início da fita.
0 1 2 3 4 5 6
❂ a1 a-1 a2 a-2 a3 a-3 ...
Início
As células pares representam a parte direita da fita e as células ímpares a esquerda.
0 1 2 3 4 5 6
❂ a1 a-1 a2 a-2 a3 a-3 ...
Parte direita da fita
As células pares representam a parte direita da fita e as células ímpares a esquerda.
0 1 2 3 4 5 6
❂ a1 a-1 a2 a-2 a3 a-3 ...
Parte esquerda da fita
Exemplo
MT = ({a, b}, {q0, q1, q2, q3, q4}, ∏, q0, {q4}, {A,B}, ß, δ)
Exemplo
...
δ q0 a
a
b
b
β
...
Exemplo
...
δ q0 a
a
b
b
β
...
Exemplo
...
δ
a q0 a
b
b
β
...
Exemplo
...
δ
a q0 a
b
b
β
...
Exemplo
...
δ
A
a q1 b
b
β
...
Exemplo
...
δ
A
a q1 b
b
β
...
Exemplo
...
δ
A
a
b q1 b
β
...
Exemplo
...
δ
A
a
b q1 b
β
...
Exemplo
...
δ
A
a q2 B
b
β
...
Exemplo
...
δ
A
a q2 B
b
β
...
Exemplo
...
δ
A q2 a
B
b
β
...
Exemplo
...
δ
A q2 a
B
b
β
...
Exemplo
...
δ
A
a q0 B
b
β
...
Exemplo
...