查看“︁可计算性理论”︁的源代码

{{NoteTA
|G1 = IT
}}
{{for|对于数理逻辑中的可计算性理论|递归论}}

在[[计算机科学]]中，'''可计算性理论'''（Computability theory）作为[[计算理论]]的一个分支，研究在不同的[[计算模型]]下哪些[[算法]]问题能够被解决。相对应的，计算理论的另一块主要内容，[[计算复杂性理论]]考虑一个问题怎样才能被''有效的''解决。

== 历史与递归论的联系 ==
== 计算模型 ==
[[图灵机]]和[[邱奇－图灵论题]]

== 图灵机的可计算性理论 ==
我们考虑关于图灵机的可计算性理论。本节中，固定字符集是{0, 1}，<math>{0, 1}^*</math>是所有有限长度字符串的集合。一个语言即是<math>{0, 1}^*</math>的一个子集。

一个语言L是可以被图灵机所枚举（enumerate）的，如果存在一个图灵机<math>M</math>，使得输入是L中的串时，M输出“接受”；而对非L中的串，M输出“拒绝”或'''不停机'''。而一个语言L'是可以被图灵机所决定（decide）的，如果存在一个图灵机M'，使得输入是L中的串时，M输出“接受”；而对非L中的串，M输出“拒绝”。注意这里的区别在于，对于图灵机决定的语言，我们需要在所有输出上，该图灵机都要停机。

=== 可计算性等级 ===

这样我们可以定义可计算性等级：所有的语言的集合，记为All；递归可枚举语言，即可以被图灵机枚举的语言的集合，记为RE；递归语言，即可以被图灵机决定的语言的集合，记为R。可见<math>R\subseteq RE\subseteq All</math>，即形成'''可计算性等级'''。那么产生相关的问题即是两个包含关系是不是严格的，即是否有在All而不在RE中的语言，以及在RE而不在R中的语言。[[阿兰·图灵]]在1930年代的工作表明这两个包含关系都是严格的，即可以证明存在语言L_d，是不能被图灵机所枚举的，以及存在语言L_u，是不能被图灵机所决定的。证明的主要思想是[[對角論證法]]。

=== 停机问题 ===
停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：给定一个程序P和输入w，程序P在输入w下是否能够最终停止。

=== PCP问题 ===

[[波斯特对应问题]]（Post's correspondence problem）。

=== 不可解度 ===
[[不可解度]]的概念定义了不可解的集合之间的相对计算难度。例如，不可解的停机问题显然比任何可解的集合都要难，然而同样不可解的“元停机问题”（即所有具备停机问题的[[预言机]]的停机问题）却要难过停机问题，因为具备元停机问题的预言机可以解出停机问题，然而具备停机问题的预言机却不能解出元停机问题。

== 更强的模型 ==
=== 带神谕的图灵机（[[预言机]]） ===

== 定理 ==
* [[波斯特对应问题|波斯特定理]]
* [[克莱尼–波斯特定理]]
* [[弗里德堡–穆奇尼克定理]]
* [[波斯纳–罗宾逊定理]]
* [[跳躍逆轉定理]]

==外部链接==
*[http://www1.chkd.cnki.net/kns50/XSearch.aspx?KeyWord=%E5%8F%AF%E8%AE%A1%E7%AE%97%E6%80%A7%E7%90%86%E8%AE%BA 可计算性理论]{{dead link|date=2017年12月 |bot=InternetArchiveBot |fix-attempted=yes }}

[[Category:计算理论]]