Authors: Katie Hafner and Matthew Lyon
Chapter #5: pages 136 – 159.
On page 139, Steve Crocker talks about when the concept of a computer programming “loop” finally became clear to him. He felt like he finally understood why “Archimedes [would] to run down the street naked yelling, ‘Eureka!’”. I wonder what Crocker would say today when 21st century computer science would tell him that computers are limited and some problems are undecidable. What would he say when they tell him that the Turing Machine thought up by Alan Turing in 1936 is capable of solving the same problems in complexity (obviously it would take lot’s more time) as today’s best computers (Turing Machine).
Crocker states a little later on page 139:
There was something amazingly enticing about programming. You created your own universe and you were the master of it. The computer would do anything you programmed it to do. It was this unbelievable sandbox in which every grain of sand was under your control.”
The Halting Problem proves that this concept Crocker was enticed by is just not true on a fundamental level; however, I think many computer scientist still feel this way: that we will find a work-around to the halting problem and make our computers do whatever we want them to do. Until then, we must come to grips with the knowledge that computers cannot tell us if our code will loop forever or halt as was so proved by Pullum in his elementary proof: Scooping the Loop Snooper: A proof that the Halting Problem is undecidable.
“No general procedure for bug checks will do.
Now, I won’t just assert that, I’ll prove it to you.
I will prove that although you might work till you drop,
you cannot tell if computation will stop…”