Máquinas de Turing

Começamos por um exemplo muito simples. Na verdade nem é necessária uma máquina de Turing para reconhecer esta linguagem, pelo que este exemplo é puramente ilustrativo.

Considere-se a linguagem formada pelas palavras sobre o alfabeto $\{ 0, 1 \}$ que são alternantes, isto é, em que cada símbolo (sem ser o primeiro) é diferente do que o antecede.
A seguinte máquina de Turing reconhece a linguagem:

A intuição por detrás da máquina é simples:
A partir do estado inicial, lendo o input da esquerda para a direita, a máquina transita para $q_1$ quando lê 0, memorizando dessa forma que o próximo símbolo a ler terá de ser 1, e para $q_2$ quando lê um 1, registando que o próximo símbolo a ler deve ser 0. A máquina vai então alternando entre os estados $q_1$ e $q_2$ até processar todo o input, o que acontece quando é lido um espaço. Neste momento, a computação vai para o estado de aceitação, terminando.
Caso dois símbolos consecutivos sejam iguais, a computação fica indefinida, já que não está representada nenhum transição a partir de $q_1$ quando o símbolo lido é 0, nem a partir de $q_2$ quando o símbolo lido é 1.

No exemplo 1 usamos, para além dos estados $Q = \{ q_{in}, q_1, q_2 \}$ usamos apenas o estado de aceitação, pois estávamos apenas interessados em reconhecer a linguagem. Para decidir a linguagem, basta então adicionar um estado de rejeição e meter todas as transições não definidas do grafo anterior a apontar para lá.

Vamos continuar com a mesma linguagem. Queremos agora uma máquina de Turing que, em vez de reconhecer/decidir essa linguagem, tenha output 1 se o input for reconhecido pela linguagem e 0 caso contrário.

No exemplo anterior vimos a máquina de Turing para decidir a linguagem. A única diferença aqui é que queremos:

• quando uma palavra é aceite, imprimir 1 e terminar a computação no estado de aceitação;
• quando uma palavra não é aceite, imprimir 0 e terminar a computação no estado de aceitação na mesma (a nossa função completou com sucesso, pois reconheceu que a palavra não é aceite).

Para isso, substituímos os estados $q_{ac}$ e $q_{rj}$ por estados $q_3$ e $q_4$ respetivamente, que indicam que já sabemos o resultado da nossa computação. Neste ponto, para terminar a computação com sucesso basta então apenas imprimir o output adequado e ir para o estado de aceitação, como é feito abaixo.

Observe-se que o output deve ser imprimido só depois do input ser todo lido, pelo que no estado $q_4$ temos de ler o resto dos 0's e 1's.

Para oferecer um exemplo menos simples, vamos desenhar uma máquina de Turing que reconheça a linguagem sobre o alfabeto $\Sigma = \{ 0, 1 \}$ cujas palavras são palíndromos.

Num primeiro momento, é sempre importante verificar se a palavra vazia deve ser aceite - neste caso deve. Quando estamos na presença de um caso destes, normalmente temos de ter especial cuidado a construir a nossa máquina.

Pensemos: um palíndromo é uma palavra cuja palavra invertida é igual a si própria. Parece então fazer sentido ir verificando as pontas da palavra, verificando se coincidem. Essa verificação terá de ser feita consecutivamente, "podando as pontas" da palavra até dar a volta (verificando então que a palavra é um palíndromo) ou até as pontas não serem iguais (obtendo então que a palavra não é um palíndromo).

Este método de verificar e podar consecutivamente as pontas tem um defeito: por definição, não tem em conta palíndromos de comprimento ímpar - palavras onde eventualmente temos as pontas a "coincidir". Ao construir a máquina teremos, portanto, de ter esse caso em consideração (e já veremos abaixo que é uma modificação bastante simples à máquina).

Temos, então, a máquina de Turing que resolve o problema proposto acima. Podemos notar as tais transições auxiliares para palavras de comprimento ímpar referidas acima, partindo de $q_1$ e $q_3$ para $q_{ac}$. Em $q_0$ e $q_2$, as iterações pela palavra até encontrar a próxima ponta, e em $B_1$ e $B_2$ o backtracking até à primeira ponta, marcada a última.

Acabamos, então, esta secção a exemplificar o processamento de um par de palavras segundo esta máquina:

Consideremos, como primeiro exemplo, a palavra $10011$. Partindo do estado inicial, o primeiro $1$ é lido, sendo substituído por $x$ na fita. Vamos, de seguida, iterar pela fita até encontrar a outra ponta da palavra - encontrada, verificamos que também é $1$, pelo que até agora a palavra continua a poder ser um palíndromo. Marcamos esta ponta com $x$ e rebobinamos até à última ponta, e vamos agora passar a considerar a palavra $001$. Marcamos $0$ com $x$ e prosseguimos até à próxima ponta. Descobrimos, aqui, que a outra ponta tem símbolo $1$, pelo que a palavra definitivamente não é um palíndromo. Sem transição associada, a palavra é rejeitada pela máquina, e o processamento termina.

