Programas impossíveis de se construir

Já se perguntou por que o compilador não emite Warnings caso o seu código possa entrar em loop infinito? Já se perguntou também por que ninguém nunca fez um programa que prova um teorema matemático automaticamente?

Na verdade, essas duas perguntas estão relacionadas de alguma forma. A resposta para essas perguntas é que esses tipos de programas são impossíveis de se programar.

O problema de se verificar loops infinitos em programas tem um nome: problema da parada. Suponha que esse problema tenha solução, ou seja, existe um programa que verifica parada para o programa "P" e entrada "i".

bool Halt(string P, string i){
  //Código mágico que verifica se o programa representado 
  //pela string P para a entrada representada pela string i.
}

Utilizando esse trecho de código, vamos criar o seguinte programa:

bool Miracle(string P){
if Halt(P,P){
   while(true){}  
}else{
  return true
}
}

Executemos esse programa com entrada ele mesmo. O que vai acontecer? Se ele para com sua própria entrada ele irá executar o while e não irá parar. Mas caso ele não pare, ele irá retornar true e irá parar. Temos uma contradição. Portanto é impossível verificar parada de programas.

Quanto a provadores automáticos, suponha que eles existam. Com eles é possível especificar programas e pedir prova de parada. Assim, também é impossível que eles existam.

Esse resultado relacionado com loops infinitos é chamado de Indecibilidade do Problema da Parada e foi provado por Alan Turing em seu artigo " On computable numbers, with an application to the Entscheidungsproblem".

Existem outros programas impossíveis de se programar e em geral todos eles derivam do problema da parada.