A double-whammy proof!
28May. 09
My logic lecturer sent an email — how long ago I couldn’t say, as I don’t check my uni email as often as I should — with a link in it to a poem written by Geoffrey K. Pullum at the University of Edinburgh.
Why is this poem a double-whammy proof, you may ask? Well, first off, it’s very clever, as it’s a poem that actually doubles as a proof that the halting problem is undecidable! What’s the second thing it proves then? I’ll let you see for yourself — here’s an extract from the beginning:
“No general procedure for bug checks succeeds.
Now, I won’t just assert that, I’ll show where it leads:
I will prove that although you might work till you drop,
you cannot tell if computation will stop.”
Clearly, this poem is proof that even though someone’s writing may be clever, that doesn’t automatically make it good. Sorry, Geoffrey!
You should all go and check it out anyway, for the sheer awesomeness of a proof of the undecidability of the halting problem in poem form.
For more info on the halting problem and computability, check out the following Stanford Encyclopedia of Philosophy articles:
*A warning — the article on the Church-Turing Thesis is quite vague and wandering, and may leave you more confused after reading it that when you began. Indeed, I can’t really recommend reading it and include it only for completeness (how ironic). Proceed at your own caution.
May 28th, 2009 at 10:20 am
Hey there, have read a little about Turing (as much as my poor head could absorb), but can you elaborate a little bit more on the undecidability of the halting problem. Ta
May 28th, 2009 at 4:22 pm
No worries — I’ll either write an article on it or comment more here later.
May 28th, 2009 at 6:35 pm
I live near a road named after Alan Turing. It is not sentient.
That is my claim to fame.
May 28th, 2009 at 9:16 pm
I live on a road called Somers. The surname of TV’s biggest arsehole.