Next: Conclusions Up: New proofs of old Previous: Russell's Paradox 


Undecidability of the Halting Problem

To show the Halting Problem can't be algorithmically solved,
We use diagonalization, a proof method that's evolved
Where Turing Machines are asked to run in modes of simulation,
On codes that represent themselves, an auto-copulation.

Suppose a TM we'll call Halt, with input that's a code
Of another machine M, and in addition is showed
An input x to M, whence Halt says (and it's always right)
Whether M did halt on x. (But how? Divine insight?)

Na to čo by sme tu radi ukázať vám chceli,
potrebujeme umenie diagonalizácie.
Týmto stroje Turingove zvláštne behať budú
Pracovať na vstupoch, ktoré
just ich kódom budú.


Uvažujme Turingov stroj, 
ten nech Halt sa volá
Vstupom nech sú inštrukcie
ďalšieho - M - stroja
Ak by nám do stroja M hneď
chcel vstup x hneď skočiť,
Potom Halt nám rečie, či má 
M na vstup x zastaviť.

Ešte tuto ďalší stroj D
do básne sa hodí,
jeho údel uvedieme
takto bude chodiť:
Toto D nech A nám zhltne
pričom A je krásne
číslom stroja Turingovho
kódované jasne.

D si samo nepomôže
tu v dôkaze sporom				nádhernom
zavolá si strojček Halt, či
A zhaltuje na sebe samom.
Ak odpoveď "nie" sa zjaví
nahodí si 1,
inak čosi iné sa nám 
ako výstup zjedná.

Toto čosi iné nie je
len tak z brucha dané
Radšej prirodzené číslo
ako bežiaci stroj v diaľave.


Let TM D, with input that's the code of machine A
Use Halt to find if A will halt on its own code, then say,
``If the answer's `no' I'll output 1, else fight the urge
To give another answer''-- better then that D diverge.

Viac uvádzať nebudeme
dôkaz zrejmý ?????
Zvyšok pekne prenecháme
tu na čitateľa.
Ak je pre Halt kód D daný
dilema tu býva
Halt nevie, či D zastaví
na kóde D - chyba!

Trikom tu je úkon chytrý
Gödela známa akcia
Naprieč ona rada chodí,
preto diagonalizácia.

V tomto akte D nám hodí
vo výstupe naviac bit
Čím tam mihom ťažkú prácu 
Halt-u ide pokaziť.
Hoci si stroj tu od práce 
pásku môže potrhať,
Diagonalizácia kontrapríklad
stvorí - čo sme mali dokázať.


Rather than recount the proof's denouement, we'll be prudent,
And leave the rest to you, dear reader, the ever-able student.
When Halt is given the code of D, it simply cannot know
If D does halt on its own code--but that's for you to show.

The trick is to diagonalize--D changed the bit returned
By Halt, thus contradicts its work, as its output is spurned.
No matter how a TM solves the Halting Problem, see,
Diagonalization makes a counter-example. Q.E.D.