Problem stopu.html



Problemem stopu nazywamy sytuację, gdy dla danego algorytmu należy stwierdzić, czy program realizujący dany algorytm zatrzyma się. Pytanie może odnosić się albo do konkretnych danych wejściowych, albo do wszystkich możliwych danych. Jeśli program zatrzymuje się dla wszystkich danych, to mówimy, że ma własność stopu.

Problem stopu jest często bardzo trudny do rozstrzygnięcia dla konkretnych algorytmów. Np. dla problemu Collatza przedstawionego poniższym pseudokodem nie znamy odpowiedzi na pytanie o własność stopu.

  x:=x0
  repeat
    if x jest parzyste then 
      x := x/2
    else
      x := 3*x + 1
  until x = 1

Dotychczas dla wszystkich sprawdzonych doświadczalnie wartości x0 > 0 algorytm się zatrzymywał, jednak nie udało się udowodnić własności stopu dla dowolnej liczby x0.

edytuj Dowód nierozwiązywalności problemu stopu

W ogólności problem stopu nie jest rozstrzygalny, co oznacza, że nie istnieje uniwersalny algorytm rozstrzygający o innych algorytmach, czy mają własność stopu.

Załóżmy, że istnieje program S, który dla dowolnego programu P i danych D:

• zatrzymuje się i zwraca 1 jeżeli P zatrzymuje się na danych wejściowych D, oraz
• zatrzymuje się i zwraca 0 w przeciwnym razie.

Korzystając z programu S, można napisać nowy program T, który dla dowolnego programu P zatrzymuje się wtedy i tylko wtedy, kiedy P zapętla się na swoim własnym kodzie podanym jako dane wejściowe. Program T można schematycznie zapisać tak:

  T(P): 
    if S(P,P)=1 then loop
    else stop

Pytanie: czy program T zatrzymuje się po otrzymaniu swojego własnego kodu jako danych wejściowych? Jeżeli T zatrzymuje się na danych T, to S zwraca 1 dla programu T i danych T, czyli T się pętli na danych T - sprzeczność. Z kolei jeżeli T się pętli na danych T, to S zwraca 0 dla programu T i danych T, czyli T się zatrzymuje na danych T - znowu sprzeczność.

Wynika z tego, że założenie o istnieniu programu S o podanych własnościach było błędne. Innymi słowy, problem stopu jest nierozstrzygalny.