Máquina de Turing - MT

Definição

• Máquina de Turing / MT = modelo matemático teórico de computação que representa o conceito de computabilidade
  • modelo teórico de computação que descreve um dispositivo abstrato capaz de manipular símbolos em uma fita infinita de acordo com um conjunto de regras
  • fundamental para definir o conceito de computabilidade
• modelo proposto por Alan Turing em 1936 para capturar o conceito de algoritmo ou procedimento efetivo
• é a fundação da Teoria da Computação, equivalente ao que computadores digitais podem computar, ignorando limitações práticas de tempo e memória
• supera os autômatos finitos (AFD/AFN) e os autômatos com pilha (PDA), pois pode manipular quantidades arbitrárias de informação com memória não limitada - fita infinita
• a fita é infinita para a esquerda e para a direita

Forma formal

• MT = 7-tupla M = (Q,Σ,Γ,δ,q_0,q_aceita,q_rejeita), onde
  • Q = conjunto finito de estados
  • Σ - Sigma = alfabeto de entrada - não contém o símbolo branco
  • Γ ⊇ Σ - Gamma = alfabeto da fita - inclui o símbolo branco
  • δ - delta = função de transição Q × Γ → Q × Γ × {L, R}
  • q_0 = estado inicial
  • q_aceita = estado de aceitação
  • q_rejeita = estado de rejeição

Funcionamento da MT

1. A fita contém a entrada - símbolos de Σ - e é infinita para ambos os lados
   • ou apenas à direita, dependendo da variante
2. A cabeça de leitura/escrita começa em q_0​ e na primeira célula da fita
3. Em cada passo, a máquina
   • lê o símbolo da fita a ∈ Γ
   • aplica δ(q,a) = (q′,b,D) = troca o estado, escreve b, e move para esquerda (L) ou direita (R)

4. Termina se atinge um estado de aceitação q_aceita ou um estado de aceitação q_rejeita - ou pode entrar em loop infinito

5. a máquina

   1. lê um símbolo da fita
   2. escreve um novo símbolo
   3. move a cabeça para esquerda (L) ou direita (R)
   4. muda de estado
   5. continua até atingir um estado de aceitação ou rejeição - ou entrar em loop

Importância

• a MT define o conceito de linguagens recursivamente enumeráveis e decidíveis
• tudo o que um computador moderno pode fazer é teoricamente possível por uma Máquina de Turing
• é o modelo usado para discutir limites da computação
  • o que é possível computar, o que não é
• a MT permite distinguir diferentes classes de linguagens
  • linguagens decidíveis / recursivas
    • há uma MT que sempre para e aceita ou rejeita
    • a máquina é um decisor
  • linguagens recursivamente enumeráveis
    • há uma MT que aceita as cadeias da linguagem, mas pode não parar em cadeias fora dela
    • a máquina é um reconhecedor

ou seja - toda linguagem decidível é RE, mas nem toda RE é decidível.

Propriedades Fundamentais

• a MT é Turing-completa
  • pode simular qualquer algoritmo computável
• a fita age como uma memória RAM ilimitada
  • linear, mas suficiente
• a função de transição é local
  • a máquina não vê a fita inteira, só o símbolo atual

Tipos de Máquina de Turing

• NTM - Não-determinística
  • pode haver múltiplas transições para o mesmo par
• apesar das diferenças, DTM e NTM têm o mesmo poder computacional

1. Determinística - DTM

• a função δ é totalmente definida para cada (q,a)
• só existe uma única transição possível para cada situação
  • para cada par (estado, símbolo)

2. Não Determinística - NTM

• A função δ pode dar várias possibilidades de transição
  • pode haver múltiplas transições para o mesmo par (estado, símbolo)
• Pode explorar todas as possibilidades simultaneamente - modelo teórico
• Apesar das diferenças, DTM e NTM têm o mesmo poder computacional - mas não necessariamente o mesmo tempo
  • DTM ≡ NTM

Importante - embora NTMs não sejam fisicamente construíveis, ajudam a entender limites de complexidade - como em NP vs P.

Exemplo de linguagem reconhecida