De seguida, tenhamos a palavra $10101$, palavra esta de comprimento ímpar. Vamos, mais uma vez, procurar sucessivamente marcar e podar as pontas da palavra. As 2 primeiras iterações correm da mesma forma que foi observada no primeiro exemplo: podamos as pontas $1$ e $0$, restando a palavra $1$. A vida pregou-nos uma partida, e a palavra tem comprimento ímpar. Contudo, fomos inteligentes, e já mais atrás tínhamos notado e criado transições auxiliares para esta situação! Procurando seguir os estados associados a este processamento, partimos de $q_{in}$, seguindo para $q_2$ (estamos a ler $1$) e movendo o cursor para a direita.Lemos a palavra vazia, pelo que mudamos o cursor para a esquerda e trocamos de estado para $q_3$. Aqui, tendo a tal transição auxiliar, podemos aceitar a palavra (já que, movendo-nos para a esquerda, apenas encontrámos mais um $x$), sendo a palavra assim aceite.

Converter uma máquina com transições-$S$ numa máquina de Turing é razoavelmente simples. Basta pegar em cada movimento $S$ e desdobrá-lo em dois movimentos, como apresentado em baixo:

em que $q_a$ denota um novo estado da máquina, e $\gamma$ deve ser expandido para representar todas as letras do alfabeto $\Gamma$.
É fácil de verificar que os dois segmentos acima levam à mesma transição de configurações.

Note-se que mover uma palavra para a direita numa fita unidirecional é algo relativamente fácil.
Para uma dada computação numa máquina bidirecional, delineamos a computação respetiva numa máquina de Turing unidirecional da seguinte forma: Sempre que a computação da fita bidirecional determinar que é preciso um espaço à esquerda da palavra, movemos toda a palavra para a direita. Desta forma, criamos um espaço na primeira posição onde podemos colocar o símbolo determinado pela computação da fita bidirecional. Uma forma de saber quando precisamos de um espaço à esquerda é, antes da computação, movermos o input um espaço para a esquerda. Assim, sempre que lermos um espaço em branco depois de fazermos um movimento para a esquerda, quer dizer que precisamos de mais um espaço à esquerda.

Intuitivamente, se conseguirmos dividir a fita da máquina de Turing em $k$ secções "independentes", conseguimos arranjar uma equivalência entre a máquina de Turing tradicional. Precisamos no entanto de:

