預言機

在计算复杂度理论与可计算性理论中，预言机（英语：oracle machine），又称谕示机，是一种抽象电脑，用来研究决定型问题。可以被视为一个多了个黑盒子（预言者）的图灵机，这个黑盒子的功能是可以在单一运算之内解答特定问题。预言者可以解答的问题，根据给定可以是任何复杂度类之内的问题。甚至可以使用不可判定问题，像是停机问题。

与预言机相关的复杂度类

我们以Aᴸ这个符号，代表一个复杂度类里面的决定性问题可以使用包含在A类别里面的算法，加上带有针对L语言之预言的预言机。举例来说，PSAT这个复杂度类，里面的问题以一个带有布尔可满足性问题预言的预言机，以多项式时间可以解决。Aᴮ这种表示法也可以引申成令B是一个问题的集合或者是一个复杂度类，使用的定义如下：
当语言L是复杂度类B里面的完备问题时，如果这个完备定义内所使用的归约过程是在A复杂度里面，则Aᴸ=Aᴮ。例如，因为SAT在多项式归约里面是NP-完全，PSAT=Pᴺᴾ。然而，要是A = DLOGTIME，因为SAT在DLOGTIME里面并不一定是NP-完全，那么ASAT并不一定等于Aᴺᴾ。
很显然的，NP ⊆ Pᴺᴾ，但是NPᴺᴾ，Pᴺᴾ，NP和P要相等则仅在最佳状况才有可能。一般相信这些复杂度类不相等，并且导出了多项式谱系这个定义。
利用预言机，研究像是针对某种预言者A，Pᴬ和NPᴬ之间的关系，对于研究P/NP问题非常的有帮助。举例来说，已经证明出分别存在语言A和B，满足Pᴬ=NPᴬ与Pᴮ≠NPᴮ。 P = NP问题证伪与证明具有相对性被是为要证明这个问题是非常困难的一个佐证。因为这表示如果证明方法带有相对性（这意思是说，增加了预言并不影响证明本身）都不可能解出P = NP问题。举例来说，要是证明了P = NP，则这方法一定会被增加预言者所影响，否则无法解释存在预言者B令Pᴮ≠NPᴮ，但是多数证明方式都带有相对性。
探讨从所有可能的预言机中（一个无限大的集合）任意选择预言机A时，会对复杂度类产生怎样的变化是一个很有趣的问题。我们已经知道，任意选择预言机A的话，Pᴬ≠NPᴬ。当一个陈述对几乎所有预言机成立时，我们可以说“对随机预言机也成立”。这个术语的成立基于随机预言机选择支持陈述的机率仅可能是零或一（根据零一律）。这被视为P≠NP的一个佐证。不过，一个陈述可以同时对随机预言机成立，但是对一般图灵机不成立；例如，对任意预言A，IPᴬ≠PSPACEᴬ，但是IP = PSPACE.

预言以及停机问题

即使一个问题是不可计算的，我们还是可以定义一个解答这类问题的预言者，像是回答停机问题或者同类问题的预言者。一部带有这类预言者的机器又被叫做超计算机。
有趣的是，停机问题的矛盾还是存在于这种机器上面；即使一个机器可以知道图灵机的停机问题，但是他必定不能解决自己这类机器的停机问题。这个事实创造出了算术谱系，对每个解决停机问题更强的机器都会有难到不能解决的停机问题。