可计算性与可判定性
可计算性理论研究算法问题解决的根本限制，划定了可以通过有效过程解决的问题与任何算法都无法判定的问题之间的界限。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
可计算性理论是研究哪些函数和判定问题可以通过有效过程计算的学科；如果某个算法总是能给出正确的“是”或“否”答案并停机，则该问题是可判定的；如果不存在这样的算法，则该问题是不可判定的。
Scope
该领域涵盖了有效计算的形式模型，例如图灵机；将这些模型与直观的算法概念等同起来的丘奇-图灵论题；包括停机问题在内的不可判定问题的存在性；用于在问题之间转移不可解性的归约；以及对超出可计算范围的问题进行分类的不可解度结构。
Sub-topics
Core questions
- 一个问题可被算法解决意味着什么？
- 是否存在任何算法都无法解决的明确定义的问题？
- 如何利用一个问题的不可解性来证明另一个问题的不可解性？
- 不可解问题如何根据其相对难度进行分类？
Key theories
- 图灵计算模型
- 图灵的抽象机器形式化了有效过程的概念，并被用来证明停机问题和一阶逻辑的判定问题是不可解的，从而确立了计算的内在限制。
- 不可判定问题的存在性
- 通过对角线论证，存在一些问题（最著名的是停机问题）是任何算法都无法判定的，因此不可判定性是一种普遍存在的结构特征，而非一种奇特现象。
- 计算模型的等价性
- 图灵机、λ演算和递归函数定义了完全相同的可计算函数类，这种收敛性是丘奇-图灵论题的基础。
Clinical relevance
不可判定性结果对软件工具所能保证的功能设定了严格限制：没有通用的算法可以判定任意程序是否停机、是否正确或是否没有某些错误，这就是为什么验证工具依赖于近似、受限语言和人工指导，而不是完全自动分析。
History
受希尔伯特判定问题（Entscheidungsproblem）的启发，丘奇和图灵于1936年独立证明了没有算法可以判定所有一阶逻辑，图灵的机器模型和丘奇的λ演算被证明是等价的。在接下来的几十年里，波斯特和克莱尼将该理论扩展到不可解度（degrees of unsolvability）的研究。
Key figures
- Alan Turing
- Alonzo Church
- Kurt Gödel
- Emil Post
Related topics
Seminal works
- turing1937
- church1936
- sipser2013
Frequently asked questions
- 可判定与不可判定之间有什么区别？
- 如果存在一个算法，对于每个输入都能始终停机并给出正确的“是”或“否”答案，则该问题是可判定的。如果不存在这样的算法，则它是不可判定的，如停机问题所证明的；一个不可判定问题可能仍然是可识别的，这意味着算法可以确认“是”的实例，但可能会在“否”的实例上永远运行。
- 不可判定性是否意味着这些问题永远无法解决？
- 这意味着没有一个单一的算法能够正确解决每个实例。在实践中，工具会处理受限情况，给出近似或保守的答案，或者解决许多实例，同时偶尔失败或寻求帮助，因此不可判定性塑造了解决问题的方式，而不是禁止所有进展。