Turing or Cantor: That is the Question

• URL: http://arxiv.org/abs/2604.10418v1
• Date: Sun, 12 Apr 2026 02:33:00 GMT
• Title: Turing or Cantor: That is the Question
• Abstract summary: It is demonstrated that there would not be Alan Turing's achievements without earlier seminal contributions by Georg Cantor.<n>It is proposed to introduce the measure of undecidability of problems unsolvable by Turing machines based on probability distribution of its input data.<n>It is also proposed to extend the Turing's work on infinite logics and Oracle machines to a class of super-Turing models of computation.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Alan Turing is considered as a founder of current computer science together with Kurt Godel, 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 is not equal to NP unanswered question for NP-complete class, has been answered negatively for U-complete class of complexity for undecidable problems.

Related papers

• The Imitation Game: Turing Machine Imitator is Length Generalizable Reasoner [71.41162392872393]
  This paper proposes Turing MAchine Imitation Learning (TAIL) to improve the length generalization ability of large language models.<n>TAIL synthesizes chain-of-thoughts (CoT) data that imitates the execution process of a Turing Machine by computer programs.<n>Without bells and whistles, TAIL significantly improves the length generalization ability as well as the performance of Qwen2.5-7B on various tasks.
  arXiv  Detail & Related papers  (2025-07-17T17:50:07Z)
• Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN [55.2480439325792]
  We show that every computation problem has an exact explicit equation that returns its solution.<n>We present a method to obtain an equation that solves exactly any problem, both inversion, constraint satisfaction and optimization.
  arXiv  Detail & Related papers  (2025-02-09T18:16:53Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation [49.1574468325115]
  We show how no (randomised) algorithm can determine the correct support sets (with probability $> 1/2$) of minimisers of LASSO when reading approximate input. For ill-posed inputs, the algorithm runs forever, hence, it will never produce a wrong answer. For any algorithm defined on an open set containing a point with infinite condition number, there is an input for which the algorithm will either run forever or produce a wrong answer.
  arXiv  Detail & Related papers  (2023-12-18T18:29:01Z)
• When Input Integers are Given in the Unary Numeral Representation [0.0]
  Many NP-complete problems take integers as part of their input instances. The "unarization" of numbers has been known to bring a remarkably different effect onto the computational complexity of the problems. We present numerous NP-complete (or even NP-hard) problems, which turn out to be easily solvable when input integers are represented in unary.
  arXiv  Detail & Related papers  (2023-12-07T15:09:24Z)
• Exceeding Computational Complexity Trial-and-Error Dynamic Action and Intelligence [0.0]
  Computational complexity is a core theory of computer science, which dictates the degree of difficulty of computation. In this paper, we try to clarify concepts, and we propose definitions such as unparticularized computing, particularized computing, computing agents, and dynamic search. We also propose and discuss a framework, i.e., trial-and-error + dynamic search.
  arXiv  Detail & Related papers  (2022-12-22T21:23:27Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Resource dependent undecidability: computability landscape of distinct Turing theories [0.0]
  We come up with a novel logical structure to formulate infinitely many problems for any pair of distinct Turing theories. Importantly, a class of other decision problems, such as the Halting one, remains unsolvable in all those theories.
  arXiv  Detail & Related papers  (2021-12-26T09:59:37Z)
• On Theoretical Complexity and Boolean Satisfiability [0.0]
  This thesis introduces some of the most central concepts in the Theory of Computing. We then explore some of its tractable as well as intractable variants such as Horn-SAT and 3-SAT. Finally, we establish reductions from 3-SAT to some of the famous NP-complete graph problems.
  arXiv  Detail & Related papers  (2021-12-22T10:13:34Z)
• Three computational models and its equivalence [0.0]
  The study of computability has its origin in Hilbert's conference of 1900, where an adjacent question, is to give a precise description of the notion of algorithm. We intend to fill this gap presenting the proof in a modern way, without forgetting the mathematical details.
  arXiv  Detail & Related papers  (2020-10-26T05:55:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.