Halting Problem in the Style of Dr. Seuss

I found a proof in verse of the undecidability of the halting problem, in the
style of Dr Seuss, written by Geoffrey K. Pullum (@ I’m delighted that I have a reason to cite Pullum on my blog here, because he is a contributor to one of my favorite reads on the web, the Language Log.@). Amusing and clear at the same time.

SCOOPING THE LOOP SNOOPER: A proof that the Halting Problem is undecidable

If P warns of infinite loops, Q will quit;
yet P is supposed to speak truly of it!
And if Q’s going to quit, then P should say ‘Good.’
Which makes Q start to loop! (P denied that it would.)

Found via Philip Wadler’s blog.


About Mathias

Software development engineer. Principal developer of DrJava. Recent Ph.D. graduate from the Department of Computer Science at Rice University.
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply