Máquinas de Turing e decidibilidade

Uma máquina de Turing pode voltar a uma célula da fita e alterar o símbolo que lá guardou. Para comparar dois blocos, marca um símbolo em cada um e regressa ao primeiro bloco para repetir. A cabeça indica a célula que a máquina lê em cada passo.

Essa memória permite reler dados que uma pilha só alcança retirando o que está no topo. Vamos seguir a comparação de $a$ e $b$ e justificar também que a máquina termina.

O modelo: fita, cabeça, estados

Usa $M=(Q,\Sigma,\Gamma,\delta,q_0,B,F)$, com alfabeto de entrada $\Sigma$, alfabeto de fita $\Gamma\supseteq\Sigma$ e branco $B\in\Gamma\setminus\Sigma$. A fita é ilimitada nos dois sentidos. No início contém a entrada numa sequência de células, com brancos no resto, e a cabeça está na primeira célula da entrada.

A transição parcial

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

manda escrever $Y$ no lugar de $X$, mudar para $p$ e mover a cabeça uma célula à esquerda ou à direita. Uma transição não definida termina a computação. Adota finais sem saídas: parar num final aceita; parar fora de $F$ rejeita. Aceitar não exige consumir a entrada toda: se a máquina entra num final a meio da fita, a computação termina ali com aceitação.

Outra convenção comum usa estados explícitos de aceitação e rejeição; ambas descrevem os mesmos algoritmos.

Uma configuração $\alpha q\beta$ coloca $q$ imediatamente antes da célula sob a cabeça. Em $01q_2X1$, a fita representada é $01X1$ e a cabeça lê $X$. Brancos fora da região mostrada ficam implícitos.

Se $\delta(q,X)=(p,Y,R)$, então $\alpha qX\beta\vdash\alpha Yp\beta$. Se o movimento é à esquerda e $\alpha=\gamma A$, então $\gamma AqX\beta\vdash\gamma pAY\beta$. Acrescenta um branco à representação quando a cabeça sai da parte escrita.

O vídeo de Rodrigo Dias apresenta o modelo de máquina de Turing:

Abrir no YouTube

Uma máquina que decide aⁿbⁿ

A máquina marca um $a$ com $X$ e um $b$ correspondente com $Y$, voltando ao início de cada ronda. Quando já não encontra $a$, verifica que só restam $Y$ e branco.

Os estados são $q_0$ para escolher o próximo $a$, $q_1$ para procurar um $b$, $q_2$ para regressar ao marcador $X$ da ronda, $q_3$ para verificar o fim, e $q_f$ final.

Estado	$a$	$b$	$X$	$Y$	$B$
$q_0$	$(q_1,X,R)$	Rejeita	Rejeita	$(q_3,Y,R)$	Aceita
$q_1$	$(q_1,a,R)$	$(q_2,Y,L)$	Rejeita	$(q_1,Y,R)$	Rejeita
$q_2$	$(q_2,a,L)$	Rejeita	$(q_0,X,R)$	$(q_2,Y,L)$	Rejeita
$q_3$	Rejeita	Rejeita	Rejeita	$(q_3,Y,R)$	Aceita

As células ‘Aceita’ podem ser implementadas por $(q_f,B,R)$ e as de rejeição por transição não definida. Nas entradas de aceitação da tabela só lês branco, por isso não apagas um símbolo da entrada. A máquina aceita também $\varepsilon$.

Para $aabb$, os passos são:

$$\begin{aligned} q_0aabb&\vdash Xq_1abb\vdash Xaq_1bb\\ &\vdash Xq_2aYb\vdash q_2XaYb\\ &\vdash Xq_0aYb\vdash XXq_1Yb\\ &\vdash XXYq_1b\vdash XXq_2YY\\ &\vdash Xq_2XYY\vdash XXq_0YY\\ &\vdash XXYq_3Y\vdash XXYYq_3B\\ &\vdash XXYYBq_fB. \end{aligned}$$

Em $aab$, a segunda procura de $b$ chega a branco e rejeita. Em $abab$, a verificação final encontra um $a$ depois de $Y$ e rejeita, apesar de as contagens globais coincidirem.

A cada ronda, os marcadores $X$ ficam no início, e $q_2$ regressa ao $X$ acabado de criar. O número de $a$ ainda não marcados diminui. Cada procura percorre uma região finita, pelo que a máquina termina em todas as entradas. A prova de terminação tem de acompanhar a prova de aceitação correta.

Editar e seguir a fita

Executa a máquina de marcação com aabb e avança passo a passo. O estado inicial é a configuração antes da primeira transição; em cada passo, a máquina escreve, muda de estado e desloca a cabeça. Compara depois aab e abab. No editor, podes alterar os estados, os alfabetos e cada transição, ou criar outra máquina.

