预言机图灵机

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

一个可逐步检验的例子是带 SAT 预言机寻找满足赋值。先查询公式 $F$ 是否可满足；若否便报告无解。若是，查询将首变量设为 $0$ 后的公式；仍可满足就保留 $0$，否则固定为 $1$。对余下变量重复，始终保持剩余公式可满足，至多再问变量数次便得到见证。每次问题依赖已经固定的前缀，体现自适应查询；查询带上写的是新公式的编码，不是一个未经描述的抽象问题。

例如，带 $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、距离和承诺间隔，用测试算法与下界区分局部违规、全局距离、容忍性和查询成本。可使用坐标、邻接或抽样 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 组织不可计算集合。