# Máquinas de Turing e decidibilidade

O modelo de Turing, decidível contra reconhecível e a indedicibilidade da paragem.

Página: https://resumos.rgo.pt/cadeiras/tc/turing-decidibilidade/

Uma **máquina de Turing** (TM) é um autómato finito com uma fita infinita onde pode ler, escrever e andar para trás e para a frente. É o modelo geral de computação: tudo o que um computador faz, uma TM faz. E, surpreendentemente, há problemas que nem ela resolve. Esta página apresenta o modelo, distingue decidível de reconhecível e prova que o problema da paragem é indecidível.

## O modelo: fita, cabeça, estados

Uma TM tem: uma **fita** infinita para a direita (ou ambos os lados), dividida em células com símbolos de um alfabeto de fita; uma **cabeça** sobre uma célula; um **estado** de um conjunto finito; e uma **função de transição** que, dado estado e símbolo lido, devolve novo estado, símbolo a escrever e movimento ($E$ esquerda, $D$ direita). Começa no estado inicial com a entrada na fita e o resto em branco ($\sqcup$). **Para** quando atinge um estado de aceitação ou rejeição; se nunca atingir, corre para sempre.

Exemplo: TM que decide $\{0^n 1^n\}$. Estratégia: em cada ronda, risca um $0$ do início e um $1$ do fim, repetindo até não restar nada (aceita) ou encontrar desordem (rejeita). Com $X$ a marcar riscados:

```
Ronda (começa na extremidade esquerda):
  varre à direita até ao primeiro 0 não riscado; risca-o (escreve X)
  continua à direita até ao primeiro 1 não riscado; risca-o
  volta à esquerda até ao X mais à esquerda
Aceita quando já não há 0 nem 1 por riscar; rejeita se vir um 1 antes
de riscar todos os 0 (ordem trocada) ou se sobrar um 0 sem um 1.
```

A diferença para o PDA: a cabeça volta atrás e relê, por isso conta duas vezes sem pilha. A fita é memória ilimitada com acesso arbitrário.

## A tabela de transições

A descrição acima vira uma tabela estado/símbolo. Para a TM do exemplo, com estados $q_0$ (procura um $0$ por riscar), $q_1$ (procura um $1$ por riscar) e $q_2$ (volta à esquerda), mais aceitação e rejeição:

```
q0: lê 0 -> escreve X, vai D, fica q1    (risca o 0 mais à esquerda)
q0: lê X -> mantém X, vai D, fica q0     (salta riscados)
q0: lê vazio -> aceita                    (já não há nada por riscar)
q0: lê 1 -> rejeita                       (um 1 onde devia haver 0)
q1: lê 0 ou X -> mantém, vai D, fica q1  (salta até aos uns)
q1: lê 1 -> escreve X, vai E, fica q2    (risca o 1 mais à esquerda)
q1: lê vazio -> rejeita                   (faltou um 1)
q2: lê 0, 1 ou X -> mantém, vai E, fica q2 (volta atrás)
q2: lê X após voltar -> mantém, vai D, fica q0 (nova ronda)
```

Cada linha é total nos casos alcançáveis: de $q_0$ só se chega a símbolos $0$, $X$, $1$ ou vazio, e cada um tem destino. O desenho mostra a primeira riscadela em $0011$: o $0$ inicial vira $X$ e o resto fica igual.