O simulador usa a convenção desta lição, com uma fita bilateral e finais sem saídas. O exemplo de incremento lê um binário, propaga o transporte e aceita quando acaba de escrever o resultado; a entrada vazia produz 1. O exemplo que percorre brancos não tem estado final e continua a deslocar-se. Ao atingir um limite do simulador, o resultado é inconclusivo. Isso não demonstra que uma máquina arbitrária nunca pararia.

Uma construção mínima com transições explícitas

Para decidir palavras binárias que terminam em $0$, com contrato explícito: aceita se o último símbolo é $0$; rejeita se termina em $1$ ou se a entrada é vazia. Usa $q_0$ para varrer até ao branco, $q_1$ para voltar uma célula e $q_f$ final:

• $\delta(q_0,0)=(q_0,0,R)$, $\delta(q_0,1)=(q_0,1,R)$, $\delta(q_0,B)=(q_1,B,L)$;
• $\delta(q_1,0)=(q_f,0,R)$; $\delta(q_1,1)$ e $\delta(q_1,B)$ ficam indefinidas para rejeitar.

Para $10$, com a convenção $\alpha q\beta$ da página:

$$q_010 \vdash 1q_00 \vdash 10q_0B \vdash 1q_10 \vdash 10q_fB.$$

O terceiro passo lê o branco e volta ao $0$ final; o quarto lê $0$ e aceita. Para $101$:

$$q_0101 \vdash 1q_001 \vdash 10q_01 \vdash 101q_0B \vdash 10q_11,$$

e a máquina para sem transição definida, logo rejeita. Para $\varepsilon$, a configuração inicial é $q_0B$, que passa a $q_1B$ com a cabeça no branco, onde não há transição: rejeita. Cada fase percorre no máximo $n+1$ células, por isso a máquina termina sempre. Parar fora de final é rejeitar.

Comparar extremos e vários blocos

Para palíndromos sobre $\{0,1\}$, guarda no estado a primeira letra não marcada e risca-a. Vai até à última letra não marcada e verifica se é igual; se for, risca-a também e regressa à esquerda, e caso contrário rejeita. Quando não restam letras, aceita, e se restar uma única letra no centro aceita sem procurar um par.

Para $01110$, as rondas retiram $0$ com $0$, depois $1$ com $1$, ficando o $1$ central. Cada ronda retira uma ou duas letras, provando terminação.

Para $\{a^nb^na^n\mid n\ge0\}$, verifica primeiro o formato dos três blocos. Em cada ronda, marca um $a$ no primeiro bloco, um $b$ no segundo e um $a$ no terceiro, com marcadores diferentes que conservem a origem. Se um bloco acabar antes de outro, rejeita. Se todos acabarem ao mesmo tempo, aceita. Em $aabbaa$, duas rondas chegam; em $aabba$, a segunda ronda não encontra o último $a$. A fita permite voltar a comparar uma terceira contagem, que uma única pilha não consegue tratar desta forma. Esta linguagem é decidível, mas não livre de contexto.

Para reconhecer $\{0^{2^k}\mid k\ge0\}$, trabalha só com zeros ainda ativos. Cada ronda percorre-os alternando um estado par e um ímpar:

1. Marca um zero em cada par e deixa o outro ativo.
2. Se havia mais de um zero e a contagem era ímpar, rejeita; se havia exatamente um, aceita.
3. Caso contrário, volta ao início e repete.

As contagens ativas de $0000$ são $4,2,1$, enquanto $000000$ dá $6,3$ e rejeita. A entrada vazia é rejeitada. Os marcadores são ignorados nas rondas seguintes, e a quantidade ativa diminui, garantindo terminação.

Para uma linguagem regular, uma TM pode copiar o DFA para o seu controlo, ler da esquerda para a direita sem alterar a entrada e, no primeiro branco, aceitar exatamente nos estados que eram finais. Usar uma TM não obriga a criar marcas quando a condição já é finita.

Usar a fita para calcular

Uma máquina também pode produzir um resultado. Para incrementar um número binário, percorre a entrada até ao branco à direita, volta uma célula e propaga o transporte:

• ao ler $1$, escreve $0$ e continua para a esquerda;
• ao ler $0$, escreve $1$ e termina;
• se chegar ao branco à esquerda, escreve $1$ e termina.

Por exemplo, $1011$ torna-se $1100$: os dois uns finais passam a zeros e o zero anterior passa a um. $111$ torna-se $1000$, usando uma célula antes da antiga entrada. A descrição do resultado deve indicar onde ele fica e onde termina a cabeça, não apenas qual linguagem a máquina aceita.

