| URM unlimited register machine 有无穷多个寄存器的理想计算机。与图灵机有相仿作用、但比图灵机复杂。令它的可数无穷多个寄存器为R1，R2，…，其中Ri可称为第i个寄存器，而i称为Ri的地址(i=1，2，…)。在机器工作的每个瞬间，每个Ri存放一个自然数，用ri表示(i=1，2，…)。但在每工作瞬间，除有限个寄存器外，假定其余的寄存器都存放数0，这是因为在每个工作瞬间实际上总是仅涉及有限个寄存器。机器工作期间的每个瞬间，各寄存器所存贮的数的情况，称为一个组态。URM能完成由三种类型的基本指令(即零指令、后继指令、转移指令)所指出的工作。由有限条这种基本指令组成的一个有序序列称为一个程序P。每个P可简记为〈I1，…，Is〉，其中Ii(1≤i≤s)称为P的第i条指令。为了使URM进行一个计算，必须提供一个程序P=〈I1，…，Is〉，以及一个初始组态，即寄存器R1，R2，R3，…的依次初始内容a1，a2，a3，…，然后URM从执行指令I1开始，再按顺序执行指令I2，I3等等，直到遇上转移指令。一旦遇上转移指令J(m，n，q)，则URM转去执行由J(m，n，q)提供的指令(即当rm＝rn时执行第q条指令，而当rm≠rn时仍依次执行下一条指令)。如果URM依次执行完p的指令，或当转移指令要求执行的指令在p中没有，则机器停止工作。否则，机器一直工作下去。我们可把任意一个程序p对应一个URM，不同的p对应不同的URM。说给定一个程序p，就是给出一个URM，反之亦然。固定一个程序p， 则给出一个初始组态〈r1， r2， r3， …〉=〈a1， a2， a3， …〉， 就相当于给定一个p的输入。当p作用于这个初始组态开始计算时，或经有限步计算(执行一个指令称为进行一步计算)后机器停止，这时留在R1中的内容作为输出;或者机器永不停止，从而也无输出。一个n元(部分)数论函数f称为是URM可计算函数，若存在一个URM程序p，使得由p计算的n元部分函数恰好为f，亦即屮(n)p≃f。 |