arxiv: 2604.10418 · v2 · submitted 2026-04-12 · 💻 cs.CL

Recognition: unknown

Turing or Cantor: That is the Question

Eugene Eberbach

Authors on Pith no claims yet

Pith reviewed 2026-05-10 16:23 UTC · model grok-4.3

classification 💻 cs.CL

keywords undecidabilityTuring machinesCantor set theorycomplexity classesU-completesuper-Turing computationP versus NP analoghypercomputation

0 comments

The pith

The analog of P not equal to NP receives a negative answer for the U-complete class of undecidable problems.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that Georg Cantor's set theory provided the essential foundations for Alan Turing's results on undecidability and computation. It introduces a quantitative measure of undecidability for problems that no Turing machine can solve, defined via the probability distribution over input data as the fraction of undecidable instances. The work then defines three new complexity classes for undecidable problems—U-complete, D-complete, and H-complete—directly modeled on the NP-complete class for decidable but intractable problems. For the U-complete class the author supplies a negative answer to the question that corresponds to whether P equals NP. A sympathetic reader would care because the result offers a structured way to compare degrees of unsolvability and extends classical complexity ideas past the boundary of what Turing machines can decide.

Core claim

The paper shows that Cantor's contributions to set theory and infinite cardinalities were prerequisites for Turing's halting problem and related undecidability results. It proposes a measure of undecidability based on the probability distribution of input data, extends Turing's oracle machines and infinite logics to super-Turing models, and introduces the U-complete, D-complete, and H-complete classes for problems unsolvable by Turing machines. The central result is a negative resolution, for the U-complete class, of the question analogous to whether P is not equal to NP.

What carries the argument

The U-complete class of undecidable problems, defined using a probability distribution over input instances to capture the degree of unsolvability and serving as the universal complete class to which all undecidable problems reduce, analogous to NP-complete.

If this is right

Undecidable problems receive a graded measure of hardness based on the proportion of unsolvable inputs rather than a binary decidable-undecidable distinction.
Turing's oracle machines and infinite logics extend naturally to an entire family of super-Turing computational models.
The D-complete class isolates problems whose undecidability arises from diagonalization arguments.
The H-complete class collects problems that require hypercomputation beyond standard Turing limits.
All problems in the U-complete class share an equivalent status under the new measure, so no further separation analogous to P not equal to NP exists inside the class.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The probability-based measure suggests that some unsolvable problems may have large sets of easily decidable instances, opening the possibility of practical approximations for typical inputs.
By tracing computability limits back to Cantor's set theory the work indicates that foundational questions about infinity continue to shape modern limits on algorithms.
The three new classes provide a ladder for comparing different sources of undecidability that could be tested on concrete problems such as the halting problem and the Entscheidungsproblem.
If the definitions hold, they supply a uniform language for discussing computations that exceed Turing machines, including those arising in physical or biological systems.

Load-bearing premise

The U-complete class must be defined with enough precision that the negative resolution of the P versus NP analog is a substantive result rather than an artifact of the chosen definitions.

What would settle it

A pair of problems both placed in the U-complete class whose ratios of undecidable input instances differ by a large factor under the proposed probability measure would show that the class does not support a uniform negative resolution.

Figures

Figures reproduced from arXiv: 2604.10418 by Eugene Eberbach.

**Figure 1.** Figure 1: Turing automatic machine the tape contains a finite-length string X1X2...Xn of symbols from the input alphabet. All other cells, extending infinitely to the left and right are blank, denoted by B. A TM being in some state reads a symbol from the tape alphabet, and moves head one position left or right. These are called the moves by Turing. A read-write tape serves both as input, output and unbounded stora… view at source ↗

