Problem stopu

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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ść[edytuj | edytuj kod]

 Zobacz też: rozstrzygalność.

Nie istnieje uniwersalny algorytm rozstrzygający problem stopu dla wszystkich algorytmów. 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ż[edytuj | edytuj kod]