圖靈歸約

圖靈歸約是可计算性理论中的一種歸約，若問題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 （页面存档备份，存于互联网档案馆）

这是一篇與科技相關的小作品。您可以通过编辑或修订扩充其内容。 查 论 编