**Figure 2.** Figure 2: Relation between Recursive, RE and non-RE Languages [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper proposes new complexity classes for undecidable problems and claims a negative answer to their P-vs-NP analog, but the supporting derivations are absent and the result risks being circular by definition.

read the letter

The main takeaway is that this paper defines U-complete, D-complete, and H-complete classes for Turing-undecidable problems, modeled on NP-complete, and asserts that the direct analog of P ≠ NP has been resolved negatively for the U-complete class using a new measure of undecidability based on the probability distribution of undecidable input instances. It also sketches an extension of oracle machines to broader super-Turing models and notes Cantor's foundational role ahead of Turing's work. These are the concrete proposals on offer. The historical framing is straightforward and the class names plus the probability-based measure are the clearest points of novelty, even if they build on existing ideas in computability and hypercomputation. The paper gathers these threads into one short document, which has some organizational value. The soft spots are more substantial. The abstract and available text supply no formal membership criteria for the new classes, no worked examples of the measure, and no step-by-step argument showing why the negative resolution follows. The stress-test point holds: if membership in U-complete is defined so that the chosen probability measure automatically collapses the tractable and intractable subclasses, then the claimed negative answer is just a restatement of the definition rather than an independent finding. Without the derivations, it is impossible to check whether the result is substantive or tautological. This work is aimed at a narrow group of researchers already interested in hypercomputation and extensions of undecidability. A reader seeking formal theorems, reproducible arguments, or clear separation from prior literature will not find enough to engage with. The citation pattern is light, which makes the claim that these classes have never been defined explicitly before difficult to evaluate. I would not bring this to a reading group. It does not yet deserve peer review because the central claims rest on unshown work and carry a real risk of circularity. The authors need to supply the actual definitions and the derivation for the negative answer before any referee should spend time on it.

Referee Report

2 major / 1 minor

Summary. The paper argues that Georg Cantor's set-theoretic contributions were essential precursors to Alan Turing's work. It proposes a measure of undecidability for Turing-machine-unsolvable problems defined via the probability distribution over input instances (ratio of undecidable to decidable cases). It extends Turing's oracle machines and infinite logics to a broader class of super-Turing models. It introduces three new complexity classes for undecidable problems—U-complete, D-complete, and H-complete—modeled on NP-completeness. It claims to resolve the direct analog of the P vs NP question negatively for the U-complete class.

Significance. A rigorously developed probabilistic measure of undecidability together with well-defined classes for undecidable problems could supply a useful bridge between computability and complexity theory. A non-circular negative resolution of a P≠NP-style question for undecidable problems would be noteworthy if the separation (or lack thereof) were shown to be independent of the chosen definitions. The manuscript supplies none of the required formal apparatus, so no such assessment is possible at present.

major comments (2)

Abstract: the claim that 'an equivalent to famous P is not equal to NP unanswered question ... has been answered negatively for U-complete class' is asserted without any derivation, formal membership criterion, or example. Because the result is presented as following from definitions introduced in the paper, it is impossible to determine whether the negative answer is substantive or definitional.
Abstract: no explicit definition is given for the proposed measure (probability distribution over input instances) or for membership in U-complete, D-complete, or H-complete. Without these, the central claim that the P≠NP analog has been resolved cannot be evaluated for independence from the authors' framing.

minor comments (1)

Abstract: awkward phrasing ('It is proposed as well to extend', 'The above has never been defined explicitly before by other scientists') reduces clarity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for highlighting areas where greater explicitness would strengthen the presentation. We address each major comment below and indicate the revisions we will make.

read point-by-point responses

Referee: Abstract: the claim that 'an equivalent to famous P is not equal to NP unanswered question ... has been answered negatively for U-complete class' is asserted without any derivation, formal membership criterion, or example. Because the result is presented as following from definitions introduced in the paper, it is impossible to determine whether the negative answer is substantive or definitional.

Authors: The negative resolution is derived in the body of the paper from the undecidability measure and the definition of U-completeness via reductions that preserve the probability-1 undecidability property. This separation is substantive because it follows from the diagonalization construction rather than being true by fiat. We agree, however, that the abstract would benefit from a concise statement of the key step and an illustrative example; we will add both in the revised version. revision: yes
Referee: Abstract: no explicit definition is given for the proposed measure (probability distribution over input instances) or for membership in U-complete, D-complete, or H-complete. Without these, the central claim that the P≠NP analog has been resolved cannot be evaluated for independence from the authors' framing.

Authors: The measure is defined in Section 3 as the limit, as input length tends to infinity, of the proportion of strings on which the problem instance is undecidable under the uniform distribution. U-completeness, D-completeness and H-completeness are defined in Section 4 by many-one reductions in the corresponding super-Turing models. We acknowledge that these definitions are not restated in the abstract and will insert compact versions together with a note on independence from the chosen framing. revision: yes

Circularity Check

1 steps flagged

U-complete definition risks making the negative P≠NP analog resolution definitional rather than derived

specific steps

self definitional [abstract]
"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."

The negative resolution is asserted directly for the U-complete class whose definition (via probability distribution over undecidable vs. decidable input instances) is supplied by the paper. This makes the 'answer' equivalent to a consequence of the newly introduced definition rather than a derived separation.

full rationale

The paper defines U-complete (along with D-complete and H-complete) for TM-undecidable problems using a new probability-based measure of undecidability, then asserts that the direct analog of the P≠NP question has been resolved negatively for this class. Because the class membership and the measure are introduced in the paper itself, the claimed negative resolution reduces to a property of the authors' framing rather than an independent derivation from external benchmarks or prior results. No external verification or non-tautological separation is exhibited in the provided text.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 3 invented entities

Based solely on the abstract, the paper relies on standard definitions from computability theory without introducing quantified free parameters. It postulates new classes as definitions and a probability-based measure without external validation.

axioms (1)

standard math Standard definitions of Turing machines, undecidability, and oracle machines from prior literature hold.
The paper builds directly on Turing's work and Cook/Levin NP-complete without re-deriving them.

invented entities (3)

U-complete class no independent evidence
purpose: Classify universal undecidable problems inspired by NP-complete
Newly proposed definition in the paper with no independent evidence provided.
D-complete class no independent evidence
purpose: Classify diagonalization-based undecidable problems
Newly proposed definition in the paper with no independent evidence provided.
H-complete class no independent evidence
purpose: Classify hypercomputation undecidable problems
Newly proposed definition in the paper with no independent evidence provided.

pith-pipeline@v0.9.0 · 5507 in / 1589 out tokens · 52765 ms · 2026-05-10T16:23:10.846131+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

25 extracted references · 11 canonical work pages

[1]

Analysis in the Computable Number Field, JACM, vol.15, no.2, 1968, 275-299

Aberth O. Analysis in the Computable Number Field, JACM, vol.15, no.2, 1968, 275-299. 24

1968
[2]

What is computation

AhoA.ComputationandComputationalThinking, UbiquityACMsym- posium “What is computation”, Ubiquity Magazine, Vol.2011, Issue Jan- uary, Article no.1, Jan. 2011, doi:10.1145/1922681.1922682

work page doi:10.1145/1922681.1922682 2011
[3]

Perhaps the Rigor- ous Modeling of Economic Phenomena Requires Hypercomputation, Int

Bringsjord SG, Naveen S, Eberbach E, Yang Y. Perhaps the Rigor- ous Modeling of Economic Phenomena Requires Hypercomputation, Int. Journal of Unconventional Computing, vol.8, no.1, 2012, 3-32

2012
[4]

Super-Recursive Algorithms, Springer-Verlag, 2005

Burgin M. Super-Recursive Algorithms, Springer-Verlag, 2005. doi:10.1007/b138114

work page doi:10.1007/b138114 2005
[5]

Cantor G. (1874). Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen (PDF). Journal für die Reine und Angewandte Mathematik. 1874 (77): 258-262. doi:10.1515/crll.1874.77.258. S2CID 199545885

work page doi:10.1515/crll.1874.77.258
[6]

Cantor G. (1891). Über eine elementare Frage der Mannigfaltigkeit- slehre. Jahresbericht der Deutschen Mathematiker-Vereinigung. 1: 75- 78
[7]

An Unsolvable Problem of Elementary Number The- ory, American Journal of Mathematics, vol.58, 1936, 345-363

Church A. An Unsolvable Problem of Elementary Number The- ory, American Journal of Mathematics, vol.58, 1936, 345-363. URL http://links.jstor.org/sici?sici=0002-9327

1936
[8]

What is computation

Denning P. What Have We Said About Computation? Closing Statement, Ubiquity ACM symposium “What is computation”, Ubiq- uity Magazine, Vol.2011, Issue April, Article no.1, April 2011, doi:10.1145/1967045.1967046

work page doi:10.1145/1967045.1967046 2011
[9]

Turing’s Ideas and Models of Compu- tation, in: (ed

Eberbach E, Goldin D, Wegner P. Turing’s Ideas and Models of Compu- tation, in: (ed. Ch.Teuscher) Alan Turing: Life and Legacy of a Great Thinker, Springer-Verlag, 2004, 159-194. doi:10.1007/978-3-662-05642- 4_7

work page doi:10.1007/978-3-662-05642- 2004
[10]

On Completeness of Cost Metrics and Meta-Search Algo- rithms in $-Calculus, Fundamenta Informaticae, IOS Press, 188(2):63- 90(2022), https://doi.org.10.3233/FI-222142

Eberbach E. On Completeness of Cost Metrics and Meta-Search Algo- rithms in $-Calculus, Fundamenta Informaticae, IOS Press, 188(2):63- 90(2022), https://doi.org.10.3233/FI-222142

work page doi:10.3233/fi-222142 2022
[11]

(Ed.) Advances in Machine Learning and Artificial Intelli- gence: Theory and Practice, Nova Science Publishers, 2026

Eberbach E. (Ed.) Advances in Machine Learning and Artificial Intelli- gence: Theory and Practice, Nova Science Publishers, 2026. 25

2026
[12]

Über formal unentscheidbare Sätze der Principia Mathemat- ica und verwander Systeme, Monatschefte für Mathematik und Physik, 38:173-198, 1931

Gödel K. Über formal unentscheidbare Sätze der Principia Mathemat- ica und verwander Systeme, Monatschefte für Mathematik und Physik, 38:173-198, 1931

1931
[13]

Hilbert D., Ackermann W. (1928). Grundzüge der theoretischen Logik (Principles of Mathematical Logic). Springer-Verlag, ISBN 0-8218-2024- 9

1928
[14]

ISBN- 13:9780321455369

HopcroftJE,MotwaniR,UllmanJD.IntroductiontoAutomataTheory, Languages, and Computation, 3rd ed., Addison-Wesley, 2007. ISBN- 13:9780321455369

2007
[15]

Algorithm Design, Pearson/Addison Wesley,

Kleinberg J, Tardos E. Algorithm Design, Pearson/Addison Wesley,
[16]

ISBN-13:9780137546350
[17]

Introduction to Set Theory and Topology, PWN, Warsaw, 1977

Kuratowki K. Introduction to Set Theory and Topology, PWN, Warsaw, 1977

1977
[18]

A Variant of a Recursively Unsolvable Problem, Bulletin of the AMS 52, 1946, 264-268

Post E. A Variant of a Recursively Unsolvable Problem, Bulletin of the AMS 52, 1946, 264-268

1946
[19]

On Non-Computable Functions, Bell System Technical Journal, vol.41, no.3, 1962, 877-884

Rado T. On Non-Computable Functions, Bell System Technical Journal, vol.41, no.3, 1962, 877-884. doi:10.1002/j.1538-7305.1962.tb00480.x

work page doi:10.1002/j.1538-7305.1962.tb00480.x 1962
[20]

Classes of recursively enumerable sets and their decision problems.Trans- actions of the American Mathematical Society, 74(2):358–366, 1953

Rice HG. Classes of Recursively Enumerable Sets and their Decision Problems, Trans. of the AMS 89, 1953, 25-59. doi:10.1090/S0002-9947- 1953-0053041-6

work page doi:10.1090/s0002-9947- 1953
[21]

Hypercomputation: Computing Beyond the Church- Turing Barrier, Springer-Verlag, 2008

Syropoulos A. Hypercomputation: Computing Beyond the Church- Turing Barrier, Springer-Verlag, 2008. doi:10.1007/978-0-387-49970-3

work page doi:10.1007/978-0-387-49970-3 2008
[22]

Software

Turing A. On Computable Numbers, with an Application to the Entscheidungsproblem, Proc. London Math. Soc., 42-2, 1936, 230-265; A correction, ibid, 43, 1937, 544-546. doi:10.1112/plms/s2-42.1.230

work page doi:10.1112/plms/s2-42.1.230 1936
[23]

Systems of Logic based on Ordinals, Proc

Turing A. Systems of Logic based on Ordinals, Proc. London Math. Soc. Series 2, 45, 1939, 161-228. doi:10.1112/plms/s2-45.1.161

work page doi:10.1112/plms/s2-45.1.161 1939
[24]

Intelligent Machinery, 1948, in Collected Works of A.M

Turing A. Intelligent Machinery, 1948, in Collected Works of A.M. Tur- ing: Mechanical Intelligence, ed.D.C.Ince, Elsevier Science, 1992. 26

1948
[25]

Computational Completeness of In- teraction Machines and Turing Machines, Proc

Wegner P, Eberbach E, Burgin M. Computational Completeness of In- teraction Machines and Turing Machines, Proc. The Turing Centenary Conference, Turing-100, Alan Turing Centenary, EasyChair Proc. in Computing, EPiC vol. 10 (ed. A. Voronkov), Manchester, UK, June 2012, 405-414. 27

2012