预言机

在计算复杂度理论与可计算性理论中，预言机（英语：Oracle Machine），又称谕示机，是一种抽象电脑，用来研究决定型问题。可以被视为具备在一次运算之内解答特定问题的黑盒子（又称为预言者）的图灵机；该问题可以是任何复杂度类，甚至可以是不可判定问题，像是停机问题。

定义

一部预言机可以视为是与一个预言者（oracle）相连接的图灵机。所谓预言者的概念，是一个可以回答特定问题集合的一个实体，而且常常使用特定的自然数子集A来表示这个问题。我们可以很自然的发现，一部预言机可以执行很多对一般图灵机来说很特殊的操作，并且可以借由询问预言者来获得"x是否在A内?"这种特定形式问题的解答。

一部预言机，基本上必定包含一整个图灵机。除了这个图灵机之外，一部预言机还包含了：

• 一条预言纸带（oracle tape），印上了一个包含许多B（代表空白）和1的无限序列，代表了一个可以计算预言集合（oracle set）A的函式;
• 一个预言读取头（oracle head），像是图灵机的读写头一样可以在纸带上左右移动来读取资料，不同的是它不能写入，而且跑的纸带是预言纸带。

这里给出的定义只是几种预言的其中一种方式。不过这一些定义大同小异，因为所有这一些定义都是表示这部机器做了某个能够运算A的特定函式f。

正式定义

一部预言机是由四个多元组${\displaystyle M=\langle Q,\delta ,q_{0},F\rangle }$构成如下：

• ${\displaystyle Q}$是有限多个“状态”
• ${\displaystyle \delta :Q\times \{B,1\}^{2}\rightarrow Q\times \{B,1\}\times \{L,R\}^{2}}$是一个叫做转化函数（transition function）的部分函数（partial function），这里L代表左移，R代表右移。
• ${\displaystyle q_{0}\in Q}$代表“起始状态”
• ${\displaystyle F\subseteq Q}$是“停止状态”的集合。

预言机以包含有限但许多的1、其馀为空白的一些输入讯号的工作带（work tape）开始，包含预言独特功能的预言带A，和处于q₀状态的图灵机，其读写头正读著工作带第一个非空格的格子，而预言读取头则读著相当于${\displaystyle \chi _{A}(0)}$的预言带的格子。

与预言机相关的复杂度类

我们以A^L这个符号，代表一个复杂度类里面的决定性问题可以使用包含在A类别里面的演算法，加上带有针对L语言之预言的预言机。举例来说，P^SAT这个复杂度类，里面的问题以一个带有布尔可满足性问题预言的预言机，以多项式时间可以解决。A^B这种表示法也可以引申成令B是一个问题的集合或者是一个复杂度类，使用的定义如下：${\displaystyle A^{B}=\bigcup _{L\in B}A^{L}}$

当语言L是复杂度类B里面的完备问题时，如果这个完备定义内所使用的归约过程是在A复杂度里面，则A^L=A^B。例如，因为SAT在多项式归约里面是NP-完全，P^SAT=P^NP。然而，要是A = DLOGTIME，因为SAT在DLOGTIME里面并不一定是NP-完全，那么A^SAT并不一定等于A^NP。

很显然的，NP ⊆ P^NP，但是NP^NP，P^NP，NP和P要相等则仅在最佳状况才有可能。一般相信这些复杂度类不相等，并且导出了多项式谱系这个定义。

利用预言机，研究像是针对某种预言者A，P^A和NP^A之间的关系，对于研究P/NP问题非常的有帮助。举例来说，已经证明出分别存在语言A和B，满足P^A=NP^A与P^B≠NP^B。^[1] P = NP问题证伪与证明具有相对性被视为要证明这个问题是非常困难的一个佐证。因为这表示如果证明方法带有相对性（这意思是说，增加了预言并不影响证明本身）都不可能解出P = NP问题。举例来说，要是证明了P = NP，则这方法一定会被增加预言者所影响，否则无法解释存在预言者B令P^B≠NP^B，但是多数证明方式都带有相对性。

探讨从所有可能的预言机中（一个无限大的集合）任意选择预言机A时，会对复杂度类产生怎样的变化是一个很有趣的问题。我们已经知道，任意选择预言机A的话，P^A≠NP^A[2]。当一个陈述对几乎所有预言机成立时，我们可以说“对随机预言机也成立”。这个术语的成立基于随机预言机选择支持陈述的机率仅可能是零或一（根据零一律）。这被视为P≠NP的一个佐证。不过，一个陈述可以同时对随机预言机成立，但是对一般图灵机不成立；例如，对任意预言A，IP^A≠PSPACE^A，但是IP = PSPACE.^[3]

预言以及停机问题

即使一个问题是不可计算的，我们还是可以定义一个解答这类问题的预言者，像是回答停机问题或者同类问题的预言者。一部带有这类预言者的机器又被叫做超计算机。

有趣的是，停机问题的矛盾还是存在于这种机器上面；即使一个机器可以知道图灵机的停机问题，但是它必定不能解决自己这类机器的停机问题。这个事实创造出了算术谱系，对每个解决停机问题更强的机器都会有难到不能解决的停机问题。

参见

• 黑盒
• 图灵机
• 图灵归约
• 交互式证明系统
• 大语言模型
• 随机预言机

参考文献

1. T. P. Baker, J. Gill, R. Solovay. Relativizations of the P =? NP Question. SIAM Journal on Computing, 4(4): 431-442 (1975)
2. C. H. Bennett, J. Gill. Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1. SIAM Journal on Computing, 10(1): 96-113 (1981)
3. Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Hastad, Desh Ranjan, Pankaj Rohatgi. The Random Oracle Hypothesis is False. Journal of Computer and System Sciences, volume 49, issue 1, pp.24–39. August 1994. ISSN 0022-0000. http://citeseer.ist.psu.edu/282397.html （页面存档备份，存于互联网档案馆）

参考书目

• Alan Turing, Systems of logic based on ordinals, Proc. London math. soc., 45, 1939
• C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Section 14.3: Oracles, pp. 339 – 343.
• Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 0-534-94728-X. Section 9.2: Relativization, pp.318 – 321.
• Martin Davis, editor: The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions, Raven Press, New York, 1965. Turing's paper is in this volume. Papers include those by Godel, Church, Rosser, Kleene, and Post.