Často o svých programech potřebujeme ukázat spoustu podstatných vlastností. Například naprogramujeme řešení nějaké těžké úlohy a počítáme s tím, že poběží celou noc. Zajímalo by nás, jestli doběhne v pořádku, anebo je v kódu chyba a musíme ho ještě přepsat.

V některých případech jsou chyby vidět na první pohled. Když bychom ale chtěli nějaký rychlý a zaručený postup na hledání chyby, začíná to zavánět naivitou. Pojďme vystavět kus teorie, která tahle naše bláhová přání od základů zesměšní.

Problém zastavení

Spustíme počítačový program a zadáme mu nějaká vstupní data. Při pohledu hodně zdálky má ten program jenom dvě možnosti, co udělat:

  1. po nějaké době výpočet zastaví a vrátí nějaký výsledek, nebo
  2. nikdy neskončí – zatuhne v nekonečném cyklu.

Lidský popis

Napíšeme program, zadáme mu nějaký vstup a spustíme ho. Kdybychom měli jistotu, že program jednou skončí (ať už to bude trvat jakkoliv dlouho), tak stačí si počkat na výsledek. Jenže co když tenhle vstup zrovna způsobí, že se program zacyklí a nikdy neskončí? Bylo by fajn, kdyby počítač takové zacyklené programy hned objevil a zabil, ať neztrácíme čas. Nejenže si tohle přání nesplníme – naopak si ukážeme, že to nejde.

Důkaz bude oklikou: představíme si, že náš počítač umí odhalovat zacyklené programy, a ukážeme, jak se pomocí toho dá zbořit svět. Protože svět ještě existuje, tak tuhle možnost škrtneme, což znamená, že zacyklené programy odhalovat nejde. Tomuhle postupu se říká důkaz sporem.

Řekněme tedy, že máme program H, který umí řešit tuhle démonickou úlohu (H jako Halting problem). Programu H zadáme jiný program a nějaká vstupní data, a program H místo počítání výsledku prostě řekne, jestli ten druhý program se zadanými vstupními daty zastaví, nebo jestli se zacyklí.

V některých případech je jasně vidět, co se bude dít – ostatně, programy se snažíme psát tak, aby se nikdy nezacyklily. Pak jsou ale jiné, složitější případy; když chceme zjistit, co dělá složitý program, často nezbývá než ho spustit a podívat se na jeho výsledky. Z tohohle hlediska se zdá, jako by program H disponoval magickou mocí, která mu umožňuje programy spouštět nekonečně rychle. Když nějaký program zacyklí a běží nekonečně dlouho, program H to nekonečno dovede odhalit za nějakou rozumnou dobu, a vrátit odpověď. Problém je stručně řečeno v tom, že i program H má nějaký kód, a když ho spustíme sám na sebe, tak tím tuhle nekonečnou sílu zkratujeme. To už pochopitelně stačí k tomu, aby se zbořil vesmír.

Formální důkaz

Zaveďme si značení:

  1. P(I) ↓= 0 znamená, že program P se vstupními daty I vrátí nulu (nebo nějakou jinou hodnotu, podle potřeby) jako výsledek,
  2. P(I)↓ znamená prostě, že program jednou zastaví (výsledek nás nezajímá),
  3. P(I)↑ znamená, že program P se na vstupních datech I navěky zacyklí.
A dále:
  1. výrok Avýrok B je logická obdoba „rovná se“: když platí A, musí platit i B, a naopak,
  2. program Pprogram Q je programová obdoba „rovná se“: výpočet programu P na každých vstupních datech skončí stejným způsobem (zacyklí ve stejných případech, jinak vrátí stejný výsledek) jako výpočet programu Q.

Máme tedy ten podezřelý program H, který pro jakýkoliv program P a vstupní data I dovede řešit problém zastavení:
P(I)↓ ⟺ H(P, I) ↓= 1,
P(I)↑ ⟺ H(P, I) ↓= 0.
Pro úplnost řekněme, že chybné programy skončí hned – takže když v kódu P třeba chybí závorka, tak H(P, I) vrátí jedničku, ať jsou vstupní data I jakákoliv.

Trochu si pohrajeme s jeho zdrojovým kódem a vyrobíme program G, který se namísto vracení jedničky zacyklí:
P(I)↓ ⟺ G(P, I)↑,
P(I)↑ ⟺ G(P, I) ↓= 0.
Program G akorát spustí program H(P, I), a když mu vyjde jednička, tak skočí do nekonečného cyklu while(1) { }.

Ďábelskému plánu už překáží v cestě jenom skutečnost, že program G má dva parametry. Vyrobíme si obdobný program F, který dostane jako jediný parametr kód nějakého programu P, a ten použije zároveň i jako vstupní data:
P(P)↓ ⟺ F(P)↑,
P(P)↑ ⟺ F(P) ↓= 0.
Program F asi není vlastně k ničemu dobrý, ale to nevadí. Důležité je, jak moc je zlý.

Soukolí démonického stroje je připravené, stačí ho zapnout. Podívejme, co když programu F dáme jako parametr jeho vlastní kód:
F(F)↓ ⟺ F(F)↑,
F(F)↑ ⟺ F(F) ↓= 0.
V tom není žádná magie. Vzali jsme dva řádky z předchozího odstavce a místo každého P jsme tam dosadili F, jako bychom dosazovali neznámou do rovnice. Spustit program a dát mu jeho vlastní kód jako vstup samozřejmě jde, můžete zkusit třeba zazipovat program WinZip.

Vyšlo nám, že program F zastaví, když se zacyklí, a zacyklí, když vrátí nulu! To je nesmysl, takový program nemůže existovat. Úpravy, jakými jsme vyrobili F a G, jsou ale neprůstřelně korektní, takže problém je v samotněm programu H.