Moore projetou sua máquina de pinball para completar a analogia com a máquina de Turing. A posição inicial do pinball representa os dados na fita que estão sendo alimentados na máquina de Turing. Crucialmente (e irrealisticamente), o jogador deve ser capaz de ajustar o local inicial da bola com precisão infinita, o que significa que especificar a localização da bola requer um número com uma procissão infinita de números após o ponto decimal. Somente nesse número poderia codificar os dados de uma fita infinitamente longa.
Em seguida, o arranjo de pára -choques dirige a bola a novas posições de uma maneira que corresponda à leitura e a escrita em uma fita de uma máquina de Turing. Certos pára -choques curvos mudam a fita de uma maneira, tornando os dados armazenados em lugares decimais distantes mais significativos de uma maneira que lembra sistemas caóticos, enquanto os pára -choques opostos curvados fazem o inverso. A saída da bola da parte inferior da caixa marca o final do cálculo, com o local final como resultado.
Moore equipou sua configuração de máquina de pinball com a flexibilidade de um computador – um arranjo de pára -choques pode calcular os primeiros mil dígitos de PI, e outro pode calcular o melhor próximo passo em um jogo de xadrez. Mas, ao fazer isso, ele também o infundiu com um atributo que talvez não possamos associar a computadores: imprevisibilidade.
Alguns algoritmos param, produzindo um resultado. Mas outros correm para sempre. (Considere um programa encarregado de imprimir o dígito final do PI.) Existe um procedimento, perguntou Turing, que pode examinar qualquer programa e determinar se ele será interrompido? Esta questão ficou conhecida como problema de parada.
Turing mostrou que esse procedimento não existe considerando o que significaria se o fizesse. Se uma máquina pudesse prever o comportamento de outra, você poderá modificar facilmente a primeira máquina – a que prevê o comportamento – para correr para sempre quando a outra máquina parar. E vice -versa: ele pára quando a outra máquina corre para sempre. Então-e aqui está a parte alucinante-tendo imaginado alimentando uma descrição dessa máquina de previsão ajustada em si. Se a máquina parar, também corre para sempre. E se corre para sempre, também para. Como nenhuma das opções poderia ser, Turing concluiu, a própria máquina de previsão não deve existir.
(Sua descoberta estava intimamente relacionada a um resultado inovador de 1931, quando o lógico Kurt Gödel desenvolveu uma maneira semelhante de Alimentando um paradoxo auto-referencial em uma estrutura matemática rigorosa. Gödel provou que existem declarações matemáticas cuja verdade não pode ser estabelecida.)
Em suma, Turing provou que resolver o problema de parada era impossível. A única maneira geral de saber se um algoritmo para é executá -lo o máximo que puder. Se parar, você tem sua resposta. Mas se não, você nunca saberá se realmente funciona para sempre, ou se teria parado se você apenas esperasse um pouco mais.
“Sabemos que existem esses tipos de estados iniciais que não podemos prever com antecedência o que vai fazer”, disse Wolpert.
Desde Moore havia projetado sua caixa Para imitar qualquer máquina de Turing, ela também pode se comportar de maneiras imprevisíveis. A saída da bola marca o fim de um cálculo; portanto, a questão de saber se algum arranjo específico de pára -choques prende a bola ou a direcionará para a saída também deve ser indecidível. “Realmente, qualquer pergunta sobre a dinâmica de longo prazo desses mapas mais elaborados é indecidível”, disse Moore.
