求闻百科
搜索
切换搜索
切换菜单
切换个人菜单
查看“不可解度”的源代码
求闻百科,共笔求闻
更多语言
阅读
查看源代码
查看历史
页面
讨论
更多操作
←
不可解度
因为下列原因,您没有权限编辑本页。请逐条确认下列问题是否解决后再试。
您所请求的操作,仅限具有
注册用户
权限的
用户
执行。
若您尚未登录求闻百科账号,请您
登录
求闻百科账号后操作。
您尚未完成实名制验证,因此操作受限。请尽快
完成实名制验证
,或联系
裁决委员会
以
获取操作权限
。
注:若您是非中国大陆用户,您应当联络电子邮件staff
qiuwen.org以获得帮助。
您尚未完成
电子邮件确认
,因此操作受限,请尽快
完成电子邮件确认
。
若您无法完成前述手续,请参考
帮助文档
,或通过适当渠道请求管理员或裁决委员协助。
您可以查看和复制此页面的源代码。
若您无权编辑本页面,您可以
提出编辑请求
,提请有权限者代为编辑。
'''不可解度''',或'''图灵度'''(Turing degree),是[[数学逻辑]]的名词,尤其应用在[[可计算性理论]]中。 == 定义 == 假设一个[[图灵机]]程序可以随意获取[[自然数函数]]<math>g</math>的值(即使<math>g</math>不可计算),且该图灵机计算自然数函数<math>f</math>,则定义函数<math>f</math>由函数<math>g</math> '''[[图灵]]可计算''',记作<math>f\le_T g</math>。符合以上特点的图灵机称为具备函数<math>g</math>的[[预言机]]。若集合<math>B</math>的[[特征函数]]可计算集合<math>A</math>,则<math>A\le_T B</math>。 在计算机科学和数理逻辑中,自然数集合的图灵度或者不可解度是对此集合的算法不可解性的度量。图灵度在可计算理论中是根本性的概念,在可计算理论里,自然数集合通常被看作一个判定问题,而图灵度则给出了解决与此集合相连的判定问题的困难程度。 如果两集合<math>A,B</math>有同一不可解度(也即两者互相图灵可计算),则称两集合为'''图灵等价''',记作<math>A\equiv_T B</math>。图灵等价是一个[[等价关系]],其等价类称作不可解度。图灵可计算关系是所有不可解度的[[搜集]]上的[[偏序]]。所有可计算集合(也即图灵等价于[[空集]]的集合)的不可解度为<math>\mathbf{0}</math>(零度)。 所有不可解度的搜集记作<math>\mathcal{D} </math>。 == 图灵跳跃 == 图灵跳跃算符是不可解度上的[[算符]]。设<math>A</math>为一集合,则其不可解度的图灵跳跃<math>A^\prime</math>为所有[[停机问题|停机]]的具备集合<math>A</math>的预言机的集合的不可解度。 零度的图灵跳跃是[[停机问题]]的不可解度,也即<math>\mathbf{0}^\prime </math>。 == 图灵锥 == 设<math>C</math>为不可解度,则所有可计算<math>C</math>的不可解度的搜集<math>\operatorname{Cone}(C) := \{ D \in \mathcal{D} \;\vert\; D\ge_T C \}</math>叫做<math>C</math>上的图灵锥。 == 定理 == * [[波斯特定理]] * [[克莱尼–波斯特定理]] * [[弗里德堡–穆奇尼克定理]] * [[波斯纳–罗宾逊定理]] * [[跳跃逆转定理]] == 参考资料 == * {{cite book|language=en|author=Robert I. Soare|title=Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets|year=2004|publisher=Springer|isbn=9780387152998}} [[Category:递归论|B]]
返回
不可解度
。