- A Concurrent Affair - https://www.concurrentaffair.org -

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 [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].

[4] [5]Share [6]