Problem z zatrzymaniem jest problemem w informatyce. Problemem jest spojrzenie na program komputerowy i ustalenie, czy program będzie działał wiecznie, czy nie. Mówimy, że program "rozwiązuje problem zatrzymania", jeśli potrafi spojrzeć na jakikolwiek inny program i stwierdzić, czy ten inny program będzie działał wiecznie, czy nie.

Na przykład, program taki jak ten:

 podczas gdy Prawda. Kontynuuj;

zapętli się na zawsze, ale program

 podczas gdy Fałszywy: kontynuuj;

zatrzymuje się bardzo szybko.

Czy istnieje program, który rozwiązuje problem zahamowania? Okazuje się, że nie ma. Udowodnimy to pokazując, że jeśli istnieje program, który rozwiązuje problem zatrzymania, to dzieje się coś niemożliwego. Więc na razie będziemy działać tak, jakby naprawdę istniał program, który rozwiązuje problem zatrzymania. Tutaj P jest funkcją, która oceni funkcję F (wywołaną argumentem I) i zwróci prawdę, jeśli będzie działała wiecznie, a false inaczej.

 def P(F, I):     jeśli F(I) działa wiecznie:       zwróć Prawdziwą;     inaczej:       zwróć Fałszywą;

P może przyjrzeć się każdemu programowi i dowiedzieć się, czy będzie działał wiecznie, czy nie. Używamy P do stworzenia nowego programu, który nazwiemy Q. To, co Q robi, to spojrzenie na inny program, a następnie odpowiedź na poniższe pytanie: "Jeśli uruchomimy ten program i zrobimy z niego kopię, czy będzie działał wiecznie?". Możemy zrobić Q, ponieważ mamy P. Wszystko, co musimy zrobić, to powiedzieć Q, aby stworzył nowy program, który jest starym programem patrząc na siebie, a następnie użyć P, aby dowiedzieć się, czy nowy program działa wiecznie, czy nie.

 def Q(F):     powrót P(F, F);

Teraz robimy kolejny program R. R patrzy na inny program i pyta Q o jego odpowiedź na ten program. Jeśli Q odpowie "tak, jeśli uruchomimy ten program i każemy mu spojrzeć na jego kopię, będzie on działał wiecznie", wtedy R zatrzymuje się. Jeśli Q odpowie "nie, jeśli uruchomimy ten program i każemy mu spojrzeć na kopię samego siebie, to nie będzie działał wiecznie", wtedy R wchodzi w nieskończoną pętlę i działa wiecznie.

 def R(F):     if Q(F):       return;                 //terminate     else:       while True: continue; //loop forever

Teraz patrzymy, co się stanie, jeśli zrobimy R. spojrzeć na kopię siebie. Mogą się zdarzyć dwie rzeczy: albo się zatrzyma, albo będzie działać wiecznie.

Jeśli uruchomienie R i zmuszenie go do spojrzenia na kopię samego siebie nie będzie działać wiecznie, to Q odpowiedział "tak, jeśli uruchomimy ten program i zmusimy go do spojrzenia na kopię samego siebie, to będzie działać wiecznie". Ale Q powiedział to, gdy spojrzał na samo R. Tak więc to, co Q faktycznie powiedział to: "tak, jeżeli uruchomimy R i zmusimy go, aby spojrzał na kopię samego siebie, to będzie działał wiecznie". Tak więc: Je±li R biegn±ce na kopii siebie samej nie biegnie wiecznie, to biegnie wiecznie. To jest niemożliwe.

Jeśli uruchomimy R i każemy mu spojrzeć na kopię samego siebie, to Q odpowiedział "nie, jeśli uruchomimy ten program i każemy mu spojrzeć na kopię samego siebie, to nie będzie działał wiecznie". Ale Q powiedział to, gdy spojrzał na samo R. Więc to, co Q faktycznie powiedział to: "nie, jeżeli uruchomimy R i zmusimy go, aby spojrzał na kopię samego siebie, to nie będzie działał wiecznie". Tak więc: Je±li R biegn±ce na kopii siebie samego biegnie wiecznie, to nie biegnie wiecznie. To też jest niemożliwe.

Nieważne, co się stanie, dostaniemy niemożliwą sytuację. Zrobiliśmy coś złego i musimy się dowiedzieć, co to było. Większość rzeczy, które zrobiliśmy, nie były złe. Nie możemy powiedzieć, że "robienie programu, który patrzy na kopię siebie samego, jest złe", ani "patrzenie na to, co powiedział inny program, a następnie wejście w pętlę, jeśli powiedział jedną rzecz, i zatrzymanie się, jeśli powiedział inną rzecz" jest złe. Nie ma sensu mówić, że nie wolno nam robić tych rzeczy. Jedyną rzeczą, którą zrobiliśmy, a która wygląda na to, że może być zła, jest udawanie, że program taki jak P istnieje w pierwszej kolejności. A ponieważ jest to jedyna rzecz, która może być zła, a coś musi być nie tak, to jest to. To jest dowód na to, że program taki jak P nie istnieje. Nie istnieje żaden program, który rozwiązuje problem zatrzymania.

Ten dowód został znaleziony przez Alana Turinga w 1936 roku.