Problém zastavení

Haltingův problém je problém z oblasti informatiky. Jedná se o problém, kdy se díváme na počítačový program a zjišťujeme, zda program poběží věčně, nebo ne. Říkáme, že program "řeší problém zastavení", pokud se dokáže podívat na jakýkoli jiný program a říci, zda tento jiný program poběží navždy, nebo ne.

Například takovýto program:

while True: pokračovat;

se bude opakovat donekonečna, ale program

while False: pokračovat;

se velmi rychle zastaví.

Existuje program, který řeší problém zastavení? Ukázalo se, že ne. Tuto skutečnost dokážeme tak, že ukážeme, že pokud existuje program, který řeší problém zastavení, pak se stane něco nemožného. Prozatím se tedy budeme chovat, jako by program, který řeší problém zastavení, skutečně existoval. Zde je P funkce, která vyhodnotí funkci F (volanou s argumentem I) a vrátí true, pokud poběží věčně, a false v opačném případě.

def P(F, I): if F(I) runs forever: return True; else: return False;

P se může podívat na libovolný program a zjistit, zda poběží věčně, nebo ne. Pomocí P vytvoříme nový program, který nazveme Q. Q se podívá na jiný program a pak odpoví na následující otázku: "Pokud spustíme tento program a necháme ho podívat se na kopii sebe sama, poběží navždy?". Můžeme vytvořit Q, protože máme P. Stačí říct Q, aby vytvořil nový program, který je starým programem, který se dívá sám na sebe, a pak pomocí P zjistit, zda nový program poběží navždy, nebo ne.

def Q(F): return P(F, F);

Nyní vytvoříme další program R. R se podívá na jiný program a zeptá se Q na jeho odpověď. Pokud Q odpoví "ano, pokud spustíme tento program a přimějeme ho podívat se na kopii sebe sama, bude běžet navždy", pak se R zastaví. Pokud Q odpoví "ne, pokud spustíme tento program a necháme ho podívat se na kopii sebe sama, nebude běžet věčně", pak R vstoupí do nekonečné smyčky a poběží věčně.

def R(F): if Q(F): return; //terminate else: while True: continue; //loop forever

Nyní se podíváme na to, co se stane, když přimějeme R podívat se na kopii sebe sama. Mohou se stát dvě věci: buď se zastaví, nebo poběží navždy.

Pokud spuštění programu R a přimění ho, aby se podíval na kopii sebe sama, neběží věčně, pak Q odpověděl "ano, pokud spustíme tento program a přimějeme ho, aby se podíval na kopii sebe sama, bude běžet věčně". Ale Q to řekl, když se díval na samotný R. Takže Q ve skutečnosti řekl: "ano, pokud spustíme program R a přimějeme ho, aby se díval na kopii sebe sama, bude běžet věčně". Takže: Pokud R spuštěné na kopii sebe sama neběží věčně, pak běží věčně. To je nemožné.

Pokud spuštění programu R a jeho prohlížení kopie sebe sama trvá věčně, pak Q odpověděl "ne, pokud spustíme tento program a necháme ho prohlížet kopii sebe sama, nebude trvat věčně". Ale Q to řekl, když se díval na samotný R. Takže Q ve skutečnosti řekl: "ne, pokud spustíme R a přimějeme ho, aby se díval na kopii sebe sama, nebude běžet věčně". Takže: Pokud R spuštěné na kopii sebe sama běží věčně, pak neběží věčně. To je také nemožné.

Ať se stane cokoli, dostaneme se do neřešitelné situace. Něco jsme udělali špatně a musíme zjistit, co to bylo. Většina věcí, které jsme udělali, nebyla špatná. Nemůžeme říci, že "to, že se program podívá na kopii sebe sama, je špatně", nebo že "to, že se podíváme na to, co řekl jiný program, a pak přejdeme do smyčky, pokud řekl jednu věc, a zastavíme se, pokud řekl jinou věc", je špatně. Nemá smysl říkat, že tyto věci nesmíme dělat. Jediné, co jsme udělali a co vypadá, že by mohlo být špatně, je to, že jsme předstírali, že program jako P vůbec existuje. A protože to je jediná věc, která by mohla být špatná, a něco špatné být musí, je to právě toto. Toto je důkaz, že program jako P neexistuje. Neexistuje žádný program, který by řešil problém zastavení.

Tento důkaz nalezl Alan Turing v roce 1936.

Otázky a odpovědi

Otázka: V čem spočívá problém Halting?

A: Haltingův problém je problém v informatice, který se zabývá počítačovým programem a určuje, zda program poběží věčně, nebo ne.

Otázka: Jak poznáme, že program řeší problém zastavení?

Odpověď: Říkáme, že program "řeší problém zastavení", pokud se může podívat na jakýkoli jiný program a říci, zda tento jiný program poběží navždy, nebo ne.

Otázka: Lze nějak dokázat, že žádný takový program neexistuje?

Odpověď: Ano, tím, že ukážeme, že kdyby takový program existoval, pak by se stalo něco nemožného. Tento důkaz nalezl Alan Turing v roce 1936.

Otázka: Co dělá program P?

Odpověď: P je funkce, která vyhodnocuje jinou funkci F (volanou s argumentem I) a vrací true, pokud běží věčně, a false v opačném případě.

Otázka: Co dělá Q?

O: Q se podívá na jiný program a pak odpoví na otázku, zda spuštění téhož programu na sobě samém povede k nekonečné smyčce. Dělá to tak, že pomocí P provede vyhodnocení dané funkce F.

Otázka: Co dělá R?

Odpověď: R se podívá na jiný program a požádá Q o odpověď na tento konkrétní program. Pokud Q odpoví "ano, pokud spustíme tento program a necháme ho podívat se na kopii sebe sama, bude běžet donekonečna", pak se R zastaví; pokud však Q odpoví "ne, pokud spustíme tento program a necháme ho podívat se na kopii sebe sama, nebude běžet donekonečna", pak R vstoupí do nekonečné smyčky a poběží donekonečna.

Otázka: Co se stane, když přimějete R, aby se podíval sám na sebe?

Odpověď: Mohou se stát dvě věci - buď se R zastaví, nebo poběží donekonečna - ale oba výsledky jsou podle toho, co bylo dokázáno o neexistenci programů jako P, nemožné, takže někde na cestě vedoucí k tomu, aby se R podíval sám na sebe, se muselo něco pokazit.