Problém zastavenia

Problém zastavenia (angl. halting problem) je úloha teórie vyčísliteľnosti, ktorá môže byť neformálne zadaná takto: Ak poznáte zdrojový kód programu a jeho vstup, rozhodnite, či program zastaví, alebo či pobeží navždy bez zastavenia.

V roku 1936 Alan Turing dokázal, že všeobecný algoritmus, ktorý by riešil problém zastavenia pre všetky vstupy všetkých programov, neexistuje. Problém zastavenia sa preto označuje ako algoritmický nerozhodnuteľný problém.

Náčrt dôkazu

Nerozhodnuteľnosť problému zastavenia sa dá dokázať sporom.

• Počiatočný predpoklad: Predpokladajme, že problém zastavenia sa dá rozhodnúť. To znamená, že existuje nejaký program Zastaví(program, vstup), ktorý je univerzálnym riešením problému zastavenia.
  Ten funguje tak, že ak volanie program(vstup) po konečnom počte krokov skončí, potom Zastaví(program, vstup) vráti hodnotu ANO, v opačnom prípade (ak by sa volanie program(vstup) zacyklilo) vráti hodnotu NIE.
• Skonštruujme program Paradox(x), ktorý sa zámerne zacyklí, ak volanie programu Zastaví(x, x) vráti ANO, a zastaví sa, ak volanie programu Zastaví(x, x) vráti NIE.
• Teraz sa spýtajme, čo je výsledkom volania Paradox(Paradox).
• Predpokladajme na chvíľu, že Zastaví(Paradox, Paradox) vracia ANO. Z definície programu Paradox potom vieme, že sa Paradox(Paradox) zacyklí. Podľa definície programu Zastaví ale platí, že ak Paradox(Paradox) zacyklí, potom musí Zastaví(Paradox, Paradox) vracať NIE. Došli sme k sporu.
• Predpokladajme na druhej strane na chvíľu, že Zastaví(Paradox, Paradox) vracia NIE. Z definície programu Paradox potom vieme, že sa Paradox(Paradox) zastaví. Podľa definície programu Zastaví ale platí, že ak Paradox(Paradox) zastaví, potom musí Zastaví(Paradox, Paradox) vracať ANO. Opäť sme došli k sporu.
• Pretože sme vyčerpali všetky možnosti a vždy došli k sporu, musí byť nepravdivý počiatočný predpoklad. Z toho vyplýva, že program Zastaví(program, vstup), tak ako bol definovaný, neexistuje.

Pozri aj

• Gödelove vety o neúplnosti

Externé odkazy

• Čo je to nenaprogramovateľné? na serveri Root.cz