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 sempre

Agora 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.