Problém zastavení

Problém zastavení (halting problem) je úloha teorie vyčíslitelnosti, která může být neformálně zadána takto:

Znáte-li zdrojový kód programu a jeho vstup, rozhodněte, zda program zastaví, nebo zda poběží navždy bez zastavení.

V roce 1936 Alan Turing dokázal, že obecný algoritmus, který by řešil problém zastavení pro všechny vstupy všech programů, neexistuje. Problém zastavení se proto označuje jako algoritmicky nerozhodnutelný problém. Je však částečně rozhodnutelný, což lze ukázat simulací univerzálním Turingovým strojem, který zastaví, pokud simulovaný TS normálně či abnormálně zastavil.

Náčrt důkazu

Nerozhodnutelnost problému zastavení lze dokázat sporem.

Počáteční předpoklad: Předpokládejme, že problém zastavení lze rozhodnout. To znamená, že existuje nějaký program Zastaví(program, vstup), který je univerzálním řešením problému zastavení – předpokládáme tedy, že pokud tomuto programu předáme libovolný program a jeho vstup, pak program Zastaví v konečném čase vrátí odpověď takovou, že pokud by volání program(vstup) po konečném počtu kroků skončilo, pak Zastaví(program, vstup) vrátí hodnotu ANO, v opačném případě (pokud by se volání program(vstup) zacyklilo) vrátí hodnotu NE.
Následně zkonstruujme program Paradox(program), který zavolá Zastaví(program, program) a pokud toto volání vrátilo ANO, tak se záměrně zacyklí, a pokud vrátilo NE, tak ihned skončí.
Nyní se ptejme, co je výsledkem volání Paradox(Paradox).
Předpokládejme na chvíli, že Zastaví(Paradox, Paradox) vrací ANO. Z definice programu Paradox pak víme, že se Paradox(Paradox) zacyklí. Podle definice programu Zastaví ale platí, že pokud se Paradox(Paradox) zacyklí, pak musí Zastaví(Paradox, Paradox) vracet NE. Došli jsme ke sporu.
Předpokládejme na druhou stranu na chvíli, že Zastaví(Paradox, Paradox) vrací NE. Z definice programu Paradox pak víme, že se Paradox(Paradox) zastaví. Podle definice programu Zastaví ale platí, že pokud se Paradox(Paradox) zastaví, pak musí Zastaví(Paradox, Paradox) vracet ANO. Opět jsme došli ke sporu.
Protože jsme vyčerpali všechny možnosti a vždy došli ke sporu, musí být nepravdivý počáteční předpoklad. Z toho vyplývá, že program Zastaví(program, vstup), tak jak byl definován, neexistuje.

Diagonalizační důkazy

Tento princip důkazu se nazývá diagonalizace a ve svém důkazu jej používají i

Gödelovy věty o neúplnosti z matematické logiky („za jistých předpokladů žádná teorie prvního řádu, silnější než aritmetika, nemůže dokázat vlastní bezespornost“)
Cantorova věta z teorie množin z matematické logiky („žádnou množinu nelze bijektivně zobrazit na systém jejích podmnožin“)
Tvrzení, že množina reálných čísel je nespočetná (což je speciální případ Cantorovy věty)

Externí odkazy

Co je to nenaprogramovatelné? na serveru Root.cz