Computers LTD: Chapter 2 Review

A friend loaned me his copy of Computers LTD: What they Really Can't Do, by David Harel, and I've found it to be a great resource for explaining computability and complexity theory to a general audience.

Chapter 2 of this book discusses computability, covering the major results in this area.  Harel starts by introducing the tiling problem, which is easily understandable because it can be represented graphically.  This is the sort of problem that can be really vexing -- it seems like you ought to be able to devise an algorithms for arranging the tiles on a plane  -- yet it turns out to be undecidable.  This is a great way of revealing the idea of noncomputable problems, a basic theoretical result that may catch the amateur by surprise.

Representation of a Turing Machin

Harel then demonstrates the robustness of computability by explaining the concept of a Turing machine, a theoretical device developed by Alan Turing that can simulate the logic of any computer problem.  This leads to the Church-Turing thesis, which roughly states that everything that is computable may be computed by a Turing machine.  Although this is not a provable statement, the Church-Turing thesis leads us to believe that noncomputable problems don't result from a limitation of current languages and computing power -- they are very likely to be noncomputable even with future advances in these areas.

At this point, Harel introduces yet another wrinkle -- unbounded problems aren't the only ones that are noncomputable.  He discusses the domino snake problem and how this is decidable for an infinite plane but undecidable if limited to a half plane.  Even more remarkable, a footnote indicates how the problem is undecidable if just a single point is removed from the plane!

Harel then discusses two more undecidable problems -- program verification and the famous halting problem.  This helps the reader to grasp the scope of the problems that computers can't solve, while also introducing some very important history and theoretical results.  Harel explains that tiling and the halting problem are reducible to each other, meaning that if we had a magic solver for one, it would solve the other.  Surprisingly, while the halting problem can be reduced to program verification (a solution for the latter would work for the former), the converse is not true.    Thus some noncomputable problems are more difficult than others -- they are highly noncomputable.

The nice thing about this book is that these concepts are all explained at a high level, and though this glosses over some details, it renders the material available to a broad audience.  It's intriguing to find that computers can't solve all problems, and that these results are so well established.  It's interesting to ponder that there are hard limits to what humans can't know or do, giving us a sense of humility that is helpful in a technologically advanced age.

Those who are mathematically inclined might try reading Turing's original paper in which he developed the concept of the Turing machine: On Computable Numbers, With An Application To The Entscheidungsproblem, published in 1936.

If you would like to examine Turing machines in more detail, visit the Javascript turing machine site.