ITLApplied  Computational Mathematics Division
ACMD Seminar Series
Attractive Image NIST

Turing computability and related topics re-visited

Joe Engel

Tuesday, November 12, 2002 15:00-16:00,
Room 145, NIST North (820)
Tuesday, November 12, 2002 13:00-14:00,
Room 4511

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. Boisvert

Note: Visitors from outside NIST must contact Robin Bickel; (301) 975-3668; at least 24 hours in advance.

Privacy Policy | Disclaimer | FOIA
NIST is an agency of the U.S. Commerce Department.
Last updated: 2011-01-12.