Máquinas de Turing e decidibilidade

Máquina de Turing

Estados finitos, fita ilimitada nos dois sentidos, cabeça que lê e escreve. $\Gamma\supset\Sigma$, branco $B\notin\Sigma$.

$$\delta(q,X)=(p,Y,D),\qquad D\in\{L,R\}.$$

Escreve $Y$, muda para $p$ e move a cabeça uma célula. A convenção usa finais sem saídas: parar num final aceita e parar fora de final rejeita; uma transição indefinida faz a máquina parar. Uma configuração $\alpha q\beta$ coloca o estado $q$ imediatamente antes da célula sob a cabeça. Quando $\delta(q,X)=(p,Y,R)$, então $\alpha qX\beta\vdash\alpha Yp\beta$. Quando o movimento é $D=L$ com $\alpha=\gamma A$, então $\gamma AqX\beta\vdash\gamma pAY\beta$.

Programar a fita

• Para $\{a^nb^n\mid n\ge0\}$: marca um $a$ com $X$ e o $b$ correspondente com $Y$, regressa ao $X$ e repete; no fim confirma que só restam $Y$. Cada ronda reduz os $a$ ativos, por isso a prova inclui a terminação.
• Para palíndromos: compara e risca os extremos; um centro isolado aceita sem procurar par.
• Para várias contagens: usa marcadores distintos por bloco e verifica primeiro o formato dos blocos.
• Para incrementar um binário: vai até ao fim e propaga o transporte à esquerda ($1\to0$; no primeiro $0$, escreve $1$ e termina; no branco à esquerda, escreve $1$).
• Num cálculo, indica sempre a região do resultado e a posição final da cabeça, não só a linguagem aceite.

Limite do simulador é inconclusivo: não prova que a máquina nunca pararia.

Modelos equivalentes

Várias fitas, fita unilateral, duas pilhas e TM não determinística: mesmo poder de reconhecimento, custos diferentes. Não determinismo simula-se por níveis, sem prender num ramo infinito. Tese de Church-Turing: procedimento efetivo equivale a TM; é tese, não teorema.

Reconhecimento e decisão

Máquina para $L$	Em $w\in L$	Em $w\notin L$
Reconhecedor	Termina e aceita	Rejeita ou corre para sempre
Decisor	Termina e aceita	Termina e rejeita

Se $L$ é decidível, então $L$ é reconhecível; a recíproca falha. Se $L$ e $\overline L$ são reconhecíveis, então $L$ é decidível: simula os dois reconhecedores alternando um passo de cada, pois um deles acabará por aceitar.

$A_{TM}$ (aceita?) e $HALT$ (para?): reconhecíveis e indecidíveis. Máquina universal simula $\langle M,w\rangle$.

Diagonalização e reduções

Sem decisor de paragem: se $H$ decidisse $HALT$, a máquina $D$ consultaria $H$ sobre $\langle M,\langle M\rangle\rangle$ e faria o contrário explícito: se $H$ disser que $M$ para, $D$ entra em ciclo infinito; se disser que não para, $D$ termina. Com a própria codificação, $D(\langle D\rangle)$ contradiz qualquer resposta de $H$.

• Redução $A\le_m B$: $f$ total computável com $x\in A\iff f(x)\in B$. Para $B$ indecidível, reduz $A$ indecidível a $B$.
• $HALT\le_m A_{TM}$: $N$ ignora a entrada, simula $M$ em $w$, aceita se parar. $M$ para em $w$ sse $\langle N,\varepsilon\rangle\in A_{TM}$.
• Com um limite fixo $t$ de passos, continua decidível perguntar se alguma entrada, ou se todas as entradas, fazem uma TM determinística ultrapassar $t$ passos. Nos primeiros $t$ movimentos, a cabeça não alcança além da posição $t+1$, por isso basta enumerar palavras até esse comprimento e simular cada representante. Este argumento usa o limite fixo e não decide a paragem sem limite.

Provas e construções completas.

Compactar um resultado

Para remover todos os $Y$ de uma entrada sobre $\{X,Y\}$ e juntar os $X$ num bloco contínuo $X^k$ desde a primeira célula: cada ronda completa desloca um $X$ para a primeira posição livre do prefixo; apagar um $Y$ durante o regresso impediria a escrita, por isso só a ronda completa conserva a quantidade de $X$. As varreduras percorrem uma região finita e a limpeza final apaga os $Y$ restantes. A máquina começa no estado $s$ na primeira célula e termina no final $f$ com a cabeça na célula 0; a tabela completa de cinco estados de trabalho está na lição.