MaquinasTuring

Prévia do material em texto

Teoria da Computação 
Máquinas de Turing 
 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
 
 
 
DCC-UFLA, Lavras 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Autômatos Finitos: Desafio 
 Projete um automâto finito (determinístico ou 
não-determinístico) que reconheça a seguinte 
linguagem: 
𝐿 = 0𝑛1𝑛 | 𝑛 ≥ 0 
2 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Autômatos Finitos: Desafio 
 Problema: Para reconhecer 𝐿, um autômato precisa de 
alguma maneira “lembrar” a quantidade de 0‘s lidos na 
entrada 
 Temos que a quantida de 0‘s não é limitada (0𝑛, onde 
𝑛 não é limitado) 
 Para reconhecer 𝐿 seria necessário “acompanhar“ uma 
quantidade ilimitada de possibilidades de 
processamento 
 Automâtos finitos realizam este “acompanhamento” 
através de estados e transições 
 Entretanto, o número de estados é limitado... 
3 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Expressões Regulares, AFs e 
Linguagens Regulares 
4 
Expressoões 
Regulares 
Operações 
Regulares 
{∪,°, *} 
 
Autômatos 
Finitos 
Linguagens 
Regulares 
reconhecem 
descrevem 
Também podemos dizer que autômatos 
descrevem linguagens regulares 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Gramáticas e Linguagens Livres de 
Contexto e Autômatos de Pilha 
5 
Grámaticas Livres 
de Contexto 
Autômatos de 
Pilha 
Linguagens Livres 
de Contexto 
reconhecem 
descrevem 
Também podemos dizer que 
autômatos de pilha descrevem 
linguagens livres de contexo 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Linguagens e Autômatos 
6 
Linguagens Livres de 
Contexto 
Linguagens Regulares 
Autômato de 
Pilha 
Autômato Finito 
reconhece 
reconhece 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Linguagens Enumeráveis Recursivamente ou Tipo 0 
Linguagens Sensitivas ao Contexto 
ou Tipo 1 
Linguagens Livres de Contexto 
ou Tipo 2 
Hierarquia de Chomsky 
7 
Linguagens Regulares ou Tipo 3 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Linguagens e Máquinas 
8 
Linguagens Máquinas 
Recursivamente 
Enumeráveis 
Máquina de Turing, 
Máquina de Turing 
Não-Determinística 
Sensitivas ao 
Contexto 
Autômato Limitado 
Linearmente 
Livres de 
Contexto Autômato de Pilha 
Regulares 
Autômato Finito 
Determinístico, Automato 
Finito Não-Determinístico 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Linguagens e Máquinas 
9 
Linguagens Máquinas 
Recursivamente 
Enumeráveis 
Máquina de Turing, 
Máquina de Turing 
Não-Determinística 
Sensitivas ao 
Contexto 
Autômato 
Linearmente Limitado 
Livres de 
Contexto Autômato de Pilha 
Regulares 
Autômato Finito 
Determinístico, Automato 
Finito Não-Determinístico 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Máquinas de Turing (MT) 
10 
 Modelo computacional 
proposto por Alan Turing 
em 1936 
 Máquina de estados finita 
com mémoria ilimitada 
 Modelo computacional 
universalmente aceito 
como possuindo poder de 
expressão equivalente aos 
computadores modernos 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Máquinas de Turing (2) 
 Componentes: 
• Uma fita infinita usada como dispositivo de entrada (a 
palavra de entrada encontra-se inicialmente escrita na 
fita), como aréa de memória para informações 
intermediárias de processamento, e como dispositivo 
de saída (resultados podem ser escritos na fita após a 
computação) 
• Uma cabeça de leitura/escrita (cabeça le) e 
movimentação ao longo da fita 
• Um controle de estados finitos 
 A MT pode Aceitar ou Rejeitar a entrada caso a 
máquina entre nos estados de aceitação ou 
rejeição, respectivamente; ou então a MT pode 
continuar executando para sempre 
11 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Máquinas de Turing (3) 
 Uma MT pode escrever e ler na fita, irrestritamente 
 A cabeça de leitura/escrita (cabeça le) pode se movimentar 
tanto para a direita quanto para a esquerda 
 A fita é infinita 
