I found a proof in verse of the undecidability of the halting problem, in the style of Dr Seuss, written by Geoffrey K. Pullum1. 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.
Footnotes:
- 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. [back]
