Przeskocz do treści

Delta mi!

Loading

Problem Stopu

Tomasz Kazana

o artykule ...

  • Publikacja w Delcie: kwiecień 2017
  • Publikacja elektroniczna: 30 marca 2017
  • Autor: Tomasz Kazana
    Afiliacja: Instytut Informatyki, Uniwersytet Warszawski

Tak zwany Problem Stopu to problem decyzyjny, którego wejściem jest jakiś program Q i jakieś dane D; a którego rozwiązaniem (wyjściem) jest stwierdzenie, czy program Q uruchomiony na danych D zakończy swoje działania w skończonym czasie.

Twierdzenie. Problem Stopu jest nierozstrzygalny.

Dowód. Załóżmy nie wprost, że Problem Stopu jest rozstrzygalny, a więc, że istnieje program P(Q, D), który zawsze (a więc w skończonym czasie dla każdych danych) rozstrzyga Problem Stopu. Rozważmy teraz następujący program P', którego wejściem jest jakiś inny program X:

boolean P ’ (program X ) { if (P(X, X)) { while (true ) do {}; } //wymuszamy pętlenie się else { return true; } }

Będziemy się zastanawiać, czy wykonanie P'(P') zatrzyma się, czy nie.

obrazek

Najpierw załóżmy, że się zatrzyma. Wtedy oczywiście (z definicji P)
P(P', P') zwraca true. Jednak wówczas z kodu programu P' (spójrzmy na warunek po if) wynika, że P'(P') się pętli w nieskończoność. Sprzeczność.

Z drugiej strony: załóżmy, że P'(P') się nie zatrzyma. To jednak (znów analizujemy kod P') implikuje, że P(P', P') zwraca true, ale to przecież oznacza, że P'(P') się zatrzymuje. Ponownie uzyskaliśmy sprzeczność, co kończy dowód.