• Entretanto, por simplicidade, vamos convencionar que a fita pode 
extender-se indefinidamente apenas da esquerda para a direita 
 Estados especificados para rejeição ou aceitação possuem 
efeito imediato 
 
12 
controle 
a b c b ˽ ˽ ... ˽ 
símbolo em branco 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 
13 
 Considere a linguagem B = {p#p | 𝑝 ∈ 0,1
∗
 } 
 Vamos descrever uma MT para aceitar a 
entrada se ela pertence a B 
0 1 0 0 1 1 1 1 0 # 0 1 0 0 1 1 1 1 0 ˽ … 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo (2) 
14 
0 1 0 0 1 1 1 1 0 # 1 1 0 0 1 1 1 1 0 ˽ … 
0 1 0 0 1 1 1 1 0 # x 1 0 0 1 1 1 1 0 ˽ … 
x 1 0 0 1 1 1 1 0 # x 1 0 0 1 1 1 1 0 ˽ … 
x x x x x x x x x # x x x x x x x x x ˽ … 
. . 
. 
Aceita 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo (3)* 
1. Percorra toda a entrada e verifica se a mesma 
contém um único símbolo #. Se não for o caso, 
Rejeita 
2. Faça movimentos em zig-zag em torno do 
símbolo #: movimente a cabeça para ler um 
símbolo à esquerda de # e depois à direita. 
Identifique cada símbolo já lido sobescrevendo 
este símbolo com X 
3. Quando todos os símbolo à esquerda tiverem 
sido marcados, verifique se ainda existem 
símbolos à direita. Se sim, Rejeita; se não, Aceita 
15 
Esta descrição visa passar uma idéia inicial a respeito do processamento de MTs. O 
formato para descrição de alto-nível de MTs será refinado mais adiante. 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Definição Formal de MTs 
 Uma Máquina de Turing é uma sétupla, 
𝑄, ∑, Γ, 𝛿, 𝑞𝑎, 𝑞𝑟 onde 𝑄, ∑, Γ são conjuntos finitos e 
1. 𝑄 é o conjunto de estados; 
2. ∑ é o alfabeto de entrada; 
3. Γ é o alfabeto da fita que contém necessariamente o 
alfabeto de entrada e o símbolo “branco” ˽ , onde 
˽ ∈ Γ − ∑ ; portanto temos que ∑ ⊂ Γ 
4. : Q Γ Q Γ {L, R}; 
5. q0 ∈ Q é o estado inicial 
6. qa é o estado de Aceitação 
7. qr é o estado de Rejeição e qa ≠qr 
 
16 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
A Função de Transição 
 : Q Γ Q Γ {L, R} 
 L e R determinam movimentos da cabeça para 
a esquerda e direita, respectivamente 
 Exmplo: (q,a) (r, b, L) 
• Quando a máquina estiver em um estado q e a 
cabeça está sobre um quadrante da fita contendo 
o símbolo a, então a máquina vai para o estado r, 
sobescreve o símbolo a com o símbolo b e a 
cabeça le é movimentada para a esquerda 
17 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
A Função de Transição: Exemplos 
18 
0 1 0 0 1 1 1 1 0 # 1 1 0 0 1 1 1 1 0 ˽ … 
(q1,1) (q2, x, L) 
0 1 0 0 1 1 1 1 0 # x 1 0 0 1 1 1 1 0 ˽ … 
Representação em 
diagrama de estados 
q1 q2 
1→x, L 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
A Palavra de Entrada 
 Inicialmente a máquina M recebe uma palavra 
𝑝1𝑝2 … 𝑝𝑛 ∈ ∑* escrita nos n quadrantes 
mais à esquerda da fita 
 O restante da fita é preenchido com simbolos 
˽ ; portanto, como ˽ ∉ ∑, o primeiro símbolo 
branco denota o final da entrada 
19 
e n t r a d a ˽ ˽ ˽ … 
Exemplo 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
A Computação de MTs 
 Uma MT M inicia sua computação 
posicionando a cabeça de le no primeiro 
quadrante da fita, da esquerda para a direita 
20 
e n t r a d a ˽ ˽ ˽ … 
Exemplo 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
A Computação de MTs (2) 
 A computação prossegue de acordo com a 
