UR机

全称为“具有无限寄存器的计算机”(unlimited register machine)，1963年由舍弗尔德森(Shepherdson)和斯图尔吉斯(Sturgis)提出的一种理论计算机。由于它比较接近实际的电子计算机，而且其指令直接与初始函数相关，因而使用比较方便，获得相当的重视。

UR机拥有可以无限增加的寄存器，依次记作R，R，…，R，每个寄存器可以存放一个自然数，R中存放的数据记作r。新增加的寄存器中都放有0，寄存器及其所存数据可以表示为：

输入的n元组(x，…，x)依次放入R，R，…，R之中。输入后，UR机在一组有序的指令(程序)的指挥下开始运算，运算就是根据指令对寄存器中的数据进行某种操作。如果运算到某一步后不再有指令可用，则称为停机，停机时R中的数据为输出。

UR机的指令有如下四种形式：

(1)(零指令)Z(n)：将第n个寄存器R中的数据r改为0，其它数据不动；

(2)(后继指令)S(n)：将r加1，其他数据不动；

(3)(转移指令)T(m，n)：将R中的数据放入R(即令r=r)，其它数据(包括R中的r)都不动；

(4)(跳跃指令)J(m，n，q)：如果r＝r，执行第q条指令；如果r≠r，执行下一条指令。

设P是一UR机程序(指令的有穷序列)，对给定的n≥1，向UR机输入n元数组(x，x，…，x)时，P的输出与输入之间是个n元部分函数关系，称为P所计算的n元函数。

例如由以下四条指令所组成的程序

IJ(3，2，5)

IS(1)

IS(3)

IJ(1，1，1)

是计算二元函数x+y的UR程序。

其计算过程可以表示如下：

输入(x，y)(不妨设y≠0)

先使用I，由于r=y≠r＝0，进入I，得

再用I，得

I的作用是回到I，为此下去，每循环一次r，r各增加1，直到R中的数据r=y

时，I要跳到I，而程序中没有I，停机，输出x+y。

定义，如果存在一个计算f(x，…，x)的UR程序，则称f为UR机可计算函数。

定理，f是UR机可计算的当且仅当f是部分递归的。