关于对于数理逻辑中的可计算性理论，请见「
递归论」。
在计算机科学中，可计算性理论（Computability theory）作为计算理论的一个分支，研究在不同的计算模型下哪些算法问题能够被解决。相对应的，计算理论的另一块主要内容，计算复杂性理论考虑一个问题怎样才能被有效的解决。
历史与递归论的联系 编辑
计算模型 编辑
图灵机的可计算性理论 编辑
我们考虑关于图灵机的可计算性理论。本节中，固定字符集是{0, 1}， 是所有有限长度字符串的集合。一个语言即是 的一个子集。
一个语言L是可以被图灵机所枚举（enumerate）的，如果存在一个图灵机 ，使得输入是L中的串时，M输出“接受”；而对非L中的串，M输出“拒绝”或不停机。而一个语言L'是可以被图灵机所决定（decide）的，如果存在一个图灵机M'，使得输入是L中的串时，M输出“接受”；而对非L中的串，M输出“拒绝”。注意这里的区别在于，对于图灵机决定的语言，我们需要在所有输出上，该图灵机都要停机。
可计算性等级 编辑
这样我们可以定义可计算性等级：所有的语言的集合，记为All；递归可枚举语言，即可以被图灵机枚举的语言的集合，记为RE；递归语言，即可以被图灵机决定的语言的集合，记为R。可见 ，即形成可计算性等级。那么产生相关的问题即是两个包含关系是不是严格的，即是否有在All而不在RE中的语言，以及在RE而不在R中的语言。阿兰·图灵在1930年代的工作表明这两个包含关系都是严格的，即可以证明存在语言L_d，是不能被图灵机所枚举的，以及存在语言L_u，是不能被图灵机所决定的。证明的主要思想是對角論證法。
停机问题 编辑
停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：给定一个程序P和输入w，程序P在输入w下是否能够最终停止。
PCP问题 编辑
波斯特对应问题（Post's correspondence problem）。
不可解度 编辑
不可解度的概念定义了不可解的集合之间的相对计算难度。例如，不可解的停机问题显然比任何可解的集合都要难，然而同样不可解的“元停机问题”（即所有具备停机问题的预言机的停机问题）却要难过停机问题，因为具备元停机问题的预言机可以解出停机问题，然而具备停机问题的预言机却不能解出元停机问题。
更强的模型 编辑
定理 编辑
外部链接 编辑
可计算性理论, 关于对于数理逻辑中的, 请见, 递归论, 在计算机科学中, computability, theory, 作为计算理论的一个分支, 研究在不同的计算模型下哪些算法问题能够被解决, 相对应的, 计算理论的另一块主要内容, 计算复杂性理论考虑一个问题怎样才能被有效的解决, 目录, 历史与递归论的联系, 计算模型, 图灵机的, 可计算性等级, 停机问题, pcp问题, 不可解度, 更强的模型, 带神谕的图灵机, 预言机, 定理, 外部链接历史与递归论的联系, 编辑计算模型, 编辑图灵机和邱奇, 图灵论题图. 关于对于数理逻辑中的可计算性理论 请见 递归论 在计算机科学中 可计算性理论 Computability theory 作为计算理论的一个分支 研究在不同的计算模型下哪些算法问题能够被解决 相对应的 计算理论的另一块主要内容 计算复杂性理论考虑一个问题怎样才能被有效的解决 目录 1 历史与递归论的联系 2 计算模型 3 图灵机的可计算性理论 3 1 可计算性等级 3 2 停机问题 3 3 PCP问题 3 4 不可解度 4 更强的模型 4 1 带神谕的图灵机 预言机 5 定理 6 外部链接历史与递归论的联系 编辑计算模型 编辑图灵机和邱奇 图灵论题图灵机的可计算性理论 编辑我们考虑关于图灵机的可计算性理论 本节中 固定字符集是 0 1 0 1 displaystyle 0 1 nbsp 是所有有限长度字符串的集合 一个语言即是0 1 displaystyle 0 1 nbsp 的一个子集 一个语言L是可以被图灵机所枚举 enumerate 的 如果存在一个图灵机M displaystyle M nbsp 使得输入是L中的串时 M输出 接受 而对非L中的串 M输出 拒绝 或不停机 而一个语言L 是可以被图灵机所决定 decide 的 如果存在一个图灵机M 使得输入是L中的串时 M输出 接受 而对非L中的串 M输出 拒绝 注意这里的区别在于 对于图灵机决定的语言 我们需要在所有输出上 该图灵机都要停机 可计算性等级 编辑 这样我们可以定义可计算性等级 所有的语言的集合 记为All 递归可枚举语言 即可以被图灵机枚举的语言的集合 记为RE 递归语言 即可以被图灵机决定的语言的集合 记为R 可见R R E A l l displaystyle R subseteq RE subseteq All nbsp 即形成可计算性等级 那么产生相关的问题即是两个包含关系是不是严格的 即是否有在All而不在RE中的语言 以及在RE而不在R中的语言 阿兰 图灵在1930年代的工作表明这两个包含关系都是严格的 即可以证明存在语言L d 是不能被图灵机所枚举的 以及存在语言L u 是不能被图灵机所决定的 证明的主要思想是對角論證法 停机问题 编辑 停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题 该问题等价于如下的判定问题 给定一个程序P和输入w 程序P在输入w下是否能够最终停止 PCP问题 编辑 波斯特对应问题 Post s correspondence problem 不可解度 编辑 不可解度的概念定义了不可解的集合之间的相对计算难度 例如 不可解的停机问题显然比任何可解的集合都要难 然而同样不可解的 元停机问题 即所有具备停机问题的预言机的停机问题 却要难过停机问题 因为具备元停机问题的预言机可以解出停机问题 然而具备停机问题的预言机却不能解出元停机问题 更强的模型 编辑带神谕的图灵机 预言机 编辑定理 编辑波斯特定理 克莱尼 波斯特定理 弗里德堡 穆奇尼克定理 波斯纳 罗宾逊定理 跳躍逆轉定理外部链接 编辑可计算性理论 永久失效連結 取自 https zh wikipedia org w index php title 可计算性理论 amp oldid 63173164, 维基百科，wiki，书籍，书籍，图书馆，
文章
，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。