Tuesday, December 4, 2012

Scooping the loop snooper

This was another discussion item I posted to the Udacity cs101 forum. To see the original post, see: http://forums.udacity.com/questions/2025383/scooping-the-loop-snooper#cs101

Your computer science education isn't complete until you've debugged an infinite loop or 2 or 3 or 4 or 5 or ... Perhaps you wondered why Python let's things run until a time limit is hit instead of detecting that your code has an infinite loop in it and issuing an error message before burning up a wad of CPU time. Well, it could try to do that, but here's proof that such detection can't work all the time. The problem is called the "Halting Problem". You can use Google search to find learned papers on the topic, but here's a simple proof in the style of Doctor Seuss.

http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html

Enjoy! Simple, but I do wish it had illustrations in his style. Where are Thing 1 and Thing 2 when you need them?

Drew