[资料，科普，感慨] 不可判定 Undecidable  （关联：“自然运算”）

一、不可判定 undecidable

   由于既不能正式证明也不能证明，因此不可判定。

   Not decidable as a result of being neither formally provable nor unprovable.

二、可判定的 decidable

https://plato.stanford.edu/entries/goedel-incompleteness/

   非正式地说，可判定性意味着有一个机械过程，使人们能够决定（理论语言的）任意给定句子是否是一个定理。

   Informally, being decidable means that there is a mechanical procedure which enables one to decide whether an arbitrary given sentence (of the language of the theory) is a theorem or not.

参考资料：

[1] Undecidable, Weisstein, Eric W., MathWorld--A Wolfram Resource

https://mathworld.wolfram.com/Undecidable.html

[2] Gödel’s Incompleteness Theorems, 2020-04-02, Stanford Encyclopedia of Philosophy

https://plato.stanford.edu/entries/goedel-incompleteness/

   Such an independent, or “undecidable” (that is, neither provable nor refutable in F) statement GF in 

F is often called “the Gödel sentence” of F.

   Church’s Theorem

   First-order predicate logic is undecidable.

   Informally, being decidable means that there is a mechanical procedure which enables one to decide whether an arbitrary given sentence (of the language of the theory) is a theorem or not.

[3] 2022-01-20，逻辑/logic/周礼全、诸葛殷同撰，杜国平修订，中国大百科全书，第三版网络版[DB/OL]

https://www.zgbk.com/ecph/words?SiteID=1&ID=89210&Type=bkzyb&SubID=52011

   克伽自在的《真理如意珠》为新正理的代表作。该书包括现量（感觉知识）、比量（推理知识）、喻量（据公认知识推断待知事物）和言量（权威言论）4篇，重点阐述认识论、逻辑和类似语言哲学的内容。

[4] 2024-12-03，计算模型/models of computation/眭跃飞，中国大百科全书，第三版网络版[DB/OL]

https://www.zgbk.com/ecph/words?SiteID=1&ID=305744&Type=bkzyb&SubID=81691

   这里的不可判定性是指不能证明也不能否证。

   哥德尔不完全性定理是说：存在皮亚诺算术中的一个公式,使得在皮亚诺算术的标准模型中是真的，但是在皮亚诺算术中是不可证明的。

   哥德尔不完备性定理说明了形式化方法的局限性。

[5] 2024-12-05，计算机科学中的逻辑/logics in computer science/眭跃飞，中国大百科全书，第三版网络版[DB/OL]

https://www.zgbk.com/ecph/words?SiteID=1&ID=218532&Type=bkzyb&SubID=81639

   1930年，美籍奥地利数学家K.哥德尔证明了该形式证明系统是完备的，并于1934年证明了：在一个形式系统内证明该形式系统是否协调的是不可判定的。这里的不可判定性是指不能证明也不能否证。这是哥德尔不完全性定理的第二种形式。哥德尔不完全性定理是说：存在皮亚诺算术中的一个公式，使得在皮亚诺算术的标准模型中是真的，但是在皮亚诺算术中是不可证明的。由哥德尔完全性定理， 在皮亚诺算术系统中也是不可证明的。

[6] 2024-12-05，程序验证/program verification/冯新宇，中国大百科全书，第三版网络版[DB/OL]

https://www.zgbk.com/ecph/words?SiteID=1&ID=232425&Type=bkzyb&SubID=81609

   程序验证是一种排除程序中的错误，提高软件质量的重要技术。

   此外，由于大多程序验证问题是不可判定的，因此程序验证很难完全自动化地进行，需要人的大量手工劳动（提供并证明引理、插入注释、提供抽象等），使得验证的开销较大。

[7] 2022-01-20，集合论/set theory/郭世铭，杜国平，中国大百科全书，第三版网络版[DB/OL]

https://www.zgbk.com/ecph/words?SiteID=1&ID=229360&Type=bkzyb&SubID=104156

   更重要的是研究集合论形式公理系统的元数学性质——集合论的模型、各公理之间的关系、各系统之间的关系、各种不可判定语句，以及集合论研究过程中所提出的种种新方法和新问题。

[8] 2023-03-29，信息安全/information security/张焕国，中国大百科全书，第三版网络版[DB/OL]

https://www.zgbk.com/ecph/words?SiteID=1&ID=39257&Type=bkzyb&SubID=81357

   可计算性的理论告诉我们：一般意义上，对于给定的授权系统是否安全这一问题是不可判定问题，但是一些受限的授权系统的安全问题又是可判定问题。例如，著名的停机问题是不可判定问题，而许多具体程序的停机问题却是可判定的。由此可知，一般计算机病毒的检测是不可判定问题，而许多具体软件的计算机病毒检测又是可判定问题。这就说明了可计算性理论是信息系统安全的理论基础之一。