• L = {w#w ∣ w ∈ {0,1}∗}
  • strings que contêm uma palavra seguida de # e a mesma palavra novamente
  • uma MT pode verificar isso comparando os dois lados
• Uma MT pode
  1. Marcar o primeiro símbolo à esquerda
  2. Mover até o #, depois até o final da cadeia
  3. Comparar símbolo a símbolo (voltando e indo), marcando os pares correspondentes
  4. Aceitar se todos coincidirem, rejeitar se encontrar desigualdade

Essa linguagem não é regular nem livre de contexto, mas é reconhecida por uma MT. Isso mostra a capacidade superior do modelo.

Problemas Decidíveis x Indecidíveis

• Há problemas que nenhuma MT pode decidir. Exemplo clássico:
  • Problema da Parada = dado uma MT M e entrada w, ela para ou entra em loop?
  • Teorema = esse problema é indecidível
• essa limitação define os limites fundamentais da computação
  • existem funções bem definidas que nenhuma máquina consegue calcular para todas as entradas

Extensões do modelo

• embora o modelo básico seja extremamente simples, ele pode ser estendido sem ganho de poder computacional, apenas em conveniência
  • Fitas múltiplas
  • Cabeças múltiplas
  • Alfabeto maior
  • Movimento para ficar parado (S)
  • Acesso bidirecional à fita
• Todos esses modelos são equivalentes ao original

Tese de Church-Turing

O que é

• Tese de Church-Turing / Tese de Turing = é uma hipótese filosófica/formal que afirma:

“Tudo o que é computável de forma efetiva pode ser computado por uma Máquina de Turing.”

• em outras palavras
• qualquer algoritmo que possa ser descrito - por um ser humano, programa ou qualquer sistema lógico - pode ser implementado por uma MT.
• Computação ≡ Computação por Máquina de Turing

Origem

• Alonzo Church e Alan Turing, em 1936, chegaram independentemente a modelos formais diferentes com o mesmo poder computacional
  • Church usou o λ-cálculo
  • Turing usou as Máquinas de Turing
• Isso levou à conclusão de que havia um único conceito robusto de função computável.

Status atual

• não é um teorema, porque não há uma definição formal do que é "efetivamente computável" fora desses modelos
• mas até hoje, nenhum algoritmo prático foi descoberto que não possa ser simulado por uma MT
• serve como fundamento da Ciência da Computação teórica

Computabilidade

• computabilidade = investiga quais problemas podem ser resolvidos por um algoritmo
  • classifica problemas entre solúveis ou não solúveis
• problema é
  • computável = se existe uma Máquina de Turing que pode resolvê-lo em um número finito de passos
• Algumas questões são não computáveis
  • problema da parada = prova que não há algoritmo geral para decidir se outro algoritmo qualquer vai parar ou rodar para sempre

Complexidade

• complexidade (computacional) = estuda a eficiência dos algoritmos, analisando quanto tempo e quanta memória são necessários para resolver um problema
  • não o que é computável, mas o que é computável eficientemente
• classifica problemas entre fáceis ou difíceis
  • Ordenação de arrays – fácil
  • Escalonamento de tarefas (combinatória) – difícil
  • O que faz um problema de computador ser mais difícil que outro?
    • ainda não há essa resposta
• classificação de problemas
  • P (Tempo polinomial) = Problemas resolvíveis de forma eficiente
  • NP (Não-determinístico polinomial) = Problemas cuja solução pode ser verificada rapidamente, mas pode não ser fácil de encontrar
  • NP-completo = Problemas difíceis dentro de NP, para os quais, se houver uma solução eficiente, todos os problemas em NP também teriam

Problemas NP e o universo da complexidade

Classes P e NP

Classe	Significado
P	Problemas que podem ser resolvidos em tempo polinomial por uma MT determinística. Exemplos - ordenação, busca binária, soma de inteiros
NP	Problemas cujas soluções podem ser verificadas em tempo polinomial por uma MT determinística. Exemplos - Sudoku, SAT, Caixeiro Viajante

NP - Nondeterministic Polynomial time

• pensar em uma NTM (Máquina de Turing Não Determinística) que "chuta" uma solução e verifica rapidamente
• em problemas NP, não se sabe como encontrar a resposta rapidamente, mas se alguém der uma resposta, é possível checar rápido

P vs NP

• A maior pergunta em aberto da computação teórica - P = NP ?
• ou seja
  • será que todo problema cuja solução pode ser verificada rapidamente também pode ser resolvido rapidamente?
  • se sim, muitos problemas considerados intratáveis se tornariam solucionáveis
    • criptografia, otimização, IA
• atualmente
  • não se sabe a resposta
  • a maioria dos cientistas acredita que P ≠ NP
  • provar isso vale US$ 1 milhão - Millennium Prize Problem

Exemplo de problemas em NP

• todos esses problemas têm soluções verificáveis em tempo polinomial, mas nenhum algoritmo eficiente é conhecido para resolvê-los (sem força bruta)
  • SAT (satisfatibilidade booleana) — problema original NP-completo
  • Caixeiro viajante (TSP)
  • Coloração de grafos
  • Sudoku e diversos puzzles
  • Problemas criptográficos (RSA, ECC) — a base da segurança digital atual

NP-completos e NP-difíceis

• NP-completos = problemas mais difíceis de NP
  • Se resolver um eficientemente, todos os problemas de NP podem ser resolvidos eficientemente.
• NP-difíceis = problemas tão difíceis quanto os NP-completos, mas podem não estar em NP
  • ou seja, talvez nem seja possível verificar rapidamente a solução

Relação com Church-Turing

• Tese de Church-Turing = trata do que é possível computar
• A análise de P, NP e demais classes = trata do que é viável computar
  • eficiência, escalabilidade, tempo

Tabela Resumo

Conceito	Tema	Pergunta
Church-Turing	Computabilidade	“Isso é possível de ser computado?”
P vs NP	Complexidade	“Isso pode ser computado rapidamente?”

Síntese

• A Máquina de Turing
  • é a base do que se entende por algoritmo
  • define os conceitos de decidibilidade e computabilidade
  • mostra que há problemas insolúveis mesmo com infinitos recursos
  • serve como uma ferramenta conceitual poderosa na análise de linguagens, lógica e limites da IA

Exercícios

Afirmações

1. Toda linguagem reconhecida por uma Máquina de Turing é uma linguagem regular.
2. A fita de uma Máquina de Turing é infinita apenas para a direita.
3. A Máquina de Turing pode simular qualquer computador moderno.
4. Uma Máquina de Turing não-determinística é mais poderosa do que uma Máquina de Turing determinística.
5. Toda linguagem decidível é também recursivamente enumerável.
6. Uma Máquina de Turing pode entrar em loop e nunca parar.
7. Uma Máquina de Turing pode ter múltiplas cabeças de leitura e escrita.
8. Toda linguagem livre de contexto pode ser reconhecida por uma Máquina de Turing.
9. A função de transição de uma MT determina o símbolo a ser lido no próximo passo.
10. A linguagem {ww | w ∈ {0,1}*} pode ser reconhecida por uma Máquina de Turing.
11. A Máquina de Turing rejeita uma entrada apenas quando atinge explicitamente o estado de rejeição.
12. Se uma linguagem é aceita por uma Máquina de Turing, então existe uma GLC que também a aceita.
13. Toda Máquina de Turing pode ser convertida em um autômato finito equivalente.
14. Uma linguagem pode ser reconhecida por uma MT mesmo que a máquina nunca pare para certas entradas.
15. O símbolo branco (blank) é parte obrigatória do alfabeto de entrada.
16. Toda linguagem decidível pode ser reconhecida por uma MT que sempre termina sua execução.
17. O número de estados de uma Máquina de Turing é sempre infinito.
18. A Máquina de Turing pode modificar a fita, enquanto autômatos finitos apenas leem a entrada.
19. Uma linguagem aceita por uma MT é sempre finita.
20. Se uma MT não encontra uma transição definida para uma situação (estado, símbolo), ela para automaticamente.

Gabarito

• 1. Toda linguagem reconhecida por uma Máquina de Turing é uma linguagem regular.
  • Resposta: ❌ Falso
  • Justificativa: As linguagens regulares são um subconjunto estrito das linguagens reconhecíveis por uma MT. Há muitas linguagens reconhecidas por MTs que não são regulares
    • exemplo - {aⁿbⁿ | n ≥ 0}
• 2. A fita de uma Máquina de Turing é infinita apenas para a direita.
  • Resposta: ❌ Falso
  • Justificativa: A fita de uma MT é geralmente considerada infinita em ambas as direções (esquerda e direita). Algumas variações usam fita infinita para a direita apenas, mas isso não altera o poder computacional.
• 3. A Máquina de Turing pode simular qualquer computador moderno.
  • Resposta: ✅ Verdadeiro
  • Justificativa: Pelo modelo de Turing-completude, qualquer algoritmo que pode ser executado por um computador moderno pode ser simulado por uma MT (mesmo que ineficientemente).
• 4. Uma Máquina de Turing não-determinística é mais poderosa do que uma Máquina de Turing determinística.
  • Resposta: ❌ Falso
  • Justificativa: Em termos de poder computacional (quais linguagens podem reconhecer), DTM e NTM são equivalentes. O que muda é a eficiência, não a capacidade.
• 5. Toda linguagem decidível é também recursivamente enumerável.
  • Resposta: ✅ Verdadeiro
  • Justificativa: Linguagens decidíveis (ou recursivas) são aquelas para as quais uma MT sempre termina e dá uma resposta (aceita ou rejeita). Essas também são RE, pois uma MT pode listá-las.
• 6. Uma Máquina de Turing pode entrar em loop e nunca parar.
  • Resposta: ✅ Verdadeiro
  • Justificativa: Isso é característico das linguagens recursivamente enumeráveis. Se a palavra não pertence à linguagem, a MT pode rodar infinitamente e nunca rejeitar.
• 7. Uma Máquina de Turing pode ter múltiplas cabeças de leitura e escrita.
  • Resposta: ✅ Verdadeiro
  • Justificativa: Existem variações com múltiplas cabeças, múltiplas fitas, etc. Todas são equivalentes em poder à MT padrão, embora possam ser mais eficientes.
• 8. Toda linguagem livre de contexto pode ser reconhecida por uma Máquina de Turing.
  • Resposta: ✅ Verdadeiro
  • Justificativa: Linguagens livres de contexto ⊆ linguagens recursivas ⊆ linguagens RE. Assim, uma MT pode reconhecer qualquer linguagem CFL.
• 9. A função de transição de uma MT determina o símbolo a ser lido no próximo passo.
  • Resposta: ❌ Falso
  • Justificativa: A função de transição atua com base no símbolo atual lido e no estado atual. Ela não escolhe o símbolo seguinte, ela move a cabeça para ler o próximo símbolo.
• 10. A linguagem {ww | w ∈ {0,1}*} pode ser reconhecida por uma Máquina de Turing.
  • Resposta: ✅ Verdadeiro
  • Justificativa: Essa linguagem não é regular nem livre de contexto, mas é reconhecível por uma MT (e, de fato, decidível). Ela exige comparar duas metades iguais, o que uma MT pode fazer com marcações e deslocamentos.
• 11. A Máquina de Turing rejeita uma entrada apenas quando atinge explicitamente o estado de rejeição.
  • Resposta: ❌ Falso
  • Justificativa: Uma MT pode rejeitar uma entrada explícita ou implicitamente. Se ela entra em loop (nunca aceita nem rejeita), a entrada também é considerada rejeitada no contexto da linguagem reconhecível, mas não decidível. Apenas linguagens decidíveis garantem parada e resposta clara.
• 12. Se uma linguagem é aceita por uma Máquina de Turing, então existe uma GLC que também a aceita.
  • Resposta: ❌ Falso
  • Justificativa: Há linguagens reconhecíveis por MTs que não são livres de contexto.
    • Exemplo - {aⁿbⁿcⁿ | n ≥ 0} não pode ser gerada por GLC, mas é reconhecida por MT.
• 13. Toda Máquina de Turing pode ser convertida em um autômato finito equivalente.
  • Resposta: ❌ Falso
  • Justificativa: O autômato finito tem menos poder computacional. Existem muitas linguagens que um AFD nunca pode reconhecer, mas uma MT pode.
• 14. Uma linguagem pode ser reconhecida por uma MT mesmo que a máquina nunca pare para certas entradas.
  • Resposta: ✅ Verdadeiro
  • Justificativa: Isso caracteriza as linguagens recursivamente enumeráveis. A MT aceita a palavra se entra em estado de aceitação; se não pertence, pode simplesmente não parar nunca.
• 15. O símbolo branco (blank) é parte obrigatória do alfabeto de entrada.
  • Resposta: ❌ Falso
  • Justificativa: O símbolo branco □ (ou espaço em branco) é reservado apenas no alfabeto da fita (Γ) e não faz parte do alfabeto de entrada (Σ), por definição.
• 16. Toda linguagem decidível pode ser reconhecida por uma MT que sempre termina sua execução.
  • Resposta: ✅ Verdadeiro
  • Justificativa: Linguagens decidíveis (ou recursivas) são aquelas para as quais existe uma MT que aceita ou rejeita e sempre termina em qualquer entrada.
• 17. O número de estados de uma Máquina de Turing é sempre infinito.
  • Resposta: ❌ Falso
  • Justificativa: O número de estados (Q) é sempre finito. O que é potencialmente infinito é o tamanho da fita, não o número de estados.
• 18. A Máquina de Turing pode modificar a fita, enquanto autômatos finitos apenas leem a entrada.
  • Resposta: ✅ Verdadeiro
  • Justificativa: A capacidade de ler, escrever e mover a cabeça em duas direções é o que torna a MT mais poderosa. AFDs e APs apenas leem.
• 19. Uma linguagem aceita por uma MT é sempre finita.
  • Resposta: ❌ Falso
  • Justificativa: MTs podem aceitar linguagens finitas, infinitas, decidíveis ou apenas reconhecíveis.
    • Exemplo - a linguagem {w#w | w ∈ {0,1}*} é infinita e reconhecida por uma MT.
• 20. Se uma MT não encontra uma transição definida para uma situação (estado, símbolo), ela para automaticamente.
  • Resposta: ✅ Verdadeiro
  • Justificativa: Isso é chamado de parada por bloqueio. Se a função de transição δ não está definida para um dado par (q, a), a máquina para, o que pode significar rejeição implícita ou erro, dependendo do contexto.

Múltipla Escolha

1. Qual das opções abaixo descreve corretamente uma linguagem recursivamente enumerável (RE)?

A) Pode ser aceita por um AFD.
B) Existe uma MT que a aceita e sempre termina.
C) Existe uma MT que a aceita, mas pode não parar em algumas entradas.
D) Pode ser gerada por uma gramática regular.
E) Pode ser decidida usando pilha.

