Vysvětlení 1266 - Problém zastavení

Problém zastavení je úlohou z teorie vyčíslitelnosti. Cílem úlohy je nalézt odpověď na otázku, zda se obecný počítačový program při některé ze zcela libovolných kombinací vstupních dat může zastavit, nebo zda poběží donekonečna.

Alan Turing v roce 1936 dokázal, že napsat obecný algoritmus, který by na tuto otázku dokázal najít řešení, není možné.

Randall v dnešním comicsu předkládá podle vlastních slov "nadčasové řešení" této otázky - vytváří velice primitivní algoritmus, který proměnnou "ZastaviSe" za všech okolností nastavuje na hodnotu "True", tedy jinými slovy říká, že se dříve či později zastaví naprosto každý program. Jde samozřejmě o to, že Randall na celý problém nahlíží z praktického hlediska, nikoliv z čistě teoretického - při zohlednění praktických okolností je skutečně víceméně možné vyloučit možnost, že by jakýkoliv program mohl běžet nekonečně dlouhou dobu, přinejlepším může běžet opravdu velice dlouho. Ale počkáme-li dostatečně dlouhou dobu, nakonec se z toho či onoho praktického důvodu v reálném světě (tedy nikoliv v rámci teoretického modelu) každý program zastaví, protože v reálném světě nic nevydrží věčně.

Mouseover text nicméně právě toto tvrzení rozporuje, respektive v něm Randall tvrdí, že k němu vymyslel protiargument. Naráží ovšem na problém, jak svůj protiargument přesvědčivě prezentovat, protože v souladu s výše zmíněným v reálném světě víceméně popírá sám sebe a jeho platnost nelze ověřit.