可计算性理论

在计算机科学中，可计算性理论（Computability theory）作为计算理论的一个分支，研究在不同的计算模型下哪些算法问题能够被解决。相对应的，计算理论的另一块主要内容，计算复杂性理论考虑一个问题怎样才能被有效的解决。我们考虑关于图灵机的可计算性理论。本节中，固定字符集是{0, 1}， 0 , 1 ∗ {displaystyle {0,1}^{*}} 是所有有限长度字符串的集合。一个语言即是 0 , 1 ∗ {displaystyle {0,1}^{*}} 的一个子集。一个语言L是可以被图灵机所枚举（enumerate）的，如果存在一个图灵机 M {displaystyle M} ，使得输入是L中的串时，M输出“接受”；而对非L中的串，M输出“拒绝”或不停机。而一个语言L'是可以被图灵机所决定（decide）的，如果存在一个图灵机M'，使得输入是L中的串时，M输出“接受”；而对非L中的串，M输出“拒绝”。注意这里的区别在于，对于图灵机决定的语言，我们需要在所有输出上，该图灵机都要停机。这样我们可以定义可计算性等级：所有的语言的集合，记为All；递归可枚举语言，即可以被图灵机枚举的语言的集合，记为RE；递归语言，即可以被图灵机决定的语言的集合，记为R。可见 R ⊆ R E ⊆ A l l {displaystyle Rsubseteq REsubseteq All} ，即形成可计算性等级。那么产生相关的问题即是两个包含关系是不是严格的，即是否有在All而不在RE中的语言，以及在RE而不在R中的语言。阿兰·图灵在1930年代的工作表明这两个包含关系都是不严格的，即可以证明存在语言L_d，是不能被图灵机所枚举的，以及存在语言L_u，是不能被图灵机所决定的。证明的主要思想是对角线法。停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：给定一个程序P和输入w，程序P在输入w下是否能够最终停止。Post对应问题（Post's correspondence problem）。不可解度的概念定义了不可解的集合之间的相对计算难度。例如，不可解的停机问题显然比任何可解的集合都要难，然而同样不可解的“元停机问题”（即所有具备停机问题的预言机的停机问题）却要难过停机问题，因为具备元停机问题的预言机可以解出停机问题，然而具备停机问题的预言机却不能解出元停机问题。