Turing or Cantor: That is the Question Journal: ToC

Eugene Eberbach · 2026

Read Turing or Cantor: That is the Question Journal: ToC by Eugene Eberbach (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-10418.txt.

Introduction

Eberbach ties Turing's feats to Cantor's older work on sets and the roots of math. He scores how unsolvable a task is by the share of inputs no Turing machine can settle. Turing's infinite logics and oracle machines grow here into a full class of super Turing models. Three fresh classes sort undecidable tasks: U-complete, D-complete, and H-complete. For U-complete tasks, he settles the twin of the P versus NP query in the negative.

Catalog record

CREATOREugene Eberbach
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51277
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.10418

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Turing or Cantor: That is the Question Journal: ToC Eugene Eberbach Abstract Alan Turing is considered as a founder of current computer science together with Kurt Gödel, Alonzo Church and John von Neumann. In this paper multiple new research results are presented. It is demonstrated that there would not be Alan Turing’s achievements without earlier seminal contributions by Georg Cantor in the set theory and foundations of mathematics. It is proposed to introduce the measure of undecidability of problems unsolvable by Turing machines based on probability distribution of its input data, i.e., to provide the degree of unsolvabilty based on the number of undecidable instances of input data versus decidable ones. It is proposed as well to extend the Turing’s work on infinite logics and Oracle machines to a whole class of super-Turing models of computation. Next, the three new complexity classes for TM undecidable problems have been defined: U-complete (Universal complete), D-complete (Diagonalization complete) and H-complete (Hypercomputation complete) classes. The above has never been defined explicitly before by other scientists, and has been inspired by Cook/Levin NP-complete class for intractable problems. Finally, an equivalent to famous P ​ ? = N ​ P P\;?=\;NP unanswered question for N ​ P NP -complete class, has been answered negatively for U-complete class of complexity for undecidable problems. 1 Introduction Alan Turing was born in 1912, became an undergraduate in mathematics at King’s College, the University of Cambridge, England in 1931, and published a paper in 1936 whose model of Turing machines became a central basis for the theory of computing. This paper, entitled “On Computable Numbers with an Application to the Entsheidungsproblem” [ 21 ] was primarily a mathematical demonstration that computers could not model all mathematical problem solving. In his paper, Turing introduced his discrete state automatic machines ( a -machines, known currently as Turing machines) used to prove the undecidability of the famous decision Entscheidungsproblem of Hilbert whether mathematics is complete and all its statements (theorems) can be decided to be true or false. In this paper it is stressed the genius of Alan Turing in creation of digital programmable computers, formalization of algorithms, proving that his Turing machines cannot solve by finite means all problems, and mathematics is incomplete. Turing did that by inventing a new automatic machine model of computation (known now as Turing machine TM) and proving that some real numbers cannot be computed by TMs. The above follows directly from earlier work of Georg Cantor who proved that the cardinality of real numbers is strictly larger than the cardinality of integers. The job of Turing was simply to associate the number of all Turing machines with integers, and the number of all languages/problems with real numbers. That’s it - the rest is the history. The elegance and simplicity of Turing’s approach turned out to be equivalent to disproving the solvability of the famous Hilbert’s Entscheidungsproblem (decision problem) in mathematics and provided the limit to the algorithmic problem solving by computers. As the follow up of the Turing’s proof of the undecidability of Entscheidungsproblem three new complexity classes for TM undecidable problems have been defined: U-complete (Universal complete), D-complete (Diagonalization complete) and H-complete (Hypercomputation complete) classes. This paper concentrates on the famous Alan Turing’s blueprint from 1936 [ 21 ] fulfilling in computer science the function of providing the foundations of computers science and computers. For that paper alone, Alan Turing has been recognized as the father of computer science. If so, in this paper, it has been justified that perhaps another famous mathematician, Georg Cantor might be considered an implicit forgotten grandfather of computer science together with Charles Babbage and Wilhelm Leibnitz. [ 21 ] is a very interesting and strange paper. It is written almost entirely in plain English, it does not have an abstract, keywords, proper introduction with previous work done, explicit theorems and definitions, practically no references, it contains several errors (corrected later), no conclusions and future work despite that it is considered commonly as the starting point of the era of programmable digital computers. In the opinion of the author of this paper, Turing’s paper was (and still is) too original and unconventional to be accepted by the majority of current professional journals, because it violated several rigid formal requirements. The question remains open, how ingenious Turing’s paper really was that despite of all the above problems, it remains to be so tremendously successful and influential for so many years. The Entscheidungsproblem (decision problem), one of the most alluring conjectures in mathematics, proposed by the prominent mathematician David Hilbert in 1928 [ 13 ] . Hilbert’s conjecture that any mathematical proposition could be decided (proved true or false) by mechanistic logical methods was approved by many mathematicians, but was unexpectedly disproved by Gödel in 1931 [ 12 ] , who showed that for any formal theory, there will always be undecidable theorems outside of its reach (famous incompleteness theorem ). Mathematicians like Alonzo Church [ 7 ] and Turing [ 21 ] continued Gödel’s work, looking for alternate techniques for proving this undecidability result. Turing’s disproof of Hilbert’s Entscheidungsproblem was accepted by Gödel as better than his own proof, and was also accepted by Church as better than his own attempt to show that his \lambda -calculus could not prove the Entscheidungsproblem either [ 7 ] . Turing’s proof, provided in his 1936 paper [ 21 ] was based on a novel model of automatic machines ( a -machines), which can be built to carry out any algorithmic computation. Turing showed that despite their versatility, these machines cannot compute all real numbers (extended to functions of integers, functions of real/computable variables, computable predicates, etc.), in particular, he proved that the now-famous halting problem of the Universal Turing Machine (representing all Turing machines) is undecidable. Turing defined “computable” numbers at the beginning of his paper as the real numbers whose expressions as a decimal are calculable by finite means 1 1 1 Turing justified that by the fact that the human memory is neccesarily limited. However, it does not prevent us to think and operate with infinite objects, and that the contents of our memory fluctuates by forgetting and learning . In the 1960s, with the development of new ACM computer science curriculum based on algorithms, Turing Machines were chosen to fulfill a central role in computer science, because of its elegance and simplicity, and for many years they have been useful in that function. However, we forget typically that Turing was more concerned that the Entscheidungsproblem is not solvable, and mathematics cannot be fully described by recursive algorithms, rather than to propose or create the foundations of computer science. Turing himself did not accept Turing machines as a complete model for problem solving, proposing 3 other models of computation going beyond his a -machines, and its acceptance by theoreticians contradicted Turing’s view on this subject. The justification why we need new models of computation besides TMs are the following. In [ 8 ] Peter Denning expressed concerns that developments in non-terminating computation, analog computation, continuous computation, and natural computation may require rethinking the basic definitions of computation. He further stated that computation is the process that the machine or algorithm generates.

Read the complete text