Máquina de Turing - Parte I

Prévia do material em texto

MÁQUINA DE TURING 
Marcelo Guerra 
INTRODUÇÃO 
 Vimos os conceitos: 
 Linguagens Regulares 
 Autômatos finitos 
 Linguagens Livres de Contexto 
 Autômatos com Pilha 
 
 As linguagens regulares são um subconjunto das 
linguagens livres de contexto. 
 Autômatos com pilha são mais poderosos que 
autômatos finitos. 
 
 As LLCs são de escopo limitado 
 {AnBnCn /n>=0} não é uma LLC. 
INTRODUÇÃO 
 ACP x Autômatos finitos 
 A diferença está na memória temporária (Pilha) 
 
 Existirão famílias de linguagens mais poderosas 
se dermos mais flexibilidade de memória ao 
autômato? 
 
 O que podemos dizer sobre o autômato mais 
poderoso e os limites da computação? 
 
 Isto nos leva ao conceito de Máquina de Turing. 
MÁQUINA DE TURING 
 Em 1936, Alan Turing propôs um modelo conhecido 
como Máquina de Turing. 
 
 Atualmente, a MT é aceita como uma formalização de 
um algoritmo ou função computável, 
 ou seja, uma sequência finita de instruções, as quais podem 
ser realizadas mecanicamente, em um tempo finito. 
 
 Ainda em 1936, Alonzo Church apresentou a Hipótese 
de Church: 
 Qualquer função computável pode ser processada por uma 
máquina de Turing capaz de processar a função. 
MÁQUINA DE TURING 
 Basicamente, é um autômato finito que tem uma 
fita de comprimento infinito onde podemos ler e 
escrever dados. 
 
NOTAÇÃO PARA A MÁQUINA DE TURING 
 A máquina consiste em um controle finito 
 que pode se encontrar em qualquer estado de um 
conjunto finito de estados 
 Existe uma fita dividida em células, cada uma 
podendo conter qualquer símbolo de um conjunto 
finito de símbolos 
 B B X1 X2 Xi Xn B B ... ... 
Unidade 
de controle 
finito 
NOTAÇÃO PARA A MÁQUINA DE TURING 
 Inicialmente, a entrada – uma string de 
comprimento finito de símbolos – é escolhida a 
partir do alfabeto de entrada e colocada na fita 
 Todas as demais células, à direita e à esquerda da string 
de entrada estão em branco, símbolo exclusivo da fita, 
junto com outros símbolos 
 B B X1 X2 Xi Xn B B ... ... 
Unidade 
de controle 
finito 
NOTAÇÃO PARA A MÁQUINA DE TURING 
 Associada à fita existe a cabeça da fita, que fica 
sempre posicionada em uma das células: 
 A cabeça pode se mover uma célula para a direita ou 
para a esquerda da fita. 
 Pode ler e escrever um único símbolo em cada 
movimento. 
 
 B B X1 X2 Xi Xn B B ... ... 
Unidade 
de controle 
finito 
NOTAÇÃO PARA A MÁQUINA DE TURING 
 Um movimento da máquina de Turing é uma 
função do estado do controle finito e do símbolo 
lido. 
 Em um movimento, a máquina: 
1. Mudará de estado 
2. Gravará um símbolo na célula lida, substituindo 
aquele que lá estava. 
 B B X1 X2 Xi Xn B B ... ... 
Unidade 
de controle 
finito 
NOTAÇÃO PARA A MÁQUINA DE TURING 
3. Movimentará a cabeça da fita para a esquerda ou 
direita. 
 A cabeça não deverá permanecer estacionária: um 
movimento deve ser feito. 
 B B X1 X2 Xi Xn B B ... ... 
Unidade 
de controle 
finito 
NOTAÇÃO PARA A MÁQUINA DE TURING 
 Formalmente, uma máquina de Turing (MT) é 
