O problema da parada.

Computadores em sua essência são máquinas feitas para resolver problemas através de algoritmos, por incrível que pareça eles possuem certas limitações com algumas tarefas aparentemente simples. Vou demonstrar um deles, que consiste no seguinte:

“É possível construir um programa que recebendo um programa e os dados de entrada para o próprio, diga se ele para ou continua indefinidamente, ou seja entra em loop infinito?”

Alan Turing provou que não, apresentarei uma adaptação para esta prova em pseudocódigo. Vamos começar com uma função que recebe um programa, que nada mais é do que um conjunto de dados, nesse caso um vetor de chars, e a entrada para esse programa, outro vetor de chars.

boolean verificaParada(char[] programa,char[] entrada){

  if(ALGUMA FORMA DE VERIFICAR SE O PROGRAMA PARA){

     return true;

  }else{

     return false;

  }

}

Vamos deixar de lado a maneira como o if funciona, vamos supor por enquanto que ele consegue definir se o programa para. Agora podemos construir a seguinte função:

boolean verificaEleMesmo(char[] programa){

  return verificaParada(programa, programa);

}

É simples, apenas verifica se o programa para quando a entrada for ele próprio. Mais uma função, é dela que vamos tirar a prova.

boolean ferraTudo(char[] programa){

  if(verificaEleMesmo(programa)){

    while(true){

      

    }
    return true;

  }else{

    return false;

  }

}

Basicamente essa função entra em loop infinito se o programa que ela recebe para, verificando quando a entrada é ele mesmo. Mas e se jogássemos o “ferraTudo” como entrada? Ocorreria um paradoxo! Vejamos, se a função "verificaEleMesmo" constatar que o programa "ferraTudo" para, ele ia entrar na condição e ficar em loop infinito, mas se ele entra em loop ele não para, então há uma contradição.


Fonte:

Michael Sipser - Uma introdução à teoria da computação.
http://www.cgl.uwaterloo.ca/~csk/halt/