![Fita com 0011 antes e com X011 depois de riscar o primeiro zero.](https://resumos.rgo.pt/cadeiras/tc/turing-decidibilidade/figura-1.svg)

A mesma ronda em código, com a fita trocada por uma lista e a ordem verificada no fim de cada ronda:

```python
def decide(w):
    fita = list(w)
    while "0" in fita or "1" in fita:
        if "0" in fita:
            fita[fita.index("0")] = "X"
            if "1" in fita:
                fita[fita.index("1")] = "X"
            else:
                return False
        else:
            return False
        resto = [s for s in fita if s in "01"]
        if resto != sorted(resto):
            return False
    return True

for w in ["0011", "010", ""]:
    print(w or "epsilon", "aceite" if decide(w) else "rejeitada")
```

O programa imprime `aceite`, `rejeitada` e `aceite`: `0011` risca aos pares por ordem, `010` falha na verificação de ordem (o `0` aparece depois do `1`), e a palavra vazia não entra no ciclo.

## Decidível contra reconhecível

*   $L$ é **reconhecível** (recursivamente enumerável) se existe uma TM que aceita todas as palavras de $L$ e nunca aceita palavras fora (mas pode correr para sempre nas de fora).
*   $L$ é **decidível** se existe uma TM que **para sempre**, aceitando as palavras de $L$ e rejeitando as de fora. A TM é então um **decisor**.

Toda a linguagem decidível é reconhecível, mas o contrário falha. Intuição: reconhecer é “dizer sim quando sim”; decidir é “responder sempre”. Para linguagens regulares e livres de contexto, pertença é decidível (simulação e CYK). O salto da cadeira é que isto nem sempre é possível.

Pertença num DFA é decidível: simula a palavra e responde sempre, como o simulador da página sobre [autómatos finitos](https://resumos.rgo.pt/cadeiras/tc/turing-decidibilidade/automatos-finitos/). O algoritmo para em no máximo $|w|$ passos, com sim ou não.

O problema da paragem é reconhecível mas não decidível: simular $M$ em $w$ e aceitar se parar aceita exatamente os casos sim, mas corre para sempre nos casos não. A prova abaixo mostra que nenhum decisor faz melhor.

## O problema da paragem é indecidível

O **problema da paragem** ($HALT$): dada uma TM $M$ e uma entrada $w$, será que $M$ para em $w$? Prova por diagonalização de que nenhum decisor resolve isto.

1.  **Supõe** que existe um decisor $H$: $H$ recebe $\langle M, w\rangle$ (uma codificação de $M$ e $w$), para sempre e aceita se $M$ para em $w$, rejeita se $M$ corre para sempre em $w$.
2.  **Constrói a máquina contrária** $D$. $D$ recebe $\langle M\rangle$ (a descrição de uma máquina) e faz: corre $H$ em $\langle M, \langle M\rangle\rangle$, ou seja, pergunta “será que $M$ para quando recebe a sua própria descrição?”. Depois faz o contrário: se $H$ aceita, $D$ entra em ciclo infinito; se $H$ rejeita, $D$ para.
3.  **Aplica $D$ a si própria.** Pergunta: $D$ para em $\langle D\rangle$? Há dois casos, e ambos rebentam:
    *   Se $D$ para em $\langle D\rangle$, então $H$ em $\langle D, \langle D\rangle\rangle$ aceita, logo $D$ em $\langle D\rangle$ entra em ciclo, ou seja, não para. Contradição.
    *   Se $D$ não para em $\langle D\rangle$, então $H$ rejeita, logo $D$ para. Contradição.
4.  **Conclui.** Os dois casos possíveis são impossíveis, por isso a suposição é falsa: o decisor $H$ não existe. $HALT$ é indecidível.

Repara que a prova não usa nada sobre como $H$ funciona por dentro, só o seu comportamento observável. É uma diagonalização: $D$ foi construída para diferir de cada máquina na diagonal “máquina aplicada a si própria”. Se treinaste [provas com condicionais](https://resumos.rgo.pt/cadeiras/md/provas-proposicionais/), revê a estrutura: é uma prova por contradição com análise de casos, onde cada caso nega a sua própria hipótese.

Reconhecível mas não decidível: o próprio HALT

$HALT$ é reconhecível: uma TM que simula $M$ em $w$ e aceita se a simulação parar aceita exatamente os pares onde $M$ para. O que falta é parar nos pares onde $M$ não para, e a prova acima mostra que nenhuma TM consegue isso sempre. Por isso $HALT$ separa as duas classes.

## Para saber mais

Duas introduções em vídeo (em inglês) e simuladores para experimentar:

[Vídeo: Máquinas de Turing explicadas, Computerphile](https://www.youtube.com/watch?v=dNRDvLACg5Q)

A miniatura vem do YouTube. O vídeo só carrega quando clicas. [Abrir no YouTube](https://www.youtube.com/watch?v=dNRDvLACg5Q)

[Vídeo: Turing e o problema da paragem, Computerphile](https://www.youtube.com/watch?v=macM_MtS_w4)

A miniatura vem do YouTube. O vídeo só carrega quando clicas. [Abrir no YouTube](https://www.youtube.com/watch?v=macM_MtS_w4)

*   [Entrada sobre máquinas de Turing](https://plato.stanford.edu/entries/turing-machine/) na Stanford Encyclopedia, com definições e variantes.
*   [Entrada sobre computabilidade](https://plato.stanford.edu/entries/computability/) na Stanford Encyclopedia, com a tese de Church Turing.
*   [turingmachine.io](https://turingmachine.io/), simulador visual de máquinas de Turing no navegador, para correres pequenos programas.

## Para levar para a próxima página

Há uma fronteira absoluta: problemas que nenhum algoritmo resolve. Mas entre os decidíveis há outra fronteira, prática: problemas decidíveis mas intratáveis. É a [complexidade](https://resumos.rgo.pt/cadeiras/tc/turing-decidibilidade/complexidade/): P contra NP.