dada pela tupla de 7 valores 
 
 M = (Q, Σ, Γ, δ, q0, B, F) 
 cujos significados são: 
 Q: é o conjunto finito de estados do controle finito 
 Σ: conjunto de símbolos de entrada 
 Γ: conjunto completo de símbolos da fita, Σ ⊂ Γ 
 q0: é o estado inicial 
 B: é o símbolo branco – B ∈ Γ e B ∉ Σ. Inicialmente, B 
aparece em todas as células da fita, exceto aquelas 
contendo a entrada. 
 F: O conjunto de estados finais, subconjunto de Q 
 
 
NOTAÇÃO PARA A MÁQUINA DE TURING 
 δ é a função de transição: os argumentos de δ(q,X) 
são: um estado e um símbolo da fita 
 
 O valor de δ(q,X), se definido, é uma tripla (p, Y, D) 
onde 
 
1. p é o próximo estado 
 
2. Y é o símbolo, em Γ, gravado na célula sendo 
varrida, em substituição a X 
 
3. D é uma direção ou sentido, L ou R, indicando 
esquerda ou direita 
EXEMPLO DE MOVIMENTAÇÃO NA MT 
 Considere a transição: δ(q0,a) = (q1,d,R) 
a b c 
q0 
d b c 
q1 
EXEMPLO 
 Considere a máquina de Turing: 
 Q={q0,q1} 
 Σ={a,b} 
 Γ = {a,b,B} 
 F= {q1} 
 q0 é o estado inicial 
 δ(q0,a) = (q0,b,R) 
 δ(q0,b) = (q0,b,R) 
 δ(q0,B) = (q1,B,L) 
 
 
 
a a 
q0 
b a 
q0 
b b 
q0 
b b 
q1 
Estado final 
DESCRIÇÕES INSTANTÂNEAS PARA MT’S 
 Para descrever formalmente o que uma MT faz, 
precisamos de uma notação para suas configurações 
(ou descrições instantâneas) 
 
 Só mostramos em uma DI células que contêm 
símbolos não-brancos 
 Em condições especiais, por exemplo, quando a cabeça 
move-se para uma célula em branco, a DI inclui alguns 
brancos à esquerda ou à direita da cabeça 
 
 Além da fita, representamos: 
 O controle finito e a cabeça da fita 
 Incorporamos o estado à fita e o colocamos à esquerda da 
célula lida 
DESCRIÇÕES INSTANTÂNEAS PARA MT’S 
 O movimento de uma configuração a outra é 
denotado pela notação ⊦M usada para ACP’s. 
 
 Ex: δ(q1,c) = (q2,e,R) 
 
 Um movimento possível é: 
 
 abq1cd ⊦abeq2d 
DESCRIÇÕES INSTANTÂNEAS PARA MT’S 
 O string X1X2...Xi-1qXiXi+1...Xn representa uma DI, 
onde: 
 
1. q é o estado da MT 
 
2. A cabeça da fita está varrendo o i-ésimo símbolo a 
partir da esquerda 
 
3. X1X2...Xn é a parte da fita entre o não branco mais à 
esquerda e o mais à direita 
 Como exceção, se a cabeça estiver à direita do não 
branco mais à esquerda (ou de maneira análoga do 
lado direito), algum prefixo ou sufixo será branco e i 
será 1 ou n, respectivamente. 
 
EXEMPLO 
a a 
q0 
b a 
q0 
b b 
q0 
b b 
q1 
 Descrições instantâneas: 
 
 q0aa 
 
 
 
 bq0a 
 
 
 bbq0B 
 
 
 
 bq1b 
q0aa ⊦bq0a ⊦bbq0B ⊦bq1b ou q0aa ⊦* bq1b 
 
δ(q0,a) = (q0,b,R) 
δ(q0,b) = (q0,b,R) 
δ(q0,B) = (q1,B,L) 
MT COMO RECONHECEDORAS DE 
LINGUAGEM 
 Uma cadeia w é escrita sobre a fita, com brancos 
preenchendo as porções não usadas. 
 
 A MT começa no estado inicial, com a cabeça da 
fita no símbolo mais à esquerda de w. 
 
 Se após uma sequência de movimentos, a MT 
entra em um estado final e pára, então w é 
considerada reconhecida pela MT. 
 
 Por convenção, quando uma MT entra em um 
