跳至內容

圖靈歸約

維基百科,自由的百科全書

圖靈歸約可計算性理論中的一種歸約,若問題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.

外部連結