entrada e as regras descritas pela função de 
transição de estados 
 A cabeça de le movimenta-se de acordo com as 
regras de transição. 
 De acordo com a nossa convenção, a única 
exceção ocorrerá quando a transição indicar 
movimentação para a esquerda e cabeça esteja 
sobre o primeiro símbolo da fita. Neste caso a 
cabeça permance no mesmo lugar 
21 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
A Computação de MTs (2) 
 A computação continua até M entrar nos 
estados qa ou qr . Neste ponto, M para. Caso 
contrárioM continua executando para sempre 
22 
q 
qa ˽ → ˽, R 
qr 0 → 0, R 
loop 
aceita 
rejeita 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Configuração de MTs 
 Existem três componentes que são 
modificáveis em uma MT 
• Estados 
• Conteúdo da fita 
• Localização da cabeça de le 
 O conjunto destes três componentes é 
chamado de configuração da MT 
23 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Notação Para Configurações 
 u q v representa uma configuração de MT onde 
• q é um estado 
• o conteúdo da fita é uv, onde u e v são palavras sobre 
o alfabeto Γ 
• A cabeça de le encontra-se sobre o primeiro 
símbolo de v. A fita contém apenas símbolos 
brancos após o último símbolo de v 
24 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 
25 
1 2 3 4 5 6 7 8 9 ˽ … 
qi 
• u = 1234 
• v = 56789 
• Configuração: 1234qi56789 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 1 
 Apresente o diagrama para a máquina M1 que 
reconhece a linguagem B = {p#p | 𝑝 ∈ 0,1
∗
 } 
 Simplificação: não é necessário representar o 
estado de rejeição e as transições que 
conduzem a este estado 
 
26 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 2: 
Solução 
27 
q1 
q8 
qa 
q6 
q7 
q2 
q4 
q3 
q5 
#→R 
x→R 
˽→R 
#→R 
0,1→R 
x→R 
0,1,x→L 
#→L 
x→R 
0,1→L 
#→R 
0,1→R 
x→R 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Configurações de MTs 
 Uma configuração C1 produz outra 
configuração C2 se a MT pode transitar de C1 
para C2 em um único passo, isto é, se existe 
uma transição de estados que conduz a MT da 
configuração C1 para C2 
28 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Configurações de MTs (2) 
 Considere a, b, e c em Γ e u e v em Γ* e os 
estados qi e qj 
 Caso em que MT move-se para a esquerda 
• Considere as configurações uaqibv e uqjacv 
• Dizemos que uaqibv produz uqjacv se na função de 
transição: 
(q1,b) (qj, c, L) 
 Caso em que MT move-se para a direita 
• Considere as configurações uaqibv e uacqjv 
• Dizemos que uaqibv produz uacqjv se na função de 
transição: 
(q1,b) (qj, c, R) 
 
 
 
 
 
 
29 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Configurações de MTs (3) 
 Ínicio da fita -> qibv 
• qibv produz qicv quando o movimento é para 
esquerda (cabeça le não se movimenta ) 
• qibv produz cqiv quando o movimento é para 
direita 
 Final da fita 
• uaqi é equivalente a uaqi ˽ 
30 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Configurações Especiais 
 Configuração de início: q0p para uma entrada p 
 Configuração de aceitação: o estado da 
configuração é qa 
 Configuração de rejeição: o estado da 
configuração é qr 
 Configurações de aceitação e rejeição são 
também configurações de parada porque não 
produzem outras configurações 
31 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Aceitação da Entrada 
 Uma MT aceita uma entrada p se existe uma 
sequência de configurações C1C2,...,Ck onde 
• C1 é uma configuração de ínicio de M para entrada p 
• Cada Ci produz Ci+1 
• Ck é uma configuração de aceitação 
 A coleção de palavras que M aceita ou a 
linguagem que M reconhece, denotado por 
L(M), é a linguagem de M 
32 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 2 
 Projete uma TM M2 que reconheça a 
