Turing computability and related topics re-visited
Tuesday, November 12, 2002 15:00-16:00,
1) A Comprehensive Turing Machine may be defined as one
that will print a well ordered set of Turing Tapes containing
every Tape that begins with any possible ordered set of 0's and 1's
of any given finite length n when operating on any given
initial computable tape of indefinite (infinite) length. Such Machines
The same CTM operating on any initial infinitely long computable tape
prints a well ordered denumerably infinite set of all ComputableTuring
2) There is no halting problem. This is accomplished by defining
any putative CTM that jams as a defective machine.
Such a machine is redundant, in any case, since it will print, before it
only tapes that can be produced by any valid Comprehensive Turing
Taken together these results have caused me to re-examine
Turing's demonstration of the unsolvability of Hilbert's problem,
as well as Cantor's demonstration of the existence of non denumerable
NEITHER OF THE ABOVE RESULTS IS OBVIOUS.
HOW THESE RESULTS WERE ARRIVED AT WILL BE DISCUSSED
BRIEFLY DURING THIS PRESENTATION.
Room 145, NIST North (820)
Tuesday, November 12, 2002 13:00-14:00,
Contact: R. F. Boisvert
Note: Visitors from outside NIST must contact
Robin Bickel; (301) 975-3668;
at least 24 hours in advance.