Turing computability and related topics re-visited
Joe Engel
Tuesday, November 12, 2002 15:00-16:00,
Room 145, NIST North (820)
Gaithersburg
Tuesday, November 12, 2002 13:00-14:00,
Room 4511
Boulder
Abstract:
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
exist.
The same CTM operating on any initial infinitely long computable tape
prints a well ordered denumerably infinite set of all ComputableTuring
Tapes.
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
halts,
only tapes that can be produced by any valid Comprehensive Turing
Machine.
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
sets.
NEITHER OF THE ABOVE RESULTS IS OBVIOUS.
HOW THESE RESULTS WERE ARRIVED AT WILL BE DISCUSSED
BRIEFLY DURING THIS PRESENTATION.
Contact: R. F. BoisvertNote: Visitors from outside NIST must contact
Robin Bickel; (301) 975-3668;
at least 24 hours in advance.
|
