图灵归约

图灵归约是可计算性理论中的一种归约，若问题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.

外部链接

• NIST Dictionary of Algorithms and Data Structures: Turing reduction （页面存档备份，存于互联网档案馆）