O problema da parada

Hoje estava lendo sobre o Problema da Parada e percebi um pouco mais a profundidade desse resultado, a partir de alguns exemplos. Resolvi escrever aqui sobre ele. Para quem não conhece o problema, ele pode ser encarado da seguinte forma:

Problema da Parada

Entrada: um programa "P" com sua respectiva entrada "E".

Saída: Sim, se o programa "P" para de rodar com a entrada "E". Não, caso contrário.

Em outras palavras, dado um programa, você quer saber se ele para de rodar ou não. Pra descobrir isso, você precisa de um outro programa. Mas, como Alan Turing mostrou, não existe um programa que resolva o Problema da Parada. Não vou entrar na argumentação de porque ele não existe, mas sim em uma outra coisa que nunca havia me dado conta, de quão importante é esse resultado.

Considere, por exemplo, o Último Teorema de Fermat. Caso existisse um programa que resolvesse o problema da parada, teríamos uma prova quase trivial para o Último Teorema de Fermat. Considere o programa P abaixo:

Programa P

Para toda tripla (x, y, n) de inteiros, x > 0, y > 0, n > 2.

Verifique se existe z inteiro satisfazendo:

Se existe z, pare.

Note que esse programa só parará de rodar caso exista um contra-exemplo para o Último Teorema de Fermat. Portanto, utilizando a solução do Problema da Parada com o programa P como entrada, teríamos como verificar a validade do Último Teorema de Fermat. Da mesma forma, esse mesmo argumento poderia ser utilizado para provar (ou refutar) diversas conjecturas e resultados por aí.

Claro que, mesmo se existisse, a solução para o Problema da Parada poderia ser ineficiente, ou seja, poderia ser necessário muito tempo para que o programa rodasse e uma resposta fosse dada. Mas esse tempo ainda seria finito e, portanto, podemos praticamente afirmar que seria apenas uma "questão de tempo" até termos uma resposta. Note que o programa P serviria para refutar o Último Teorema de Fermat caso ele não fosse verdadeiro mas, por outro lado, apenas com ele, nunca poderíamos ter certeza de que o teorema é verdadeiro, pois nesse caso ele teria que testar uma infinidade de triplas e, portanto, nunca pararia. Assim, de fato, a solução do Problema da Parada seria um resultado importantíssimo.