Problema de parada
O problema da parada é um problema na ciência da computação. O problema é olhar para um programa de computador e descobrir se o programa vai funcionar para sempre ou não. Dizemos que um programa "resolve o problema de parada" se ele pode olhar para qualquer outro programa e dizer se esse outro programa vai ou não rodar para sempre.
Por exemplo, um programa como este:
enquanto Verdadeiro: continuar;irá loopar para sempre, mas o programa
enquanto Falso: continuar;pára muito rapidamente.
Existe algum programa que resolva o problema de parada? Afinal, não existe. Provamos este fato mostrando que se existe um programa que resolve o problema de parada, então algo impossível acontece. Portanto, no momento, vamos agir como se realmente houvesse um programa que resolvesse o problema de parada. Aqui, P é uma função que avaliará a função F (chamada com argumento I) e retornará verdadeira se for executada para sempre e falsa de outra forma.
def P(F, I): se F(I) correr para sempre: return True; else: return False;P pode olhar para qualquer programa e descobrir se ele vai funcionar para sempre ou não. Usamos P para fazer um novo programa que chamaremos Q. O que Q faz é olhar para outro programa e depois responder a seguinte pergunta: "Se executarmos este programa e o fizermos ver uma cópia de si mesmo, ele será executado para sempre?". Podemos fazer Q porque temos P. Tudo o que precisamos fazer é dizer a Q para criar um novo programa que seja o programa antigo olhando para si mesmo, e então usar P para descobrir se o novo programa funciona para sempre ou não.
def Q(F): retornar P(F, F);Agora fazemos outro programa R. R olha para outro programa e pede a Q a sua resposta sobre esse programa. Se Q responder "sim, se executarmos este programa e o fizermos olhar para uma cópia de si mesmo, ele será executado para sempre", então R pára. Se Q responder "não, se executarmos este programa e o fizermos olhar para uma cópia de si mesmo, ele não correrá para sempre", então R entra em um loop infinito e corre para sempre.
def R(F): se Q(F): retornar; //terminado mais: enquanto Verdadeiro: continuar; //lugar para sempreAgora olhamos para o que acontece se fizermos R olhar para uma cópia de si mesmo. Duas coisas podem acontecer: ou ela vai parar ou correr para sempre.
Se rodar R e fazê-lo olhar para uma cópia de si mesmo não rodar para sempre, então Q respondeu "sim, se rodarmos este programa e o fizermos olhar para uma cópia de si mesmo, ele rodará para sempre". Mas Q disse isso quando olhou para R em si. Então o que Q realmente disse foi: "sim, se rodarmos R e o fizermos olhar para uma cópia de si mesmo, ele rodará para sempre". Portanto, o Q disse isso: Se R rodar em uma cópia de si mesmo não rodar para sempre, então ele rodará para sempre. Isto é impossível.
Se rodar R e fazer com que ele olhe uma cópia de si mesmo corre para sempre, então Q respondeu "não, se rodarmos este programa e fizermos com que ele olhe uma cópia de si mesmo ele não correrá para sempre". Mas Q disse isso quando olhou para R em si. Então o que Q realmente disse foi: "não, se rodarmos R e o fizermos olhar para uma cópia de si mesmo, ele não rodará para sempre". Portanto, o que o Q disse foi Se R rodar em uma cópia de si mesmo corre para sempre, então ele não corre para sempre. Isto também é impossível.
Aconteça o que acontecer, ficamos com uma situação impossível. Fizemos algo errado, e precisamos descobrir o que foi. A maioria das coisas que fizemos não estavam erradas. Não podemos dizer que "fazer um programa olhar para uma cópia de si mesmo está errado", ou "olhar para o que outro programa disse e depois entrar em um loop se ele disse uma coisa, e parar se ele disse outra coisa" está errado. Não faz sentido dizer que não estamos autorizados a fazer essas coisas. A única coisa que fizemos que parece que pode estar errada é que fingimos que um programa como P existe em primeiro lugar. E como esta é a única coisa que poderia estar errada, e algo deve estar errado, é isto. Esta é a prova de que um programa como o P não existe. Não há nenhum programa que resolva o problema de parada.
Esta prova foi encontrada por Alan Turing em 1936.
Perguntas e Respostas
P: Qual é o problema da suspensão?
R: O problema da suspensão é um problema na informática que olha para um programa de computador e determina se o programa será executado para sempre ou não.
P: Como sabemos se um programa resolve o problema de parada?
R: Nós dizemos que um programa "resolve o problema de parada" se ele pode olhar para qualquer outro programa e dizer se esse outro programa vai funcionar para sempre ou não.
P: Existe alguma maneira de provar que não existe nenhum programa desse tipo?
R: Sim, mostrando que se houvesse um programa desse tipo, então algo impossível aconteceria. Essa prova foi encontrada por Alan Turing em 1936.
P: O que o P faz?
R: P é uma função que avalia outra função F (chamada com argumento I) e retorna verdadeiro se correr para sempre e falso caso contrário.
P: O que o P faz?
R: P olha para outro programa e depois responde à questão de se a execução desse mesmo programa em si resultará ou não em um loop infinito. Faz isso usando P para fazer uma avaliação da função F.
P: O que faz o R?
R: R olha para outro programa e pede a resposta de R sobre esse programa em particular. Se o Q responde "sim, se nós executarmos esse programa e o fizermos olhar para uma cópia de si mesmo, ele correrá para sempre", então o R pára; entretanto, se o Q responde "não, se nós executarmos esse programa e o fizermos olhar para uma cópia de si mesmo, ele não correrá para sempre", então o R entra num loop infinito e corre para sempre.
P: O que acontece quando o senhor faz o R olhar para si mesmo?
R: Duas coisas podem acontecer - ou R pára ou corre para sempre - mas ambos os resultados são impossíveis de acordo com o que foi provado sobre programas como o P não existente, então algo deve ter dado errado em algum lugar no caminho que leva a fazer o R olhar para si mesmo.
