A 2-MINUTE PROOF OF THE 2nd-MOST IMPORTANT THEOREM OF THE 2nd MILLENUIUM

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.


DOWNLOAD THE PROOF [(1/3 page) of plain text]


Added March 15, 2002: Nachum Dershovitz has an even more succinct rewriting (note pun!) of this:
(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 and Shalosh B. Ekhad's Personal Journal

Doron Zeilberger's List of Papers

Doron Zeilberger's Home Page