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.

Thu Oct 9 11:06:29 EDT 1997