可计算性理论

维基百科,自由的百科全书
跳转至: 导航搜索

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

历史,与递归论的联系[编辑]

计算模型[编辑]

图灵机和图灵-丘奇论题[编辑]

图灵机的可计算性理论[编辑]

((非递归可枚举语言(non-recursively enumerable language),递归可枚举语言(recursively enumerable language/enumerable language),递归语言(recursive language/decidable language)。)本节内容基于《Introduction to Automata Theory, Languages, and Computation》(John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman著)。“/”后为《Introduction to Theory of Computation》(Michael Sipser著)中的名词。)

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

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

可计算性等级[编辑]

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

停机问题[编辑]

PCP问题[编辑]

Post对应问题(Post's correspondence problem)。

不可解度[编辑]

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

更强的模型[编辑]

带神谕的图灵机(预言机[编辑]

外部链接[编辑]