A prova de diagonalização de Turing é uma versão deste jogo em que as questões percorrem uma lista infinita de algoritmos possíveis, perguntando repetidamente: “Este algoritmo pode resolver o problema que gostaríamos de provar incomputável?”
“São uma espécie de ‘questões do infinito’”, disse Williams.
Para vencer o jogo, Turing precisava criar um problema em que a resposta fosse não para todos os algoritmos. Isso significava identificar uma entrada específica que faz com que o primeiro algoritmo produza a resposta errada, outra entrada que faz o segundo falhar e assim por diante. Ele encontrou essas informações especiais usando um truque semelhante ao que Kurt Gödel usara recentemente para provar que afirmações autorreferenciais como “esta afirmação é improvável” representavam problemas para os fundamentos da matemática.
O principal insight foi que todo algoritmo (ou programa) pode ser representado como uma sequência de 0s e 1s. Isso significa, como no exemplo do programa de verificação de erros, que um algoritmo pode receber o código de outro algoritmo como entrada. Em princípio, um algoritmo pode até usar seu próprio código como entrada.
Com esse insight, podemos definir um problema incomputável como o da prova de Turing: “Dada uma string de entrada que representa o código de um algoritmo, produza 1 se esse algoritmo produzir 0 quando seu próprio código for a entrada; caso contrário, produza 0.” Todo algoritmo que tentar resolver esse problema produzirá a saída errada em pelo menos uma entrada – ou seja, a entrada correspondente ao seu próprio código. Isso significa que esse problema perverso não pode ser resolvido por nenhum algoritmo.
O que a negação não pode fazer
Os cientistas da computação ainda não haviam terminado a diagonalização. Em 1965, Juris Hartmanis e Richard Stearns adaptaram o argumento de Turing para provar que nem todos os problemas computáveis são criados iguais – alguns são intrinsecamente mais difíceis do que outros. Esse resultado lançou o campo da teoria da complexidade computacional, que estuda a dificuldade dos problemas computacionais.
Mas a teoria da complexidade também revelou os limites do método contrário de Turing. Em 1975, Theodore Baker, John Gill e Robert Solovay comprovado que muitas questões em aberto na teoria da complexidade nunca poderão ser resolvidas apenas pela diagonalização. O principal deles é o famoso problema P versus NP, que pergunta se todos os problemas com soluções facilmente verificáveis também são fáceis de resolver com o algoritmo engenhoso certo.
Os pontos cegos da diagonalização são uma consequência direta do alto nível de abstração que a torna tão poderosa. A prova de Turing não envolveu nenhum problema incomputável que pudesse surgir na prática – em vez disso, ela inventou esse problema na hora. Outras provas de diagonalização são igualmente distantes do mundo real, portanto não podem resolver questões onde os detalhes do mundo real são importantes.
“Eles lidam com computação à distância”, disse Williams. “Imagino um cara que está lidando com vírus e os acessa através de algum porta-luvas.”
O fracasso da diagonalização foi uma indicação precoce de que resolver o problema P versus NP seria uma longa jornada. Mas apesar das suas limitações, a diagonalização continua a ser uma das principais ferramentas no arsenal dos teóricos da complexidade. Em 2011, Williams usou-o junto com uma série de outras técnicas para provar que um determinado modelo restrito de computação não poderia resolver alguns problemas extraordinariamente difíceis – um resultado que escapou aos pesquisadores durante 25 anos. Estava muito longe de resolver P versus NP, mas ainda representava um grande progresso.
Se você quiser provar que algo não é possível, não subestime o poder de simplesmente dizer não.
História original reimpresso com permissão de Revista Quanta, uma publicação editorialmente independente do Fundação Simons cuja missão é melhorar a compreensão pública da ciência, cobrindo desenvolvimentos e tendências de pesquisa em matemática e ciências físicas e biológicas.