• um símbolo para separar as diferentes secções da fita (que correspondem às várias fitas da máquina multifita) - vamos usar o símbolo $\#$;
• símbolos para demarcar o início e fim da fita - vamos usar $I$ e $F$;
• símbolos idênticos aos do nosso alfabeto de trabalho, mas que assinalem que a cabeça de escrita/leitura da respetiva fita está nessa posição - vamos chamar a este conjunto $\Gamma^\blacksquare$. Vamos então usar o alfabeto $\Gamma \cup \Gamma^\blacksquare \cup \{ \#, I, F \}$.
  Vamos então tentar construir uma máquina de Turing $T$ tradicional que compute o mesmo que uma máquina multifita $M$.
  A máquina $T$ começa por criar uma fita da seguinte forma:
• coloca $I$ na primeira posição;
• coloca na segunda posição a correspondente em $\Gamma^\blacksquare$ ao primeiro símbolo no input de $M$;
• coloca na fita a $\#$ seguido de $\square^\blacksquare$ uma vez por cada fita de $M$ ($k-1$ vezes);
• acaba por colocar o símbolo de terminação $F$.

Com a fita de $T$ inicializada, podemos agora fazer as mudanças indicadas por $M$. Isto é feito da seguinte forma: da esquerda para a direita, reconhecemos onde está a cabeça de escrita/leitura das correspondentes a cada uma das $k$ fitas, e fazemos a alteração necessária. Note-se que poderá ser necessário mover símbolos para a direita para disponibilizar novos espaços para alguma fita.
É importante realçar que, no final, de forma a que $T$ devolva o mesmo output que $M$, temos de converter o símbolo de $\Gamma^\blacksquare$ do espaço correspondente à última fita no correspondente símbolo de $\Gamma$, bem como remover o $F$ no final da fita.

Vamos, mais uma vez, definir para uma máquina não-determinística $N$, definir uma máquina de Turing $D$ que lhe seja equivalente.
A ideia será que $D$ terá 3 fitas:

• a primeira fita manterá o input do problema, sem o alterar;
• a segunda fita será usada para escolher o caminho a percorrer no grafo das possíveis transições de configurações;
• a terceira fita será usada para mexer no input para cada sequência na fita 2.

A máquina $D$ começa por inicializar as fitas:

• na segunda fita coloca $ para indicar o início do caminho, abre $d$ (depende do input) espaços vazios, e coloca $\#$ no final para indicar o fim do caminho.
• copia-se para a terceira fita o input.

Então, executamos na fita 3 de acordo com o caminho 2 até que:

• cheguemos a um estado de aceitação de $D$: neste caso vamos para o estado de aceitação de $N$ e terminamos a computação;
• cheguemos a um estado de rejeição de $D$: neste caso passamos ao próximo caminho na fita 2.

Se nenhum dos caminhos na fita 2 aceitar a palavra, então a palavra deve ser rejeitada.

Para uma máquina de Turing $M = (\Sigma, \Gamma, Q, q_{in}, q_{ac}, q_{rj}, \delta)$, a representação canónica é uma string da forma:

que pode ser descrita da seguinte forma:

• uma string de $n$ 1's: tantos quanto o número de estados na máquina de Turing, isto é, tantos quanto os estados em $\hat{Q} = Q \cup \{ q_{ac}, q_{rj} \}$: os $n$ estados são identificados da seguinte forma:

  $$\begin{aligned} q_1 = q_{in} &= 100 \cdots 00 \\ q_2 &= 010 \cdots 00 \\ q_3 &= 001 \cdots 00 \\ & \vdots \\ q_{n-1} = q_{ac} &= 000 \cdots 10 \\ q_n = q_{rj} &= 000 \cdots 01 \end{aligned}$$

• um 0 de separação;

• uma string de $k$ 1's: tantos quantos símbolos no alfabeto auxiliar $\Gamma = \Gamma \backslash \{ \square \} \cup \{ \square \} = k+1$: os $k+1$ símbolos são da seguinte forma:

  $$\begin{aligned} a_0 &= 000 \cdots 00 \\ a_2 &= 100 \cdots 00 \\ a_3 &= 010 \cdots 00 \\ &\vdots \\ a_{k-1} &= 000 \cdots 10 \\ a_k &= 000 \cdots 01 \end{aligned}$$

• um 0 de separação;

• uma sequência de strings que representam as transições dadas pela função $\delta$: cada string que representa uma transição $\delta(q_i, a_j) = (q_r, a_s, m)$ é uma palavra $trans_i = q_i a_j q_r a_s m \in \{ 0, 1 \}^*$ de comprimento $2n+2k+1$.

Consideremos por exemplo a seguinte máquina de Turing, que decide a linguagem das palavras sobre $\{0,1\}$ que começam com dois $0$'s consecutivos:

A sua representação canónica é:

A máquina tem estados ($q_0 = q_{in}$, $q_1$, $q_2 = q_{ac}$ e $q_3 = q_{rj}$).
O alfabeto de trabalho da máquina tem $2+1$ símbolos: $0$, $1$ e $\square$.
A máquina tem duas transições, representadas acima.

Seja $U$ uma máquina de Turing com 6 fitas.

A máquina, ao receber um input $x$, começa por verificar se a palavra $x$ é da forma $M \text{\textdollar} rep(\omega)$ para alguma máquina de Turing $M \in \mathcal{M}^\Sigma$ e $\omega \in \Sigma^*$, rejeitando se este não for o caso.

Passada esta verificação, a máquina passa para a fase inicial:

• copia a sequência de $1$'s correspondente ao número de estados de $M$ para a fita 2;
• copia a sequência de $1$'s correspondente ao número de símbolos de $M$ para a fita 3;
• copia as transições de $M$ para a fita 4;
• coloca o estado inicial de $M$ na fita 5;
• copia $rep(\omega)$ para a fita 6;
• coloca as cabeças de leitura/escrita de cada fita no início destas palavras.

Após a fase inicial, a máquina entra na fase de simulação. Nesta fase, $U$ faz os seguintes passos repetidamente até $M$ abortar/terminar.

• lê o símbolo onde está posicionado a cabeça de leitura/escrita da fita 6;
• lê o estado atual de $M$ na fita 5;
• percorre a fita 3 à procura da transição de $M$ para este símbolo e estado. Se não encontrar transição, $U$ aborta. Se encontrar, $U$ altera o estado de $M$ na fita 5, o símbolo na fita 6 e a posição da cabeça de leitura/escrita conforme indicado na transição encontrada;
• Se o passo anterior levar a um estado de terminação de $M$, $U$ termina em concordância com $M$.