Problem stopu (Turing) — granice komputerów

Co się właśnie stało?

Dla programu A („licz do 100") od razu widać, że się zatrzyma. Dla programu B („while prawda") — że będzie działał w nieskończoność. Ale dla programu C („szukaj kontrprzykładu pewnej hipotezy") nie wiadomo: jeśli kontrprzykład istnieje, program go znajdzie i stanie; jeśli nie istnieje — będzie szukał wiecznie. A my z góry nie wiemy, który przypadek zachodzi.

Problem stopu (halting problem)

To fundamentalny wynik informatyki teoretycznej, udowodniony przez Alana Turinga w 1936 r. — w tej samej pracy, która zdefiniowała maszynę Turinga, matematyczny model komputera. Pytanie brzmi: czy da się napisać jeden uniwersalny program (detektor $H$), który dla DOWOLNEGO innego programu $P$ i jego danych rozstrzygnie, czy $P$ się kiedyś zatrzyma, czy będzie działał w nieskończoność?

Dowód przez sprzeczność (samo-odniesienie)

Turing udowodnił, że taki $H$ nie istnieje. Dowód jest genialny i przewrotny — w duchu paradoksu Russella. Załóżmy, że $H$ istnieje. Zbudujmy z niego przewrotny program $D$, który robi ODWROTNIE, niż twierdzi detektor:

Teraz uruchommy $D$ na nim samym — $D(D)$:

Otrzymujemy samo-sprzeczność: jeśli detektor twierdzi, że $D(D)$ się zatrzyma, to $D$ celowo wpada w pętlę (nie zatrzyma się) — i odwrotnie. Skoro założenie o istnieniu $H$ prowadzi do sprzeczności, taki program nie może istnieć. Problem stopu jest NIEROZSTRZYGALNY (ang. undecidable).

Co to znaczy w praktyce?

Konsekwencja jest głęboka: istnieją problemy zasadniczo nieobliczalne — których żaden komputer, choćby nieskończenie szybki, nigdy nie rozwiąże. To nie kwestia „za mało mocy", lecz fundamentalna granica tego, co algorytmy mogą osiągnąć. Dlatego nie da się napisać programu, który idealnie wykryje wszystkie wirusy, wszystkie błędy w cudzym kodzie albo wszystkie nieskończone pętle.

Po co Ci to na maturze:

Odkrycie Turinga — równolegle z twierdzeniami Gödla o niezupełności — wyznaczyło granice matematyki i informatyki, a zarazem założyło podwaliny pod całą informatykę (Turing jest uważany za jej ojca). To rozszerzenie tematu obliczalności: sam schemat dowodu przez sprzeczność i argument przekątniowy (samo-odniesienie) to klasyczne narzędzia logiki i teorii mnogości.

Zapamiętaj: istnieją problemy nierozstrzygalne algorytmicznie — żaden program nie rozwiąże problemu stopu dla wszystkich możliwych programów. To nie brak mocy obliczeniowej, lecz twarda, matematyczna granica obliczalności.