带神谕的图灵机

刻画相对可计算性的理论计算机。文献中常用的叙述方法有两种。一种方法是在普通的图灵机上增加一个“神谕”装置和一种转移指令。“神谕”装置中有一个自然数集合A(称为神谕)，该装置能回答形如“n∈A?”的问题。

转移指令用四元组表示，就是

qSqq

其意义为：若某时刻工作带上总共有n个1、读写头内部状态为q、所对方格中印有S，读写头不动，S不变，读写头内部状态视n∈A或nA(由神谕装置回答)而变为q或q。

转移指令用五元组表示，就是

qSSqq

其意义为：若某时刻工作带上共有n个1、读写头内部装态为q、所对方格中印有S，读写头不动，将S变为S′，内部状态视n∈A或nA(由神谕装置回答)而变为q或q。

另一种方法是将带神谕的图灵机设想为具有两条可以向两端无限伸长的带子的机器，一条称为信息带(神谕带)，一条称为工作带。工作带的情形与普通图灵机相同。信息带(神谕带)上有一个格称为原点，从原点起向右的无穷多个格中放入A的特征函数——如果n∈A，第n个格印1，否则印0，原点左方的空格以b表示。输入的数据置于工作带上，要求最左边的1对准原点，读写头也对准原点，内部状态为q。读写头可同时从神谕带和工作带上读出字母，但只在工作带上打印字母。

指令用五元组表示，有三种：

qSSSq

qSSRq

qSSLq

qSSq的意义为：当读写头内部状态为q、在工作带上读到S、在神谕带上读到S′时，将工作带上的S改为&，读写头位置不动，内部状态变为q；

qSRq的意义为：当读写头内部状态为q、在工作带上读到S、在神谕带上读到时，读写头右移一格，内部状态变为q；

qSSLq的意义与上一条相似，只是改为左移一格。

这两种叙述方法是等价的。

由带神谕A的图灵机Z所计算的n元函数称为相对于A可计算的，简称A可计算的，记作

或 (x，…，x)

(当n=1时常略去不写)。

如果Z的号码为e，可记作

或(x，…，x)

也可记作

｛e｝或｛e｝(x，…，x)

普通的图灵可计算函数可以看作是相对于可计算的函数。f是A可计算的当且仅当f是A递归函数。(参见A递归函数、A递归集)