Máquina de Turing

Como funciona

A máquina. Uma fita de células, uma cabeça que lê e escreve um símbolo por vez, um estado interno e uma tabela. Cada célula da tabela diz: no estado tal, lendo tal símbolo, escreva isto, mova para a esquerda ou para a direita e passe para tal estado. A regra aplicada acende em dourado a cada passo. Quando a máquina chega ao estado H, ela para.

As máquinas de exemplo:

• Somar um (unário): o número 3 escrito como 111; a máquina anda até o fim e acrescenta um 1.
• Somar dois números: 111+11 vira 11111 — troca o + por 1 e apaga um 1 no fim.
• Somar um em binário: 1011 vira 1100, com o vai-um andando para a esquerda. Troque a fita inicial e teste outros números.
• Castores ocupados: entre todas as máquinas com 2, 3 ou 4 estados que param numa fita vazia, as que escrevem mais uns. O campeão de 4 estados para depois de exatamente 107 passos com 13 uns — o teste da simulação confere os três recordes. Com 5 estados, o recorde de passos é 47 176 870, provado só em 2024; com 6, ninguém sabe.
• Uma que nunca para: escreve 1 e anda para a direita para sempre. Rodá-la não prova isso: em qualquer momento, você só sabe que ela ainda não parou.

Dois algoritmos. Ordenar é o problema; a lista embaralhada é uma entrada; a lista em ordem é a saída. A bolha compara vizinhos e troca os invertidos; a seleção acha o menor do resto e o põe no lugar. As duas chegam à mesma resposta por caminhos diferentes: a seleção sempre faz $\frac{n(n-1)}{2}$ comparações e no máximo $n-1$ trocas; a bolha faz exatamente uma troca por par fora de ordem.

O problema da parada. Suponha um programa PARA? que, para qualquer programa e entrada, responde corretamente se ele termina. Construa CONTRÁRIO: ele pergunta a PARA? se P para quando recebe a própria descrição, e faz o oposto. Rode CONTRÁRIO nele mesmo e escolha a resposta do preditor: qualquer uma sai errada. Logo, PARA? não existe.

A parede exponencial. Uma busca que testa todas as combinações de $n$ escolhas de sim ou não percorre $2^n$ caminhos. A um bilhão de caminhos por segundo, 40 escolhas levam 18 minutos; 100 levam milhares de vezes a idade do universo. Um algoritmo de $n^3$ passos, no mesmo computador, faz $n=100$ num milésimo de segundo.