[9] 2025-05-24，概率自动机/probabilistic automata/张立军，中国大百科全书，第三版网络版[DB/OL]

https://www.zgbk.com/ecph/words?SiteID=1&ID=229957&Type=bkzyb&SubID=81610

   对于确定有穷自动机和概率自动机，语言等价问题是多项式时间可判定的。有穷自动机语言包含问题是可判定的，然而，概率自动机语言性包含问题却是不可判定的，即使限定其状态个数。另外，有穷自动机识别的语言都是正则语言，但概率自动机所识别的语言不一定不是正则的。

[10] 2022-01-20，空间关系/spatial relation/舒红，中国大百科全书，第三版网络版[DB/OL]

https://www.zgbk.com/ecph/words?SiteID=1&ID=226449&Type=bkzyb&SubID=148914

   然而，人类记忆限度（奥卡姆剃刀思维经济性原则）和人类空间常识追求认知有效性（高阶谓词逻辑的不可判定性），数学逻辑追求理论表达精细（复杂对象之间空间关系高精度高分辨率的拓扑度量组合理论表达），这两者难以同时兼顾是导致当前空间关系的复杂理论研究和朴素实际应用脱节局面的根本原因。

[11] 2022-01-20，量子算法/quantum algorithm/孙晓明，中国大百科全书，第三版网络版[DB/OL]

https://www.zgbk.com/ecph/words?SiteID=1&ID=46832&Type=bkzyb&SubID=81678

   在经典计算机中的不可判定问题在量子计算机中仍不可判定。有趣的地方在于求解一些问题时，量子算法比经典算法更快。量子算法通常在量子计算的电路模型中进行描述，该量子电路作用在一些输入量子比特上并且在一个测量之后结束。

[12] Philosophy of Mathematics, 2022-01-25, Stanford Encyclopedia of Philosophy

https://plato.stanford.edu/entries/philosophy-mathematics/

   Some of the researchers who seek to decide the continuum hypothesis think that it is true; others think that it is false. But there are also many set theorists and philosophers of mathematics who believe that the continuum hypothesis not just undecidable in ZFC but absolutely undecidable, i.e. that it is neither provable (in the informal sense of the word) nor disprovable (in the informal sense of the word) because it is neither true nor false. If the mathematical universe is a set theoretic multiverse, for instance, then there are equally models that make the continuum hypothesis true and equally good models that make it false, and there is no more to be said (Hamkins, 2015).

以前的《科学网》相关博文链接：

[1] 2025-7-29 21:11，[资料，科普，感慨] 布里丹之驴 Buridan's Ass

https://blog.sciencenet.cn/blog-107667-1495729.html

[2] 2025-07-06 22:43，[科普，笔记] “本体觉 proprioception”（第六感）、一见钟情 （关联：“自然运算”）

https://blog.sciencenet.cn/blog-107667-1492620.html

[3] 2024-01-04 22:49，[请教，讨论] 什么是超过“图灵机”能力的更强的计算机？

https://blog.sciencenet.cn/blog-107667-1416691.html

[4] 2024-03-31 22:43，[小资料] 丘奇-图灵论题（The Church-Turing thesis）

https://blog.sciencenet.cn/blog-107667-1427697.html

[5] 2024-07-02 22:41，[偶感，随笔，科普] 抽象（逻辑）思维的局限性（关联：丘奇-图灵论题 The Church-Turing thesis ）

https://blog.sciencenet.cn/blog-107667-1440701.html

[6] 2024-06-27 22:43，[小资料，笔记，计算] 楚泽论题（Zuse's thesis）

https://blog.sciencenet.cn/blog-107667-1440026.html

[7] 2024-01-07 22:42，[搜集，小资料] 理论计算机模型的名字

https://blog.sciencenet.cn/blog-107667-1417022.html

[8] 2024-10-22 22:21，[打听，笔记] 推导符号公式的局限性：从数学、心理学到哲学

https://blog.sciencenet.cn/blog-107667-1456506.html

[9] 2024-12-24 22:51，[科普，惊悚] 演绎推理的局限性：芝诺的“运动场悖论”、“阿基里斯追龟悖论” paradoxes of Zeno

https://blog.sciencenet.cn/blog-107667-1465885.html

感谢您的指教！

感谢您指正以上任何错误！

感谢您提供更多的相关资料！