Parte 9

Prévia do material em texto

Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Texto base 
9 
 
Teoria da Computação 
Ana Paula Ferreira da Rocha 
Resumo 
 A máquina de Turing é um autômato cuja fita não tem tamanho máximo e pode ser usada 
simultaneamente como entrada, saída e dispositivo de memória. A computação com uma 
máquina de Turing demonstra a execução de problemas solucionáveis e as regras 
existentes para que não tenhamos um loop infinito. Observaremos que as extensões da 
máquina de Turing nos trazem modelos de máquina de Turing que podemos usar para 
cálculos e reconhecimento de linguagem e o poder computacional da gramática. 
Introdução 
 Abordaremos a computação com máquinas de Turing e as definições aceitas por 
ela, veremos as situações que levam ao loop infinito e a parada da máquina. As extensões 
da máquina de Turing irão abordar os modelos desta máquina universal e suas definições 
e seu poder computacional. 
 
 
9.1. Computação com máquinas de Turing 
Uma das abordagens do estudo das máquinas de Turing, de máquinas universais em geral, 
é como reconhecedores de linguagens, dispositivos capazes de determinar se uma dada 
palavra sobre o alfabeto de entrada pertence ou não a uma certa linguagem. 
 
Linguagem aceita, linguagem rejeitada linguagem loop 
Seja M = (∑, Q, 𝜹, q0, F, V, 𝜷, ⊛) uma máquina de Turing, então: 
• A linguagem aceita ou linguagem reconhecida por M, é representado por: 
 ACEITA(M) ou L(M) 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
É o conjunto de todas as palavras pertencentes a ∑* aceitas por M, a partir do estado 
inicial q0; 
• A linguagem rejeitada por M, é representada por: 
 REJEITA(M) 
É o conjunto de todas as palavras pertencentes a ∑* rejeitadas por M, a partir do estado 
inicial q0; 
• A linguagem loop de M, representada por: 
 LOOP(M) 
É o conjunto de todas as palavras pertencentes a ∑* para as quais M fica processando 
indefinidamente a partir do estado inicial q0. 
Supondo que ∑* é o conjunto universo, as seguintes afirmações são verdadeiras: 
 ACEITA(M) ∩ REJEITA(M) ∩ LOOP(M) = ∅ 
 ACEITA(M) ∪ REJEITA(M) ∪ LOOP(M) = ∑* 
 ~ACEITA(M) = REJITA(M) ∪ LOOP(M) 
 ~REJEITA(M) = ACEITA(M) ∪ LOOP(M) 
 ~LOOP(M) = ACEITA(M) ∪ REJITA(M) 
Cada máquina de Turing M definida sobre o alfabeto ∑ induz uma partição do conjunto 
de todas as palavras ∑* em três classes de equivalência: ACEITA(M), REJEITA(M) e 
LOOP(M) conforme ilustrado abaixo: 
 
Tabela 1.1 – Partição de ∑* induzida por uma máquina de Turing M 
ACEITA(M) REJEITA(M) LOOP(M) 
Fonte: Paulo Blauth Menezes, 2011. 
Sendo preciso, se um ou dois dos conjuntos forem vazios, então a partição induzida 
contém um ou dois conjuntos a menos, reforçando que uma classe de equivalência não 
pode ser vazia. 
 
Máquina de Turing: duplo balanceamento 
Considere a linguagem: 
 L = {anbn | n ≥ 0} 
A máquina de Turing: 
 M = ({a, b}, {q0, q1, q2, q3, q4}, 𝜹, q0, {q4}, {A, B}, 𝜷, ⊛) 
Sendo apresentado no diagrama abaixo, tal que: 
 ACEITA(M) = L e REJEITA(M) = ~L 
∑* 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
E, portanto, LOOP(M) = ∅ 
Figura 1.1 – Diagrama MT – duplo balanceamento 
 
Fonte: Paulo Blauth Menezes, 2011. 
Sendo 𝜹 demonstrada na tabela abaixo: 
 
Tabela 1.2 – Função programa MT – duplo balanceamento 
𝜹 ⊛ a b A B 𝜷 
q0 (q0, ⊛, D) (q1, A, D) (q3, B, D) (q4, 𝜷, D) 
q1 (q1, a, D) (q2, B, E) (q1, B, D) 
q2 (q2, a, E) (q0, A, D) (q2, B, E) 
q3 (q3, B, D) (q4, 𝜷, D) 
q4 
Fonte: Paulo Blauth Menezes, 2011. 
O algoritmo apresentado reconhece o primeiro símbolo a o qual é marcado como A, e 
movimenta a cabeça da fita à direita, procurando o b correspondente, o qual é marcado 
como B. este ciclo é repetido sucessivamente até identificar, para cada a o seu 
correspondente b. Adicionalmente o algoritmo garante que qualquer outra palavra que 
não esteja na forma anbn é rejeitada. 
Já a figura abaixo demonstra a sequência do processamento da máquina de Turing M para 
a entrada w = aabb: 
 
Figura 1.2 – Computação MT – duplo balanceamento para a entrada aabb 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
 
Fonte: Paulo Blauth Menezes, 2011. 
 
