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 [1].@). Amusing and clear at the same time.
SCOOPING THE LOOP SNOOPER: A proof that the Halting Problem is undecidable [2]
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 [3].
