Problem stopu

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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]

Information icon.svg 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? Jeżeli test zatrzymuje się na danych test, to stop zwraca tak dla programu test uruchomionego z danymi test, czyli test zapętla się dla danych test, co jest sprzeczne z założeniem o skończoności działania stop. Z kolei jeżeli test zapętla się dla danych test, to stop zwraca nie dla programu test z danymi test, czyli test się zatrzymuje dla danych test, co stoi w sprzeczności z założeniem o zapętleniu się kombinacji tego programu i danych.

W ten sposób założenie o istnieniu programu stop prowadzi do sprzeczności, skąd wynika, iż problem stopu jest nierozstrzygalny.