可计算性理论

图灵机和邱奇－图灵论题

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

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

可计算性等级

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

停机问题

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

PCP问题

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

不可解度

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

带神谕的图灵机（预言机）

• 波斯特定理
• 克莱尼–波斯特定理
• 弗里德堡–穆奇尼克定理
• 波斯纳–罗宾逊定理
• 跳跃逆转定理

• 可计算性理论^{[永久失效链接]}