estado final, ela pára. 
 
MT COMO RECONHECEDORAS DE 
LINGUAGEM 
 Definição: 
 
 Seja M = (Q, Σ, Γ, δ, q0, B, F) uma máquina de 
Turing. Então a linguagem reconhecida por M é: 
 
 L(M) = {w  Σ* | q0w ⊦* x1qfx2} 
 
 Onde qf F 
 x1,x2 Γ* 
 


EXEMPLO 
 Para Σ={0,1}, projetar uma máquina de Turing que 
reconhece a linguagem denotada pela expressão 
regular 0* 
 
 Colocamos uma cadeia pertencente à linguagem na fita 
precedidos e seguidos de uma infinidade de brancos. 
 Começando no lado esquerdo da entrada, lemos cada 
símbolo e checamos se ele é um 0. 
 Se for 0 , continuamos movendo para a direita. 
 Se atingirmos um branco, terminamos e reconhecemos a 
cadeia. 
 Se a cadeia contiver um 1 em algum lugar, paramos em 
algum estado não final e a cadeia não pertence à 
linguagem. 
 
EXEMPLO 
 M=({q0,q1}, {0,1}, {0,1,B}, δ, q0, B, {q1}) 
 
 δ(q0,0) = (q0,0,R) 
 δ(q0,B) = (q1,B,L) Sequência de descrições instantâneas para 000 
 
 q0000 ⊦0q000 ⊦00q00 ⊦000q0B ⊦00q10 
EXEMPLO 
 Construímos a MT para a linguagem {anbn| n 1} 
e vemos como a máquina se comporta 
 
 Colocamos uma cadeia pertencente à linguagem na 
fita precedidos e seguidos de uma infinidade de 
brancos 
 A MT trocará um a por um X e um b por um Y até 
todos os símbolos terem sido comparados 
 
 Começando à esquerda da entrada, a MT troca 
repetidamente a’s por X e se move para a direita 
sobre qualquer a e Y que vier até chegar a um b 
 
EXEMPLO 
 Ela troca esse b por um Y e se move para a 
esquerda, sobre os Y’s e a’s que encontrar até 
encontrar um X 
 Nesse ponto, a MT procura por um a 
imediatamente à direita. Se encontrar, troca-o 
por X e repete o processo trocando o b 
correspondente por Y 
 Se a entrada não contiver anbn, a MT deixará de 
ter um próximo movimento e morrerá sem aceitar 
a entrada 
 Se terminar de trocar todos os a’s por X, ela 
trocará o último b por Y e depois descobrirá que a 
entrada está na forma anbn e aceitará. 
EXEMPLO 
 M=({q0,q1,q2,q3,q4}, {a,b}, {a,b,X,Y,B}, δ, q0, B, {q4}) 
 δ é dado por: 
 
Estado a b X Y B 
q0 (q1,X,R) (q3,Y,R) 
q1 (q1,a,R) (q2,Y,L) (q1,Y,R) 
q2 (q2,a,L) (q0,X,R) (q2,Y,L) 
q3 (q3,Y,R) (q4,B,R) 
q4 
EXEMPLO 
 Sequência de descrições instantâneas para “aabb” 
 
 q0aabb ⊦Xq1abb ⊦Xaq1bb ⊦Xq2aYb ⊦q2XaYb ⊦ 
 Xq0aYb ⊦XXq1Yb ⊦XXYq1b ⊦XXq2YY ⊦ Xq2XYY ⊦ 
 XXq0YY ⊦XXYq3Y ⊦ XXYYq3B ⊦XXYYBq4B 
 
 A MT pára em um estado final, logo a cadeia 
aabb é aceita. 
 
 Repita o exercício para a cadeia “aaabb” 
Estado a b X Y B 
q0 (q1,X,R) (q3,Y,R) 
q1 (q1,a,R) (q2,Y,L) (q1,Y,R) 
q2 (q2,a,L) (q0,X,R) (q2,Y,L) 
q3 (q3,Y,R) (q4,B,R) 
q4