In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever. This sounds straightforward, but in 1936 Alan Turing proved that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. A key part of the proof was a mathematical definition of a computer and program, which became known as a Turing machine — the halting problem is undecidable over Turing machines (and was one of the first examples of a decision problem).

A delightful poetic proof of the halting problem being undecidable was published by Geoffrey Pullum in *Mathematics Magazine* (73, no. 4, 319-320) in 2000 — albeit with a minor error, since fixed — in the style of Dr. Seuss:

No general procedure for bug checks will do.

Now, I won’t just assert that, I’ll prove it to you.

I will prove that although you might work till you drop,

you cannot tell if computation will stop.For imagine we have a procedure called

P

that for specified input permits you to see

whether specified source code, with all of its faults,

defines a routine that eventually halts.You feed in your program, with suitable data,

andPgets to work, and a little while later

(in finite compute time) correctly infers

whether infinite looping behavior occurs.If there will be no looping, then P prints out ‘Good.’

That means work on this input will halt, as it should.

But if it detects an unstoppable loop,

then P reports ‘Bad!’ — which means you’re in the soup.Well, the truth is that

Pcannot possibly be,

because if you wrote it and gave it to me,

I could use it to set up a logical bind

that would shatter your reason and scramble your mind.Here’s the trick that I’ll use — and it’s simple to do.

I’ll define a procedure, which I will callQ,

that will useP’s predictions of halting success

to stir up a terrible logical mess.For a specified program, say

A, one supplies,

the first step of this program calledQI devise

is to find out fromPwhat’s the right thing to say

of the looping behavior ofArun onA.If

P’s answer is ‘Bad!’,Qwill suddenly stop.

But otherwise,Qwill go back to the top,

and start off again, looping endlessly back,

till the universe dies and turns frozen and black.And this program called

Qwouldn’t stay on the shelf;

I would ask it to forecast its run onitself.

When it reads its own source code, just what will it do?

What’s the looping behavior ofQrun onQ?If

Pwarns of infinite loops,Qwill quit;

yetPis supposed to speak truly of it!

And ifQ’s going to quit, thenPshould say ‘Good.’

Which makesQstart to loop! (Pdenied that it would.)No matter how

Pmight perform,Qwill scoop it:

QusesP’s output to makePlook stupid.

Whatever P says, it cannot predictQ:

Pis right when it’s wrong, and is false when it’s true!I’ve created a paradox, neat as can be —

and simply by using your putativeP.

When you positedPyou stepped into a snare;

Your assumption has led you right into my lair.So where can this argument possibly go?

I don’t have to tell you; I’m sure you must know.

Areductio: There cannot possibly be

a procedure that acts like the mythicalP.You can never find general mechanical means

for predicting the acts of computing machines;

it’s something that cannot be done. So we users

must find our own bugs. Our computers are losers!

“Scooping the Loop Snooper”: A proof that the Halting Problem is undecidable(2000)

Geoffrey K. Pullum