预言机图灵机

预言机把某个语言的成员查询封装成一步完成的完美黑盒，用来研究“若能免费解决 $A$，还剩下哪些困难”，以及归约可以怎样自适应地多次询问。它不是现实中神奇的算法组件，而是相对计算能力的比较工具：同一台外层机器接上不同预言机，会得到不同的可计算集合。其重要作用是把绝对问题改写为依赖关系，并揭示某些证明技术无法仅靠黑盒方式解决。

二分搜索式查询可让后一个问题依赖前一个答案，因此 Turing 归约比一次性映射归约更灵活。预言机是数学模型，不暗示现实设备能在一步解决不可计算问题。

例如，带 $HAL{T}_{TM}$ 预言机的机器可以直接判定普通停机问题，还能解决一些原本不可判定的组合问题；但继续询问“带停机预言机的机器是否停机”会得到相对该预言机仍不可判定的更高层问题，并不能由原停机预言机自动解决。

把一次预言机查询算作一步，只衡量外层计算，不反映预言机本身的成本。相对化结论也不必在无预言机世界成立；不同预言机下 $P^A$ 与 $N{P}^A$ 的关系可以不同，确实存在预言机 $A,B$ 使 $P^A=N{P}^A$ 而 $P^B\ne N{P}^B$，所以相对化证明不能单独解决 $P$ 与 $NP$。

“查询”在其他模型中不是这项定义的别名。位查询模型公理库查询复杂度模型Query complexity model · Bit-query model将输入隐藏在坐标 oracle 后，只统计算法为确定函数值而读取的输入位置数量。读取一个有限输入的指定坐标，并把读取次数作为资源；统计查询公理库统计查询模型statistical query model · SQ model让学习器查询有界统计量的近似期望，并以查询数、容差和计算量衡量效率。返回有界统计量在未知分布下的近似期望，答案还带容差；性质测试公理库性质测试模型Property testing model · Property testing通过少量 oracle 查询区分完全满足性质的对象与到该性质至少相距 ε 的对象，并允许 gap 内行为任意。可使用坐标、邻接或抽样 oracle，只需完成成员与 $\epsilon$-far 之间的 gap decision。预言机图灵机查询的则是完整字符串是否属于固定语言，通常还允许依据前一答案自适应地生成下一串。若不同时写明 oracle 的答案语义、收费单位和正确性目标，这四种查询复杂度不能比较。

预言机模型扩展 图灵机公理库图灵机Turing machine通过有限控制、可读写纸带和移动读写头刻画一般算法计算能力的模型。，Turing 归约公理库Turing 归约Turing reduction · Oracle reduction允许算法把目标语言作为预言机进行多次自适应查询的可计算性归约。用它刻画可自适应多次查询的计算，并与 映射归约公理库映射归约Mapping reduction · Many-one reduction用可计算函数把一个语言成员关系变换为另一个语言成员关系。 的一次性翻译形成对照。复杂度理论借它定义 $P^A,N{P}^A$ 等相对类、识别证明技术的相对化障碍，并理解 多项式层级公理库多项式层级Polynomial hierarchy · PH由交替存在和全称多项式证书或逐层 NP 预言机构成的复杂性层级。 的量词和预言机刻画；递归论则用 Turing degree 组织不可计算集合。