Na soma de duas parcelas da mesma largura, codificadas como $=n_1+n_2$, o resultado fica à esquerda de $=$ e o resto da fita pode ser apagado. Trabalha com espaço para um bit adicional se houver transporte final. Para calcular, trabalha da direita para a esquerda, guardando o transporte no estado. Como as duas parcelas estão em regiões distintas, marca cada bit já usado e desloca-te entre elas para obter o par seguinte. Por exemplo, $011+010$ produz $101$: no bit menos significativo, $1+0=1$; depois $1+1=0$ com transporte $1$; no último, $0+0+1=1$. A fita trata o armazenamento e os estados tratam os casos finitos de soma e transporte.

Para complemento para dois num comprimento fixo, percorre da direita até ao primeiro $1$, conservando os bits vistos, incluindo esse $1$. Inverte todos os bits que ficam à esquerda. Assim, $0100$ passa a $1100$, e $0000$ fica $0000$ ignorando overflow. O exemplo $1000$ também fica $1000$, pois representa o valor mínimo nessa largura. O comprimento fixo e o tratamento de overflow fazem parte da operação.

Técnicas úteis incluem guardar um símbolo no estado, marcar símbolos já tratados e dividir o algoritmo em subrotinas com estados de entrada e saída. Várias pistas na mesma fita podem usar símbolos-tuplo, como $(a,\text{marcado})$. Isso aumenta o alfabeto finito, sem criar outro tipo de memória.

Compactar a fita sem deixar intervalos vazios

Para remover todos os $Y$ de uma entrada sobre $\{X,Y\}$, apagar cada $Y$ onde o encontramos deixaria brancos entre os $X$. O resultado pedido é um bloco contínuo $X^k$, a partir da primeira célula original, com $k$ igual à quantidade inicial de $X$.

Usa cinco estados de trabalho e o final $f$, sem saídas. $B$ é branco. Cada célula da tabela dá estado seguinte, símbolo escrito e movimento:

Estado	$X$	$Y$	$B$
$s$, início	$(s,X,R)$	$(g,Y,R)$	$(f,B,R)$
$g$, procurar outro $X$	$(m,Y,L)$	$(g,Y,R)$	$(c,B,L)$
$m$, regressar ao intervalo	$(w,X,R)$	$(m,Y,L)$	$(w,B,R)$
$w$, preencher o primeiro $Y$	Indefinida	$(s,X,R)$	Indefinida
$c$, limpar os $Y$ finais	$(f,X,L)$	$(c,B,L)$	$(f,B,L)$

$s$ atravessa o prefixo de $X$ já compacto. Ao encontrar um $Y$, $g$ procura o próximo $X$. Se o encontrar, troca esse $X$ por $Y$ e regressa em $m$, conservando os $Y$. Ao encontrar o $X$ que limita o prefixo, ou o branco à esquerda, move uma célula à direita para $w$. Essa célula ainda é o primeiro $Y$ do intervalo; $w$ troca-o por $X$.

Uma ronda desloca um $X$ para a primeira posição livre do prefixo. A quantidade de $X$ diminui temporariamente em $g$ e recupera em $w$. Só a ronda completa conserva essa quantidade. Apagar os $Y$ durante o regresso em $m$ impediria $w$ de encontrar o símbolo que deve substituir.

Para $YXYX$, a primeira ronda é:

Estado	Índice da cabeça	Fita entre as células 0 e 3
$s$	0	$YXYX$
$g$	1	$YXYX$
$m$	0	$YYYX$
$m$	-1, branco	$YYYX$
$w$	0	$YYYX$
$s$	1	$XYYX$

Os índices começam em zero e os estados ficam fora da fita. A ronda seguinte deixa $XXYY$ e retoma $s$ na célula 2. Já não há outro $X$, por isso $g$ chega ao branco e $c$ apaga os dois $Y$ finais. Termina com $XX$ nas células 0 e 1, brancos nas restantes, estado $f$ e cabeça na célula 0.

Cada ronda completa aumenta o prefixo compacto em um $X$, e há apenas finitos $X$ na entrada. As varreduras percorrem a região finita original e a limpeza termina ao chegar ao prefixo ou ao branco esquerdo. Se a entrada só tiver $Y$, a limpeza deixa tudo branco; se for vazia ou já só tiver $X$, $s$ chega diretamente ao final. A máquina termina em todas as entradas. Aceitar aqui assinala a conclusão do cálculo, não uma seleção das palavras que já estavam compactas.

Variantes com o mesmo poder

Máquinas com várias fitas não reconhecem mais linguagens que máquinas com uma fita. Uma fita pode codificar as várias fitas e marcar a posição de cada cabeça. Para simular um passo, varre a codificação, encontra os símbolos sob as cabeças e atualiza-os. Pode levar mais passos, mas mantém o resultado.

