A 2-MINUTE PROOF OF THE 2nd-MOST IMPORTANT THEOREM OF THE 2nd MILLENIUM
By Doron Zeilberger [zeilberg@math.temple.edu]
Theorem: (Turing's No-Halting Theorem adapted to Maple) There is no Maple
procedure, A(m,n), that inputs positive integers m and n, and outputs true iff
the m-th Maple program (in length-then-lex. order) outputs at least n bits.
Proof (Turing, shrunk by DZ): Denote by P(m) the m-th Maple program, and by
P(m)[n] its n-th bit of output (if it exists). If A(m,n) exists
then the following is a valid Maple program:
T:=proc() local m: for m do if A(m,m) then print(1-P(m)[m]): else print(0):fi:
od:end: T();
Let it be the m0-th Maple program. Then, its m0-th output bit is both
P(m0)[m0] and 1-P(m0)[m0]. Contradiction. QED.