2. Seja o problema:

“Dado um programa P e uma entrada w, determine se P aceita w.”

Esse problema é:

A) Decidível
B) Semidecidível
C) Não reconhecível
D) Determinístico
E) Regular

3. Uma linguagem L é decidível se e somente se:

A) Existe uma GLC que gera L.
B) Existe um PDA que reconhece L.
C) Existe uma MT que aceita L e nunca entra em loop.
D) L é subconjunto de uma linguagem regular.
E) A função de transição de L é injetiva.

4. Qual das linguagens abaixo não é decidível?

A) L = { (P, w) | P é um programa em C que imprime “Olá” na entrada w }
B) L = { w ∈ {0,1}* | w contém número par de zeros }
C) L = { w#w | w ∈ {0,1}* }
D) L = { aⁿbⁿ | n ≥ 0 }
E) L = { ε }

5. Qual afirmação está correta?

A) Toda linguagem RE é regular.
B) Toda linguagem decidível é livre de contexto.
C) Existe linguagem que não é reconhecível por nenhuma MT.
D) Toda linguagem gerada por uma GLC é indecidível.
E) Nenhuma MT pode simular outra MT.

6. Sobre os problemas indecidíveis, qual é o método mais comum para prová-los?

A) Construir uma GLC equivalente.
B) Fazer um loop infinito.
C) Usar uma função injetora.
D) Redução de um problema indecidível conhecido.
E) Demonstrar que a linguagem é infinita.

Gabarito

1. C - Justificativa: Uma linguagem RE é aquela para a qual existe uma MT que aceita as cadeias da linguagem, mas pode nunca parar para cadeias que não pertencem a ela.
2. B - Justificativa: Esse é o famoso problema da parada. É RE (existe uma MT que aceita se P aceita w), mas não é decidível (não existe uma MT que sempre responde sim ou não).
3. C - Justificativa: Uma linguagem decidível é aquela para a qual existe uma MT que sempre termina com aceitação ou rejeição — ou seja, não entra em loop.
4. A - Justificativa: Essa linguagem exige analisar comportamento arbitrário de programas, o que nos leva à indecidibilidade por uma redução ao problema da parada.
5. C - Justificativa: Sim — o conjunto de linguagens possíveis é não enumerável, enquanto o conjunto de MTs é enumerável. Portanto, existem linguagens que não são nem reconhecíveis por MT alguma.
6. D - Justificativa: O método clássico de prova de indecidibilidade é por redução: mostrar que, se esse novo problema fosse decidível, então um problema indecidível conhecido também seria — o que é absurdo.

---