Turing or Cantor: That is the Question
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
How rare are the properties of binary relations?
Knoblauch (2014) and Knoblauch (2015) investigate the relative size of the collection of binary relations with desirable features as compared to the set of all binary relations using symmetric difference metric (Cantor) …
CantorNet: A Sandbox for Testing Geometrical and Topological Complexity Measures
Many natural phenomena are characterized by self-similarity, for example the symmetry of human faces, or a repetitive motif of a song. Studying of such symmetries will allow us to gain deeper insights into the underlying…
Data AugmentationCantor: Inspiring Multimodal Chain-of-Thought of MLLM
With the advent of large language models(LLMs) enhanced by the chain-of-thought(CoT) methodology, visual reasoning problem is usually decomposed into manageable sub-tasks and tackled sequentially with various external to…
Decision MakingLogical ReasoningVisual ReasoningA Cantor-Kantorovich Metric Between Markov Decision Processes with Application to Transfer Learning
We extend the notion of Cantor-Kantorovich distance between Markov chains introduced by (Banse et al., 2023) in the context of Markov Decision Processes (MDPs). The proposed metric is well-defined and can be efficiently …
reinforcement-learningReinforcement LearningTransfer LearningA PyTorch Library of Turing-Complete Neural Networks
We present a PyTorch package that compiles neural networks and their weights from Turing machine descriptions, producing models that exactly simulate the specified machine without any training. Given a transition functio…