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;
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/
Fonte:
Michael Sipser - Uma introdução à teoria da computação.
http://www.cgl.uwaterloo.ca/~csk/halt/
