图灵归约
来自维基百科,自由的百科全书
来自维基百科,自由的百科全书
图灵归约是可计算性理论中的一种归约,若问题A可图灵归约成问题B,是指若问题B的解答已经知道(Rogers 1967, Soare 1987),就可以解问题A,也可以解释为若一个算法可以用来处理问题B,就可以处理问题A。较正式的说法,可被图灵归约成问题B的问题是指若存在问题B的预言机,就可以求解的问题集合。图灵归约可以用在决定性问题及功能性问题。
这是一篇与科技相关的小作品。您可以通过编辑或修订扩充其内容。 |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.