计算机科学

首页 > 计算机科学

图灵归约

2018-08-28 09:58:19     所属分类:递归论

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

上一篇:图灵完全性
下一篇:互递归
相关推荐