by Doron Zeilberger
Written: Oct. 4, 1998
All the numerous proofs that I have seen of Turing's revolutionary theorem that there is no algorithm that inputs a Turing machine (TM) and outputs true if the input TM halts and false otherwise, are either too tedious (e.g. Turing's original proof that had to define computers and programming from scratch), and/or too technical (using jargon like recursive functions etc.) and/or too long-winded (e.g. Roger Penrose's in `The Emperor's new mind').
A corollary is that all the above renditions are boring. A very non-boring proof is given by Greg Chaitin in his classic `The Limits of Mathematics'. But his approach suffers from another, even worse than boredom, drawback. It assumes that real numbers exist, and takes as a starting point Cantor's `proof' that the so-called real numbers are uncountable. As we all know, but some of us refuse to admit, real numbers do not exist, since they involve the actual infinity. Of course Chaitin believes in the existence of non-constructive numbers, since his pet number, Omega, is non-constructive.
Here we present a 2-minute proof of an equivalent statement that uses Maple instead of TMs, and that is EXCITING and EDUCATIONAL, and more importantly Glatt-Kosher for Constructivists and Finitists like myself.
Note added 11/16/98: I just bought a copy of Arturo Sangalli's masterpiece, `The importance of being fuzzy', and there you can find, among many other fascinating things, a short and sweet proof of Turing's Halting Theorem phrased in the original TM language (app. 3). So I am retracting my previous statements. Still it is not as short as my rendition.
(define (c f) (if (halt f f) (c f) 1)) if (halt c c)=T then (c c) diverges; if (halt c c)=F then (c c) returns 1.
Doron Zeilberger's List of Papers
Doron Zeilberger's Home Page