圖靈歸約
来自维基百科,自由的百科全书
Remove ads
来自维基百科,自由的百科全书
圖靈歸約是可计算性理论中的一種歸約,若問題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.