可计算性理论
可计算性理论研究哪些问题原则上可以通过算法解决，并根据其难度对不可解决的问题进行分类。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
可计算性理论，又称递归理论，是数理逻辑的一个分支，它精确地阐明了有效可计算函数的概念，研究了算法可以和不可以计算的集合和函数，并衡量了不可解问题的相对难度。
Scope
该领域涵盖了计算的形式模型和丘奇-图灵论题、可计算集和可计算可枚举集、停机问题等不可判定问题、衡量相对不可解性的可归约性和图灵度，以及根据量词复杂性分层定义性的算术层次。
Sub-topics
Core questions
- 函数或集合可计算意味着什么？
- 哪些自然问题是算法上不可判定的？
- 如何比较和排序不可解问题的难度？
- 逻辑复杂性如何与可计算性水平相对应？
Key theories
- 丘奇-图灵论题
- 有效可计算性的直观概念与图灵机可计算性一致，等价于递归函数和λ可定义函数，从而确立了算法的严格数学定义。
- 停机问题的不可解性
- 没有算法可以判断每个程序和输入是否会停机，这提供了第一个也是典型的不可判定问题的例子。
- 图灵度
- 图灵可归约性根据相对可计算性对集合进行排序，由此产生的度形成一个丰富的偏序，其结构，包括中间度的存在，是研究的核心对象。
Clinical relevance
可计算性理论划定了算法可解性的绝对边界，支撑着理论计算机科学，并提供了不可判定性结果，例如停机问题和字问题的不可解性，这些结果在数学中反复出现，并为计算复杂性理论提供了信息。
History
可计算性理论兴起于20世纪30年代，当时丘奇、图灵、克莱尼和波斯特通过λ演算、图灵机、递归函数和组合系统独立地形式化了有效过程的概念，所有这些都被证明是等价的。波斯特和克莱尼发展了度理论和算术层次，20世纪50年代引入的优先级方法推动了对可计算可枚举度的深入结构研究。
Key figures
- Alan Turing
- Alonzo Church
- Stephen Cole Kleene
- Emil Post
Related topics
Seminal works
- soare1987
- rogers1987
- cutland1980
Frequently asked questions
- 可计算性理论与复杂性理论相同吗？
- 不。可计算性理论关注一个问题是否可以被任何算法解决，而不考虑资源；而复杂性理论则关注一个可解问题需要多少时间或内存。可计算性划定了可解与不可解之间的界限；复杂性则对可解的一侧进行分级。
- 为什么丘奇-图灵论题不是一个定理？
- 它将一个非形式化的概念（有效可计算性）等同于一个精确的数学概念，因此无法被形式化证明。它的被接受是基于许多独立的形式化都收敛到同一类函数，这提供了强有力的证据而非证明。