主流数学认为: “连续统假设在ZF(或GB)中是不可判定的,它即不能被证明,也不能被否证。”“Formal unsolvability is understood in the sense that there does not exist a formal derivation in the Zermelo–Fraenkel system ZF either for the continuum hypothesis or for its negation. ”
实际上,在理论计算机科学里,NPI(NP-Intermediate,NP里不属于P类且不属于NP-完全问题)的无穷化版本就是Cantor原本意义下的连续统假设: The hypothesis, due to G. Cantor (1878), stating that every infinite subset of the continuum R is either equivalent to the set of natural numbers or to R itself.
An equivalent formulation (in the presence of the axiom of choice) is:
“连续统假设”出来50多年之后,才有Gödel的【数学-逻辑系统】的不可判定性。由1931年的不完全性定理引发。 您说的【不可判定问题理论】,应该是Turing在1936年之后的理论计算机科学里的【不可判定问题理论】吧? 后者似乎是前者的具体化。 实际上,Gödel 也研究过计算机理论,据说【P对NP】最早是Gödel 于 20 March 1956 给 von Neumann的信件中提出的,可惜该信目前找不到原件了。 这个说法出自: Michael Sipser, The history and status of the P versus NP question, in Proceedings of ACM STOC'92, pp. 603–618, 1992. 以及一些网上资源。
图灵在他的重要论文《论可计算数及其在判定问题上的应用》(英语:On Computable Numbers, with an Application to the Entscheidungsproblem,1936年5月28日提交)里,对哥德尔1931年在证明和计算的限制的结果作了重新论述,他用现在叫做图灵机的简单形式装置代替了哥德尔的以通用算术为基础的形式语言。由于速度很慢,尽管没有一台图灵机会有实际用途,图灵还是证明了这样的机器有能力解决任何可想像的数学难题,如果这些难题是用一种算法来表达。现今,图灵机还是计算理论研究的中心课题。他继续证明了判定问题(Entscheidungsproblem)是没有答案的。他的证明首先展示了图灵机的停机问题(halting problem)是没有答案的,这是说不可能用一个算法来决定一台指定的图灵机是否会停机。尽管他的证明比阿隆佐·邱奇在λ演算方面相等的证明晚发表了几个月,图灵的著作是更易于理解和直观的。 他的通用(图灵)机的概念也是新颖的。这一通用机能够完成任何其他机器所能做的任务。这篇论文还介绍了可定义数的概念。 http://zh.wikipedia.org/wiki/%E8%89%BE%E4%BC%A6%C2%B7%E5%9B%BE%E7%81%B5