重新定义不可判定问题的复杂度，提出三类新计算类并推翻其等价性猜想。
Turing or Cantor: That is the Question
- 基于输入数据分布定义不可判定程度，量化问题难解性
- 提出U、D、H三类新复杂度类，扩展图灵机理论边界
- 证明U类问题中“等价于P≠NP”的猜想不成立，具突破性
本文揭示了康托尔集合论对图灵成就的基础性贡献。提出基于输入数据概率分布的不可判定性度量方法，以量化不可解实例与可解实例的比例。进一步将图灵的无限逻辑与预言机理论拓展至超图灵计算模型体系。首次定义三类针对图灵机不可判定问题的新复杂度类：U-complete（全知完备）、D-complete（对角化完备）和H-complete（超计算完备），其构想源于库克-列文的NP完全类。最终，针对不可判定问题的“等价于P≠NP”未决问题，在U-complete类中给出否定解答，为计算理论提供全新视角。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。