next up previous
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?)

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.

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.

Harry Mairson
Thu Oct 9 11:06:29 EDT 1997