8299308020

Dowód tw. 1.18 (szkic):

P w

fttl

s

TT

stop pętla

Łatwiej mówić o programach komputerowych analizujących inne programy, niż o maszynach Turinga, więc tego będę się trzymał. Ale dla pełnego dowodu należałoby rozważać maszyny Turinga.

Załóżmy więc, że problem stopu jest rozstrzygalny; mamy więc taki program komputerowy S w jakimś języku programowania, który jako dane bierze dowolny tekst programu P w tym języku oraz dowolne dane w, chwilę działa, następnie zatrzymuje się, i drukuje poprawną odpowiedź na pytanie, czy program P na danych w kończy obliczenie, czy też działa nieskończenie długo.

Skonstruujmy program R przez dobudowanie do programu S:

•    „podwajacza danych”, który tworzy dwie kopie podanych mu na wejściu danych, i doczepmy go do obu wejść programu; w ten sposób program R będzie wczytywał tekst programu P i sprawdzał, czy program P zatrzymuje się na swoim własnym tekście;

•    ślepą pętlę, i doczepmy ją do wyjścia „stop”.

Wobec tego, jeśli program P zatrzymuje się na swoim tekście, to program R na tekście programu P się zapętla; a w przeciwnym razie zatrzymuje się (i drukuje wynik „pętla”).

I w końcu sprawdźmy, jak zachowuje się program R na swoim własnym tekście; to znaczy wykonajmy go z R zamiast P. Są dwie możliwości:

•    albo R zatrzymuje się na R; wtedy S powinien dać wynik „stop”; tak więc R wchodzi w ślepą pętlę — sprzeczność;

•    albo R zapętla się na R; wtedy S powinien dać wynik „pętla”, ważne, że zatrzymać się i dać wynik; tak więc R zatrzymuje się — znowu sprzeczność.

W każdym przypadku dostajemy sprzeczność. To dowodzi, że oryginalny program S nie może istnieć.

□

Załóżmy, że istnieje funkcja s(p, w), która na każdych danych zatrzymuje się i stwierdza, czy obliczenie p(w) jest skończone. Definiujemy funkcję

fun r(p) :

if s(p,p) then {while true do od} /* ślepa pętla */ else return true; fi

Czy obliczenie r(r) się zatrzymuje?

Rys. 1.2: Programistyczna wersja dowodu tw. 1.18.

Wniosek 1.19

Żaden język, dla którego problem stopu jest rozstrzygalny, nie może mieć pełnej mocy maszyn Turinga (czyli: nie może być zupełny w sensie Turinga).

13