linguagem A = {02
𝑛
𝑛 ≥ 0 
 Ou seja a TM deve reconhecer palavras de 
comprimento igual a alguma potência de 2 (0, 
00, 0000, 00000000, etc, mas não 000 ou 
000000) 
33 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 1 (2) 
 Intuição: |p| = 2n = 2 X 2 X ... X 2 
34 
n 
 Caso trivial: comprimento de p é ímpar->Rejeita 
 Se o comprimento de p é par e realizarmos divisões 
sucessivas por 2 iremos obter em algum momento o 
resultado 1 (após n divisões). Qualquer outro número 
ímpar obtido como resultado de uma divisão implica 
que o tamanho de p não é uma potência de dois 
 Como podemos expressar esta computação usando 
uma MT? 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 2 (3) 
1. Percorra a palavra p realizando o seguinte 
procedimento: após ler um 0, marque o zero 
seguinte com x. Se apenas um 0 foi lido no 
Passo 1, Aceita 
2. Se a fita continha mais de um zero e o 
número é impar, Rejeita 
3. Volte a cabeça le para o começo da fita 
4. Vá para o passo 1 
35 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 2 (4) 
 M2 = (Q, ∑, Γ, , q1, qa, qr) 
 Q = {q1, q2, q3, q4, q5, qa, qr}, 
 ∑={0}, 
 Γ = {0, x, ˽} 
 (diagrama de estados nos próximos slides) 
 Estado inicial, de aceitação e rejeição são q1, qa, e 
qr, respectivamente 
 Notação: 
• 0 → x,R: associado a transição saindo do estado q1 
para q2 corresponde a (q1,0) = (q2, x, R) 
• 0 → R: significa que o símbolo lido não é sobescrito ou 
permance o mesmo: (q1,0) = (q2, 0, R) 
36 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 2 (5) 
37 
q1 q2 q3 
qr qa q4 
q5 
˽→R 
x→R 
0→˽, R 
˽→R 
˽→R 
0→x, R 
x→R 
0→R 
x→R 
0→x, R 
0→L 
x→L 
x→R 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Sequência de Configurações 
 Considerando a MT anterior, apresente a sequência de 
configurações para entrada 0 
1. q10 
2. ˽q2 
3. ˽ ˽qa 
 
 Apresente a sequência de configurações para entrada 000 
1. q1000 
2. ˽ q200 
3. ˽ xq30 
4. ˽ x0q4 
5. ˽ x0 ˽ qr 
 
38 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 4 
 Apresente a sequência de configurações para as 
entrada 000000 e 000000000000 
 
39 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 4 
 Projete uma MT para resolver o problema dos 
elementos distintos. Dado um lista de palavras 
sobre {0,1} separadas pelo símbolo #, a MT 
deve aceitar a entrada se todas as palavras 
contidas na lista forem diferentes 
• L = {#a1#a2…#an} cada ai Є {0,1}* and ai ≠ aj 
para i ≠ j 
40 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 4 
 Projete uma MT para resolver o problema dos 
elementos distintos. Dado um lista de palavras 
sobre {0,1} separadas pelo símbolo #, a MT 
deve aceitar a entrada se todas as palavras 
contidas na lista forem diferentes 
• L = {#a1#a2…#an} cada ai Є {0,1}* and ai ≠ aj 
para i ≠ j 
 Dica: Represente loops aninhados na MT (for-
for) 
41 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 4 
 Projete uma MT para resolver o problema dos 
elementos distintos. Dado um lista de palavras 
sobre {0,1} separadas pelo símbolo #, a MT 
deve aceitar a entrada se todas as palavras 
contidas na lista forem diferentes 
• L = {#a1#a2…#an} cada ai Є {0,1}* and ai ≠ aj 
para i ≠ j 
 Dica: Represente loops aninhados na MT (for-
for) 
42 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 3: Solução 
1. Escreva um marcador (m1) no lugar do primeiro 
símbolo da entrada. Se o símbolo original for #, 
prossiga para o próximo passo; caso contrário 
rejeite 
2. Percorra a fita até o próximo símbolo # e escreva 
um segundo marcador sobre ele (m2). Se 
nenhum for encontrado, aceite (a lista de 
entrada contém apenas 1 palavra) 
3. Fazendo movimentos em zig-zag, compare as 
palavras à direita de cada marcador. Se forem 
iguais rejeite 
43 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 3: Solução (2) 
4. “Mova” m2 para o próximo símbolo #, isto é, 
substitua m2 por # na sua posição original e 
escreva-o na posição do próximo símbolo # 
encontrado. Se nenhum outro # for encontrado, 
então mova m1 (marcador mais a esquerda) 
para o próximo símbolo # à sua direita e depois 
mova m2 para próximo símbolo # à direita de 
m1. Neste ponto, se não existir mais símbolos # 
para m2, então todas palavras foram 
comparadas. Aceite 
5. Volte ao passo 3 
 
44 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Linguagens Turing Reconhecível 
 Uma linguagem é chamada Turing 
reconhecível se alguma MT a reconhece 
 Estas linguagens são também chamadas 
linguagens recursivamente enumeráveis 
45 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Decididores 
 Existem três possibilidades para o resultado de uma 
MT 
• Aceita 
• Rejeita 
• Executa para sempre (entraem “loop infinito” e nunca 
termina) 
 É difícil diferenciar entre MTs de demoram bastante 
para produzir uma saída daquelas que entram em loop 
 Uma MT falha em aceitar uma palavra entrando no 
estado de rejeição ou entrando em loop 
 Um Decididor é uma MT que sempre produz Aceita ou 
Rejeita (fazem uma decisão) como resultado 
46 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Linguagens Turing Decidíveis 
 Uma linguagem é chamada Turing decidível se 
alguma MT a decide 
 Estas linguagens são também chamadas linguagens 
recursivas 
 
 
47 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Relação entre Linguagens 
Reconhecíveis e Decidíveis 
 Toda linguagem decidível é também Turing 
reconhecível. Entretanto algumas linguagens 
são Turing reconhecíveis mas não decidíveis 
48 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 
 Projete uma MT que reconheça a linguagem 
A = { anbncn| n>=0 }. Descreva-a em alto-nível 
49 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 2 
 Projete uma MT que reconheça a seguinte 
linguagem L= {p| p contém um número igual 
de 0s e 1s} 
 
50 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 3 
 Projete uma MT que reconheça a seguinte 
linguagem: 
 
 L = {01𝑛101𝑛2, … , 01𝑛𝑘| 𝑘 > 0 𝑒 𝑛1 < 𝑛2 … <
𝑛𝑘}. 
 
 Informalmente, nas palavras aceitas pela MT, 
cada 0 deverá ser seguido por um número 
crescente de 1’s. A máquina poderá conter uma 
ou duas fitas. Descreva-a em alto-nível 
51 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Variantes de Máquinas de Turing 
 Possíveis variações 
• A fita pode extender-se para ambos os lados 
• Mais de uma fita, e.g., uma fita para escrita e 
outra para leitura 
• Mais de uma cabeça le 
• Máquinas não-determinísticas 
• ... 
52 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Variantes de Máquinas de Turing 
 Todas variações produzem modelos 
computacionais diferentes 
 O modelo original da Máquina de Turing e 
todas suas variantes possuem o mesmo poder 
de expressão – todos modelos reconhecem a 
mesma linguagem 
 Com isso, dizemos que MTs são robustas 
53 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Toy Example 
 Considere a seguinte modificação na função 
de transição: 
• : Q Γ Q Γ {L, R, N} 
 N significa nenhum movimento da cabeça le 
 Poderíamos reconhecer linguagens adicionais 
com esta modificação, i.e., aumentariamos o 
poder do modelo original? 
54 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Toy Example (2) 
 Não. Podemos converter qualquer MT do 
novo modelo em uma MT do modelo original 
• Substitua todas transições envolvendo N por duas 
transições, um com R e outra com L 
55 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Máquinas de Turing Multi-fita 
 MT contendo mais de uma fita (F1, F2,..., Fk) 
 Cada fita possui sua própria cabeça le 
 Inicialmente a entrada está escrita apenas em 
uma fita (convenção: F1). As demais contém 
apenas símbolos brancos 
 
 
56 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Máquinas de Turing Multi-fita 
 Nova função de transição: 
• : Q Γk Q Γk {L, R}k, onde k é o 
número de fitas 
• (qi, a1,...,ak) = (qj, b1, ..., bk, L, R, ..., L) 
• A expressão acima significa que a MT está no 
estado qi quando ela lê os símbolos a1,...,ak para 
F1,...,Fk. A MT transita então para o estado qj 
escrevendo os símbolos b1,...,bk nas fitas fazendo 
os movimentos correspondentes 
 
57 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 
 Projete uma MT multi-fita que aceite palavras 
que são palíndromos 
58 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Equivalência entre MTs Multi-fita e 
MT Convencionais 
 Teorema 3.1: Toda MT multi-fita possui uma 
MT equivalente com apenas uma fita 
 Prova (por construção): mostrar como 
converter uma MT multi-fita M em uma MT 
com apenas uma fita S 
• Idéia: mostrar como simular M com S 
59 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Equivalência entre MTs Multi-fita e 
MT Convencionais (2) 
 Armazene a informação de múltiplas fitas em 
uma única fita 
 Use um símbolo especial (e.g., #) para 
delimitar o conteúdo de cada fita 
 Acompanhe a posição da cabeça le de cada 
fita colocando uma marca especial sobre cada 
sobre o qual a cabeça está posicionada 
60 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
˽ 
Equivalência entre MTs Multi-fita e 
MT Convencionais (2) 
61 
M 
a b c ˽ ... 
0 1 0 ˽ ... 
a b ˽ ... 
S # a b c # 1 0 0 # a b ... 
Símbolos com um ponto em 
cima podem ser interpretados 
como novos símbolos no 
alfabeto da fita 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Equivalência entre MTs Multi-fita e 
MT Convencionais (3) 
 Dado uma entrada p=p1,…,pn, faça: 
1. Primeiramente, S formata a fita para representar 
todas k-fitas de M. O fomato é 
#p1p2…pn#˽#˽#...# 
2. Um único movimento de M é simulado em dois 
passos sobre a fita. O primeiro passo determina os 
símbolos sobre as cabeças le virtuais. O segundo 
passo atualiza as fitas de acordo com o resultado da 
função de transição 
62 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
3. Se em algum ponto, S encontra algum # após algum 
movimento para a direita, isto significa que M 
movimentou sua cabeça para um ponto com 
símbolo branco da fita correspondente. Neste caso, 
todo o conteúdo restante da fita é movido para a 
direita em uma casa (mais especificamente, até o 
último #) e o símbolo branco é na posição da 
cabeça virtual 
 
63 
Equivalência entre MTs Multi-fita e 
MT Convencionais (3) 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Linguagens Reconhecíveis 
e MT Multi-fita 
 Corolário 3.1 : Uma linguagem é Turing 
reconhecível sse alguma MT Multi-fita a 
reconhece 
 
64 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Máquina de Turing 
Não-Determinística (MTND) 
 A qualquer ponto, a computação da máquina 
pode seguir caminhos diferentes 
 Função de transição: 
: 2Q Γ {Q Γ {L, R}} 
 A MTND aceita a entrada quando qualquer 
uma de suas ramificações de computação 
chega a uma configuração de aceitação 
65 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Equivalência Entre MTs e MTNDs 
 Teorema 3.2: Toda MTND possui uma MT 
equivalente 
 Prova (Intuição): Demonstrar que nós 
podemos simular qualquer MTND N com uma 
MT D 
• D tenta todos os possíveis branches da 
computação não-determinística de N. Se D chega 
até uma configuração de aceitação em algum 
destes branches, então D aceita a entrada. Caso 
contrário a simulação de D não termina. 
66 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova Teorema 3.2 (2) 
 Assim como para AFNDs, a computação naõ-
determinística de N pode ser vista como uma 
árvore de possibilidades 
• Cada ramificação da árvore é uma ramificação de não-
determinismo 
• Cada nó é uma configuração de N 
• A raiz é a configuração de início 
 Idéia: M realiza uma busca nesta árvore pelo 
estado de aceitação 
• Qual melhor estratégia de busca? Busca em 
profundidade (depth-first) ou busca em largura 
(breadth-first)? 
67 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova Teorema 3.2 (3) 
 Usando busca em profundidade podemos 
encontrar uma ramificação infinita 
• O algoritmo de busca nunca retorna 
 Melhor estratégia: busca em largura 
• Visita todos os nós no mesmo nível da árvore 
68 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova Teorema 3.2 (4) 
 Considere uma MT determinística com três 
fitas (de acordo com o Teorema 3.1 esta MT é 
equivalente a uma MT com uma única fita) 
 Cada fita possui uma finalidade específica: 
• Fita 1: Contém a palavra de entrada e nunca é 
alterada 
• Fita 2: Mantém a cópia da fita de N em alguma 
ramificação 
• Fita 3: Mantém informação sobre a posição de D 
na árvore de possiblidades 
 
 
69 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova Teorema 3.2 (5) 
 Considere Fita 3. Cada nó na árvore pode ter no 
máximo n filhos, onde n é o tamanho do maior 
conjunto de possíveis escolhas retornado pela função 
de transição de N 
 Atribua um endereçopara cada nó na árvore 
• Uma palavra sobre ∑b = {1,2,…,b} 
• Nó com endereço 321: Chegamos até este nó seguindo o 
3º filho da raiz, u1, o 2º filho de u1, u2, e, finalmente , 1º 
primeiro filho de u2 
• Podem existir endereços inválidos (não conduzem a 
nenhum nó) 
 O alfabeto da Fita 3 é ∑b; a palavra vazia representa a 
raiz 
70 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova Teorema 3.2 (6) 
1. Incialmente Fita 1 contém a palavra de entrada e as 
demais fitas estão vazias 
2. Copie Fita 1 para Fita 2 
3. Use Fita 2 para simular N com entrada 𝑝 em algum 
branch. Antes de cada passo de N, consulte o próximo 
símbolo na Fita 3 para determinar qual escolha fazer entre 
aquelas permitidas pela função de transição de N. Se não 
existirem mais símbolos na Fita 3 ou se sua escolha não-
deterministica é inválida, aborte este branch e vá para o 
passo 4. Também vá para o passo 4 se uma configuração 
de rejeição é encontra. Se uma configuração de aceitação 
for encontrada, Aceite a entrada 
71 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova Teorema 3.2 (7) 
4. Substitua a palavra na Fita 3 com a próxima 
palavra em ordem lexicográfica. Simule o 
próximo branch da computação de voltando 
ao passo 2 
72 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Linguagens Reconhecíveis 
e MTNDs 
 Corolário 3.2: Uma linguagem é Turing 
reconhecível sse alguma MTNDs a reconhece 
73 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
MTNDs e Decididores 
 Uma MTND é um decididor se todas as 
possíveis ramificações de computação 
terminam em todas entradas 
 Corolário 3.3: Uma linguagem é decidível se 
alguma MTND a decide 
74 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Enumeradores 
 Turing reconhecível  recursivamente 
enumerável 
 Além de funcionarem como reconhecedores 
de uma linguagem, MTs também podem ser 
projetadas para enumerar um linguagem – um 
enumerador 
 A computação deste tipo máquina produz 
sequencialmente uma lista exaustiva de uma 
linguagem 
75 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Enumeradores (2) 
 Informalmente, podem ser interpretadas como 
uma impressora conectada 
 Um enumerador não possui entrada---inicia-se 
com uma fita em branco 
 Pode produzir uma lista infinita de palavras, caso 
não termine 
 A linguagem enumerada por E é a coleção de 
todas palavras que eventualmente é impressa 
• Palavras podem aparecer fora de ordem ou com 
repetiçoes 
76 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Enumeradores: Definição Formal 
 Uma Máquina de Turing com k fitas enumera 
um linguagem L se 
i. A computação começa com todas as fitas em 
branco 
ii. Em cada transição, a cabeça le da Fita 1 (a 
fita de saída de impressão) permanece 
parada ou move-se para a direita 
77 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Enumeradores: Definição Formal (2) 
iii. Em qualquer ponto da computação, a parte 
escrita da Fita 1 tem a forma: 
B#u1#u2#...#uk# ou B#u1#u2#...#uk#v, onde ui está em 
L e v está em ∑* 
iv. u será escrita na Fita 1 precedido por um # 
sse u está em L 
 
78 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Linguagem Turing Reconhecível 
e Enumeradores 
 Teorema 3.3: Uma linguagem é Turing 
reconhecível sse algum Enumerador a 
enumera 
79 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova Teorema 3.3 
 Primeiro, nós mostramos que se nós temos 
um Enumerador E que enumera uma 
linguagem A, então existe uma TM M a 
reconhece. A TM trabalha da seguinte forma: 
 M=“Na entrada p: 
1. Execute E. Sempre que E imprimir uma palavra, 
compare ela com p. 
2. Se p aparecer alguma vez como a saída de E, 
aceite” 
 80 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova Teorema 3.3 (2) 
 Agora a segunda parte da prova. Se uma TM 
reconhece uma linguagem A, nós podemos 
construir o seguinte enumerador E para A. 
Seja s1, s2,... a lista de todas possíveis palavras 
em ∑* 
 E = „Ignore a entrada. 
Repita para i=1,2,3… 
Execute M por i passos em cada entrada s1, s2, …, si 
Se si é aceita por M, então imprima si 
81 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Equivalência Entre Modelos 
 Nós temos visto diversas variantes do modelo de 
máquinas de Turing com poder computacional 
equivalente 
 Além disso, vários outros modelos, alguns 
bastante diferentes do conceito de MTs tem sido 
propostos 
 Todos tem em comum o acesso a memória 
infinita 
 Todos são equivalentes em poder computacional 
desde que satisfaçam certos requistos mínimos 
como a habilidade de executar apenas um 
número finito de trabalho em um único passo 
82 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
A Definição de Algoritmo 
 Décimo problema de Hilbert: Existe um 
processo, que pode ser determinado por um 
número finito de operações, que encontre a 
raiz integral de um polinômio? 
 O que Hilbert perguntou foi se existia um 
algoritmo para resolver esta tarefa 
 Ainda outra interpretação, dada a linguagem 
D = {p | p é um polinômio com uma raiz integral}, o 
que Hilbert perguntou foi se D é decidível 
83 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
A Definição de Algoritmo (2) 
 Um polinômio é a soma de termos, onde cada termo é 
o produto de certas variáveis e uma constante 
chamada coeficiente 
 Exemplo: 
• 6𝑥3𝑦𝑧2 + 3𝑥𝑦2 − 𝑥3 − 10, é um polinômio de 4 termos 
sobre as variáveis x, y, z. 
 A raiz de um polinômio é uma atribuição de valores 
para suas variáveis de maneira que o valor do 
polinômio é zero (por exemplo, x =5, y = 3, e z=0) 
 A raiz é integral se todos valores atribuídos a variáveis 
são inteiros 
84 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
A Definição de Algoritmo (3) 
 Por simplicidade, considere uma versão mais 
simples do polinômio contendo apenas uma 
variável, como 4𝑥3 − 2𝑥2 + x − 7 
 Seja D1 = {p|p é um polinômio sobre x com uma 
raiz integral} 
 A MT M1 reconhece D1 
 M1= A entrada é um polinômio p sobre a variável x 
1. Avalia p com a variável x atribuída sucessivamente os 
valores 0, 1, -1, 2, -2, 3, -3, … Se a qualquer ponto o 
resultado do polinômio é 0, aceite 
85 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
A Definição de Algoritmo (4) 
 Se p possui uma raiz integra, M1 irá em algum 
momento encontra-la e aceitar 
 Caso contrário M1 irá executar para sempre 
 Conclusão: M1 reconhece D1 mas não a decide 
86 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
A Definição de Algoritmo (5) 
 Para o problema específico de encontar uma 
raiz integral de polinômios contendo apenas 
uma variável, é possível projetar uma MT 
decididora 
• É conhecido que a raiz do polinômio, se existir 
estar no intevalo ±𝑘
𝑐𝑚𝑎𝑥
𝑐1
, onde é o número de 
termos do polinômio, 𝑐𝑚𝑎𝑥 é o coeficiente com o 
maior valor absoluto, e c1 é o coeficiente do 
termo de maior ordem 
 Se uma raiz não é encontrada dentro destes 
limites, então a máquina rejeita 
 87 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Church-Turing Thesis 
 Conexão entre a noção informal de algoritmos 
e definição formal baseada no modelo de 
Máquinas de Turing 
• Máquinas de Turing capturam e representam 
precisamente a noção abstrata a respeito do que é 
um algoritmo e quais são seus limites 
88 
Noção intuitiva 
de algoritmos = 
Algoritmos de 
Máquinas de Turing