求闻百科
搜索
切换搜索
切换菜单
切换个人菜单
查看“圖靈歸約”的源代码
求闻百科,共笔求闻
更多语言
阅读
查看源代码
查看历史
页面
讨论
更多操作
←
圖靈歸約
因为下列原因,您没有权限编辑该页面。请逐条确认下列问题是否解决后再试。
您所请求的操作,仅限具有
注册用户
权限的
用户
执行。
若您尚未登录求闻百科账号,请您
登录
求闻百科账号后操作。
您尚未完成实名制验证,因此操作受限。请尽快
完成实名制验证
,或联系
裁决委员会
以
获取操作权限
。
注:若您是非中国大陆用户,您应当联络电子邮件staff
qiuwen.org以获得帮助。
您尚未完成
电子邮件确认
,因此操作受限,请尽快
完成电子邮件确认
。
若您无法完成前述手续,请参考
帮助文档
,或通过适当渠道请求管理员或裁决委员协助。
您可以查看和复制此页面的源代码。
若您无权编辑本页面,您可以
提出编辑请求
,提请有权限者代为编辑。
'''图灵归约'''是[[可计算性理论]]中的一种[[归约]],若问题A可图灵归约成问题B,是指若问题B的解答已经知道(Rogers 1967, Soare 1987),就可以解问题A,也可以解释为若一个演算法可以用来处理问题B,就可以处理问题A。较正式的说法,可被图灵归约成问题B的问题是指若存在问题B的[[預言机]],就可以求解的问题集合。图灵归约可以用在[[決定性问题]]及[[功能性问题]]。 == 相关条目 == * [[黑盒]] * [[图灵机]] * [[交互式证明系统]] * [[随机預言机]] == 参考资料 == * H. Rogers, 1967. Theory of recursive functions and effective computability. McGraw-Hill. * R. Soare, 1987. Recursively enumerable sets and degrees, Springer. == 外部链接 == * [https://xlinux.nist.gov/dads/HTML/turingredctn.html NIST Dictionary of Algorithms and Data Structures: Turing reduction] {{技术小作品}} [[Category:递归论]] [[Category:计算复杂性理论]] [[Category:艾伦图灵]]
返回
圖靈歸約
。