CCT-UFCA/Ciência da Computação/Teoria da Computação/Máquinas de Turing
O que uma Máquina de Turing (MT)?
[editar | editar código]Uma Máquina de Turing (MT) é, de forma informal, semelhante a um autômato de pilha, porém com maior capacidade de processamento. Sua principal estrutura é uma fita infinita, que funciona como memória. Essa fita possui início (à esquerda), mas não tem fim, sendo inicialmente preenchida com a entrada do problema seguida de símbolos em branco (⊔) nas posições restantes.
A MT possui uma cabeça de leitura e escrita que pode se mover para a esquerda ou para a direita na fita. Essa cabeça lê o símbolo presente na célula atual, pode sobrescrevê-lo com outro símbolo, e então se desloca para a próxima célula, conforme definido pelas regras da máquina.
A computação é guiada por uma função de transição δ, que define o comportamento da máquina. Quando ela está no estado q, lendo o símbolo x, e δ(q, x) = (q′, x′, P), os seguintes passos são executados:
- A máquina transita para o novo estado q′;
- O símbolo x na fita é substituído por x′;
- A cabeça se move uma posição: à esquerda se P=E, ou à direita se P=D.
Se a cabeça estiver na primeira posição da fita e for instruída a mover-se para a esquerda, ela permanece no lugar.
A computação prossegue até que a máquina entre em um estado de aceitação ou rejeição, momento em que a execução é encerrada. Caso isso nunca ocorra, a máquina nunca para.
Durante a execução, ocorrem mudanças no estado atual, no conteúdo da fita e na posição da cabeça. Cada combinação possível desses três elementos define uma configuração da Máquina de Turing.
Uma configuração é representada por uma cadeia do tipo u q v, em que:
- u representa a parte da fita à esquerda da cabeça;
- v representa a parte da fita à direita, começando pelo símbolo atualmente sob a cabeça;
- q é o estado atual da máquina.
Após o trecho representado por v, considera-se que a fita segue indefinidamente com o símbolo ⊔ (em branco).
Comportamento de uma MT
[editar | editar código]De maneira informal, suponha a linguagem L = {w#w | w ∈ {0,1}∗}, para resolver isso a máquina vai fazer um zigue-zague, comparando os símbolos antes e depois do símbolo #, posição por posição. Se não houver o # ou se os símbolos comparados forem diferentes, a máquina rejeita a entrada. Quando dois símbolos correspondem, eles são marcados com um x. Esse processo continua até todos os símbolos antes do # serem marcados. Por fim, a máquina verifica se restam símbolos não marcados após o #. Se houver, rejeita; se não houver, aceita.
Exemplo de MT para L = {02^n ∣ n ≥ 0}
[editar | editar código]A ideia seguida aqui foi fazer com que a MT verificasse se a quantidade de zeros na fita é uma potência de 2. Para isso, ela faz varreduras sucessivas, marcando (com 'x') a cada duas iterações o segundo zero de cada par. Se conseguir formar pares certinhos em cada varredura (ou seja, quantidade par de zeros), ela continua até restar apenas um zero não marcado — nesse caso, aceita a entrada.
Se em alguma varredura sobrar um zero sem par (número ímpar de zeros), ela rejeita.
Veja como essa ideia foi aplicada a seguir: