形式陈述

带预言机 $A\subseteq\Sigma^*$$A\subseteq {\mathrm{\Sigma }}^{\ast }$ 的图灵机有专用查询带与查询状态，可在一步内获得“当前查询串是否属于 $A$$A$”的答案。由此定义相对可计算性和复杂性类 $P^A,NP^A$$P^A,N{P}^A$ 等。若问题 $B$$B$ 可由带 $A$$A$ 预言机的机器判定，记作 $B\le_T A$$B{\le }_{T}A$。预言机答案被视为原子操作，其内部计算成本不计入机器资源。

直觉

预言机把某个子问题封装成完美黑盒，用来研究“假如能免费解决 A，还能解决什么”以及归约可以怎样自适应地多次询问。

例子与边界

二分搜索式查询可让后一个问题依赖前一个答案，因此 Turing 归约比一次性映射归约更灵活。令预言机为停机问题可判定许多普通 TM 无法判定的问题，但仍存在相对该预言机不可判定的更高层问题。预言机是数学模型，不暗示现实设备能在一步解决不可计算问题。不同预言机下 $P^A$$P^A$ 与 $NP^A$$N{P}^A$ 的关系可不同，所以相对化证明不能单独解决 $P$$P$ 对 $NP$$NP$。

推论与应用

预言机模型组织 Turing 度、算术层级和复杂性层级，也用于识别证明技术的相对化障碍以及定义带子程序访问的算法类别。

参考资料

• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Chs. 0–10。
• Alan M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, 1936，Full paper。