Problem stopu

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.

Nierozstrzygalność

Nie istnieje uniwersalny algorytm rozstrzygający czy dowolny program się zatrzyma, 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))?

• Jeżeli wywołanie zapętli się, to stop zwróci nie, czyli procedura test zatrzyma się, co przeczy założeniom o zapętleniu się wywołania test(test)
• Jeżeli wywołanie zatrzyma się, to 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.

Zobacz też

• twierdzenie Gödla
• pracowity bóbr