Problem stopu – zagadnienie algorytmiczne odpowiadające, dla danego algorytmu, na pytanie, czy realizujący go program zatrzyma się (w skończonym czasie); pytanie może dotyczyć konkretnych danych wejściowych albo wszystkich możliwych. O programie, który zatrzymuje się dla wszystkich możliwych danych mówi się, że ma własność stopu.
Problem stopu bywa trudny do rozstrzygnięcia, przykładem może być sformułowany w prosty sposób problem Collatza, dla którego odpowiedź jest dotychczas nieznana.
Nie istnieje uniwersalny algorytm rozstrzygający czy dowolny program się zatrzyma[1], dowiedli to jednocześnie Alan Turing oraz Alonzo Church, dzięki utworzeniu uniwersalnych modeli obliczeniowych, odpowiednio maszyny Turinga oraz rachunku lambda. Jest to więc problem nierozstrzygalny. Otóż jeżeli istniałby taki program stop
, to mógłby on działać zgodnie z poniższym pseudokodem:
procedura stop(program, dane): jeżeli program(dane) zatrzymuje się, to zwróć tak, w przeciwnym przypadku zwróć nie.
Dla dowolnego programu program
i jego danych wejściowych dane
program stop
zatrzymuje się, po czym zwraca tak
w przypadku, gdy program
wykonany wejściem dane
zatrzymuje się, oraz zwraca nie
w przeciwnym przypadku. Korzystając z programu stop
można by jednak stworzyć nowy program test
, który dla dowolnego programu program
zatrzymuje się wtedy i tylko wtedy, kiedy program
zapętla się na swoim własnym kodzie podanym jako dane wejściowe; jego pseudokod miałby postać:
procedura test(program): jeżeli stop(program, program) = tak, to zapętl się.
Powstaje wtedy pytanie: czy program test
zatrzymuje się po otrzymaniu swojego własnego kodu jako danych wejściowych (czyli po wywołaniu test(test)
)?
stop
zwróci nie
, czyli procedura test
zatrzyma się, co przeczy założeniom o zapętleniu się wywołania test(test)
stop
zwróci tak
, czyli procedura test
zapętli się, co przeczy założeniom o zatrzymaniu się wywołania test(test)
oraz o rozstrzygalności problemu stopu przez procedurę stop;Powyższy dowód nie wprost zaprowadził nas do sprzeczności z początkowymi założeniami, z czego wynika, iż nie istnieje taki uniwersalny algorytm, który rozstrzyga problem stopu dla dowolnego algorytmu.