Máquina de Turing x algoritmo 
Em vários momentos, foi afirmado que a máquina de Turing é aceita como uma 
formalização do conceito de algoritmo, entretanto, também é usual considerar que o 
conceito de algoritmo corresponde a uma máquina de Turing que sempre para, para 
qualquer entrada. Nesse caso uma máquina que eventualmente fica processando 
indefinidamente em loop infinito não seria considerada um algoritmo. 
 
Você sabia? 
Vamos aprofundar o conhecimento sobre Máquinas de Turing? Assista ao vídeo 
Máquinas de Turing – com Prof. Kyller Costa Gorgônio. Disponível em: 
< https://www.youtube.com/watch?v=rPowO0EJTzU>. Acesso em: 09 mai. 2023. 
9.2. Extensões da Máquina de Turing 
Uma das razões para considerar a máquina de Turing como o mais geral dispositivo de 
computação é o fato de que todos os demais modelos de máquinas propostos bem como 
as diversas modificações da máquina de Turing possuem no máximo o mesmo poder 
computacional da máquina de Turing. 
 
Autômato com múltiplas pilhas 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
O poder computacional do autômato com duas pilhas é equivalente ao da máquina de 
Turing, adicionalmente um maior número de pilhas também não aumenta a capacidade 
computacional. A definição formal do autômato com duas pilhas e do autômato com 
múltiplas pilhas e a equivalência deles ao modelo da máquina de Turing é interessante 
observar que como são necessárias duas pilhas para que o autômato possua o mesmo 
poder computacional que uma máquina de Turing, pode-se afirmar que a estrutura de fita 
é mais expressiva do que a de pilha. 
 
Máquina de Turing não determinística 
A facilidade de não determinístico não aumenta o poder computacional da máquina de 
Turing. 
 
Máquina de Turing com fita infinita à esquerda e à direita 
A modificação da definição básica da máquina de Turing, permitindo que a fita seja 
infinita dos dois lados, não aumenta o seu poder computacional. Na realidade, a fita 
infinita à esquerda e à direita pode ser facilmente simulada por uma fita tradicional, na 
qual as células pares representam a parte direita da fita, e as ímpares a parte esquerda 
como demonstrado na figura abaixo: 
 
Figura 1.3 – Fita MT – simulação de uma fita infinita à esquerda e à direita 
 
Fonte: Paulo Blauth Menezes, 2011. 
 
Máquina de Turing com múltiplas fitas 
A máquina de Turing com múltiplas fitas possui k fitas infinitas à esquerda e à direita e 
k cabeças de fita, a função programa é como segue: 
• Dependendo do estado corrente da máquina e do símbolo lido em cada uma das 
fitas; 
• Grava um novo símbolo em cada uma das fitas; 
• Move cada uma das cabeças independentemente; 
• A máquina assume um único novo estado. 
Inicialmente a palavra de entrada é armazenada na primeira fita, ficando as demais com 
valor branco. 
 
Máquina de Turing multidimensional 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Neste modelo, a fita tradicional é substituída por uma estrutura do tipo arranjo k-
dimensional infinita em todas as 2k direções. 
 
Máquina de Turing com múltiplas cabeças 
A máquina de Turing com esta modificação possui k cabeças de leitura e gravação sobre 
a mesma fita, cada cabeça possui movimento independente assim o processamento 
depende do estado corrente e do símbolo lido em cada uma das cabeças. 
 
Combinações de modificações sobre a máquina de Turing 
A combinação de algumas ou todas as modificações apresentadas não aumenta o poder 
computacional da máquina de Turing. Por exemplo uma máquina de Turing não 
determinísticacom múltiplas fitas e múltiplas cabeças pode ser simulada por uma 
máquina de Turing tradicional. 
 
Você sabia? 
Vamos aprofundar o conhecimento sobre Máquina de Turing? Assista ao vídeo 
Extensões de Máquina de Turing. Disponível em: 
< https://www.youtube.com/watch?v=DI0Hf58YRDQ >. Acesso em: 27 abr. 2023. 
 
 
Considerações finais 
 Como vimos a máquina de Turing é um autômato cuja fita não possui tamanho 
máximo e pode ser usada simultaneamente como dispositivo de entrada, de saída e de 
memória. A computação com máquina de Turing nos demonstra a execução dos 
problemas solucionáveis e as regras existentes para que não tenhamos um loop infinito 
provocando a parada da computação. Observamos que as extensões da máquina de Turing 
nos trazem os modelos de máquina de Turing que podemos utilizar para as computações 
e o reconhecimento das linguagens e o poder computacional da gramática. 
 
 
Teoria da Computação 
 
Núcleo de Educação a Distância | Faculdade Impacta 
Referências 
DIVERIO, Tiarajú Asmuz; MENEZES, Paulo Blauth. Teoria da Computação: 
máquinas universais e computabilidade. Porto Alegre: Bookman, 2011. 
MENEZES, Paulo Blauth. Linguagens Formais e Autômatos. 6. ed. Porto Alegre: 
Bookman, 2011. 
SIPSER, Michael. Introdução à Teoria da Computação. 2. ed. São Paulo: Cengage 
Learning, 2007.