预言机/Oracle Machine

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

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

一部预言机是由四个多元组构成如下：
是有限多个状态
是一个叫做转化函数（transition function）的部分函数（partial function），这里L代表左移，R代表右移。
代表起始状态
是停止状态的集合。
预言机以包含有限但许多的1、其余为空白的一些输入讯号的工作带（work tape）开始，包含预言独特功能的预言带A，和处于q0状态的图灵机，其读写头正读著工作带第一个非空格的格子，而预言读取头则读着相当于{\displaystyle \chi _{A}(0)}的预言带的格子。