可计算性理论IV

IV. 可计算函数 4.1 理想计算机URM URM——u nlimited register machine 理想计算机M，有无穷多个寄存器,,,321RRR，每个可存储一个任意大小的自然数，并记iR 中为 ir ，全部存储积存器的内容构成 M 的一个内部状态即格局。 具体计算有限，只考虑前面有限个寄存器（格局）。 M 所能完成的四种指令： 1. 清零指令 Z(n)：将nR 的内容nr 清除掉，记为0:nr 2. 后继指令 S(n)：将nR 的内容nr 增加 1，记为1:nnrr 3. 传送指令 T(m,n)：把mR 的内容传送给nR ，其他单元不变，记为mnrr : 4. 条件转移指令（Ju mp）J(m,n,q)： 定义 4.1 有穷指令的序列nIIIP21称为程序，程序中指令条数n 称为它的长度，指令编号称为它的编号。 若 J(m,n,q)为第 i 条指令，则 nmrr ： M 执行指令qI nmrr ： M 执行指令1iI q > k （程序长度），mr = nr 时停机 M 执行一条指令时完成两项工作： 1. 改变寄存器中某单元的内容； 2. 指出下一步执行哪一条指令 记号： 1. ),,(21aaP 程序 P 在初始格局,,21 aa下的计算； 2. ),,(21aaP 计算最终停机； 3. ),,(21aaP 计算不停机 例 4.1 程序 1I ：Z（1） 2I ：S（1） 3I：J（1，1，1） 对任何 a，均有)(aP 定义4.2 令ZZfn : 上部分函数，其中Z 为自然数集。 1. 假定P 是程序，Zbaaan,,,,21， （1） 计算),,,(21naaaP收敛（conv erge）于b，如果),,,(21naaaP并且在最终格局中b 在1R 中，记为baaaPn ),,,(21 （2） P URM- 计算f ：如果Zbaaan,,,,21，baaaPn ),,,(21，iff )(),,,(21fDomaaan ，并且baaafn ),,,(21 （特别，f 有定义时停机） 2. 函数f 是URM-可计算的，如果存在程序URM-计算f。 URM 的状态：mRRk,,,1 ,其中K 为指令计数器，mRR,,1 表示M 个寄存器内的值；下一状态 最后1R 中的值 即为函数计算的值 例4.2 ： 00011xxifxx  J(1,4,8) S(3) J(1,3,7) S(2) S(3) J(1,1,3) T(2,1) 4.2 生成可计算函数 定义4.3 基本函数 1. 零函数：0 0)(xO  x Z 2. 后继函数： S 1)( xxS 3. 投影函数： niP innixxxxP),,,(21 定理4.1 基本函数是可计算函数 4.2.1 程序的连接 程序P = 1I2I ……mI ， Q = '1I'2I ……'nI 简单连接成 1I2I ……mI1...