Důkaz neřešitelnosti halting problemu, tak jak je podán v článku, je zjednodušený možná až moc, takže není úplně jasné, že je opravdu korektní. Funkce zastavi() potřebuje znát vnitřek testované funkce včetně všech dalších funkcí, které ta testovaná volá, k čemuž Céčková syntaxe moc nenavádí. Šlo by popsanou konstrukci zmodifikovat, aby místo funkcí předávala jejich zdrojáky, ale pak bychom museli ve funkci Q konstruovat zdroják funkce Q, což je sice pěkná hříčka (schválně si rozmyslete, jak by se to dělalo), ale je to zbytečná komplikace.
Korektně a snad srovnatelně srozumitelně by to šlo třeba takto:
Předpokládejme, že všechny funkce mají za parametry stringy a výsledkem funkce je zase jenom string. Dokážeme, že nelze naprogramovat funkci Halt(X,Y), která dostane za parametry X=zdrojový text nějaké funkce s jedním parametrem a Y=parametr pro tuto funkci a odpoví "ZASTAVI" resp. "NEZASTAVI", podle toho, zda X(Y) se zastaví resp. nezastaví.
Kdyby tomu tak bylo, lze zkonstruovat i funkci H(X), která zavolá zastavi(X,X) a zachová se přesně opačně (tedy pokud se funkce X na vstup rovný svému vlastnímu zdrojáku zastaví, pak H(X) se nezastaví a opačně). [Máme-li k dispozici zdroják funkce zastavi, vyrobíme z něj snadno zdroják funkce H.]
No jo, jenže H je také funkce jedné proměnné, takže jde zavolat na svůj vlastní zdroják, čímž uděláme totéž, co funkce Q v článku, a H se nemůže ani zastavit, ani nezastavit, což není možné.
Laskavý čtenář nechť si povšimne, že při konstrukci funkce H jsme nepotřebovali žádné speciální vlastnosti programovacího jazyka, jen to, že se v něm dají dělat podmínky a věčné cykly a skládat funkce. Proto i kdybychom si do jazyka přidali libovolně silné operace (a nezabývali se chvilku tím, zda jsou technicky realizovatelné -- pokud máte rádi matematiku, přimyslete si třeba možnost používat existenční kvantifikátory; původní halting problem by se pak snadno napsal jako "existuje x takové, že se simulace programu X zastaví po x krocích"), půjde udělat úplně stejná konstrukce a opět dokážeme, že i takovýhle silnější jazyk na nějaký problém nestačí.
Ještě odbočka: Samozřejmě by také šlo zkonstruovat jazyk, ve kterém by se všechny programy vždycky zastavily (třeba tak, že zavedeme povinnost před každým cyklem [rekurzivní volání je také cyklus] předem uvést, kolikrát se maximálně může provést, čili nahradit všechny cykly for-cykly). Jenže takový jazyk bude mít pro změnu jiné neřešitelné problémy, třeba v něm nepůjde napsat interpretr toho samého jazyka. A dokáže se to skoro stejně, jako jsme před chvílí dokázali neřešitelnost halting problemu:
Nechť I(X,Y) je interpretr funkcí s jedním parametrem, čili funkce, která pro zdroják X a parametr Y vrátí totéž, co X(Y). Pak existuje i Z(X)=I(X,X)+1 a pokud byla I for-cyklová funkce, je i Z taková (žádný cyklus jsme nepřidali). Jenže pak Z(Z) = I(Z,Z)+1 = Z(Z)+1 :-)