O não determinismo também não acrescenta linguagens reconhecíveis. Uma máquina determinística explora a árvore de computações por níveis, por isso não fica presa num ramo infinito antes de chegar a outro ramo que aceita. Para reconhecer, basta encontrar um ramo aceitante.

Uma fita ilimitada só para a direita pode codificar as duas metades de uma fita bilateral em pistas. Duas pilhas também simulam uma fita: uma guarda a parte à esquerda da cabeça, a outra a célula atual e a parte à direita. Mover a cabeça corresponde a passar um símbolo de uma pilha para a outra.

A tese de Church-Turing identifica os procedimentos efetivos com o que estas máquinas conseguem calcular. É uma tese sobre a noção informal de algoritmo, não um teorema que deduz essa noção de uma definição matemática. Um computador físico tem memória finita; a comparação usa o modelo idealizado com memória extensível.

Reconhecível e decidível

Uma linguagem é reconhecível, ou recursivamente enumerável, se existe uma TM que aceita exatamente as suas palavras. É decidível, ou recursiva, se existe uma TM que termina em todas as entradas e responde corretamente.

Máquina para $L$	Se $w\in L$	Se $w\notin L$
Reconhecedor	Termina e aceita	Pode terminar e rejeitar, ou correr para sempre
Decisor	Termina e aceita	Termina e rejeita

A máquina de marcação de $a^nb^n$ é um decisor, porque a sua prova de terminação abrange também as palavras rejeitadas. Reconhecer exige aceitar cada palavra de $L$ após finitos passos, não apenas evitar aceitar palavras erradas.

Todas as decidíveis são reconhecíveis. Nem todas as reconhecíveis são decidíveis. Dar mais tempo a uma simulação não resolve esta diferença: não conseguir prever se ela vai parar é precisamente parte do problema.

Se $L$ e $\overline L$ forem reconhecíveis, então $L$ é decidível. Simula os dois reconhecedores alternando um passo de cada. A palavra dada pertence a $L$ ou ao seu complemento, pelo que um dos reconhecedores acabará por aceitá-la. Responde sim quando o reconhecedor de $L$ aceitar, ou não quando o do complemento aceitar.

Máquina universal e codificação

Uma TM tem finitos estados, símbolos e transições, por isso pode ser codificada por uma palavra $\langle M\rangle$. Uma máquina universal recebe $\langle M,w\rangle$ e simula $M$ em $w$. O programa da máquina simulada torna-se parte da entrada.

A linguagem $A_{TM}=\{\langle M,w\rangle\mid M\text{ aceita }w\}$ é reconhecível: simula $M$ e aceita se ela aceitar. Se $M$ não parar, a simulação também pode não parar.

O problema da paragem

Define $HALT=\{\langle M,w\rangle\mid M\text{ para em }w\}$. É reconhecível, pois podes simular e aceitar quando a simulação parar, mas é indecidível.

Supõe que existe um decisor $H$ para $HALT$. Constrói $D$ que, ao receber $\langle M\rangle$, consulta $H(\langle M,\langle M\rangle\rangle)$. Se $H$ disser que $M$ para, $D$ entra num ciclo infinito. Se disser que não para, $D$ termina.

Agora executa $D$ com a sua própria codificação. Se $H$ disser que $D$ para, a construção faz $D$ não parar. Se disser que não para, faz $D$ parar. Ambas as respostas contradizem a correção de $H$. Logo, esse decisor não existe.

Reduções de indecidibilidade

Por exemplo, $HALT\le_m A_{TM}$. Dada $\langle M,w\rangle$, constrói uma máquina $N$ que ignora a sua entrada, simula $M$ em $w$ e aceita se essa simulação parar, quer aceitando quer rejeitando. Tens $\langle M,w\rangle\in HALT$ se e só se $\langle N,\varepsilon\rangle\in A_{TM}$. Portanto, $A_{TM}$ também é indecidível.

Ver o que continua decidível com um limite de passos

Uma pergunta limitada a $t$ passos pode ser decidível: simula esses passos e termina. Não concluas indecidibilidade só porque o enunciado fala de máquinas de Turing.

Mesmo perguntar se alguma entrada, ou se todas as entradas, fazem uma TM determinística dar mais de um limite fixo $t$ de passos é decidível. Nos primeiros $t$ movimentos, a cabeça não alcança uma posição de entrada além da posição $t+1$. Basta enumerar palavras de comprimento até $t+1$, incluindo as curtas cujo branco final pode ser encontrado. Uma entrada mais longa tem, nesse tempo, o mesmo comportamento que o seu prefixo de comprimento $t+1$. Simula cada representante por esse limite e combina as respostas conforme o quantificador. Há finitos representantes; o procedimento pode ser caro, mas termina. Este argumento usa o limite fixo e não se estende à pergunta de paragem sem limite.