可计算性理论-IV

IV.可计算函数4.1理想计算机URMURM——unlimitedregistermachine理想计算机M，有无穷多个寄存器,,,321RRR，每个可存储一个任意大小的自然数，并记iR中为ir，全部存储积存器的内容构成M的一个内部状态即格局。具体计算有限，只考虑前面有限个寄存器（格局）。M所能完成的四种指令：1.清零指令Z(n)：将nR的内容nr清除掉，记为0:nr2.后继指令S(n)：将nR的内容nr增加1，记为1:nnrr3.传送指令T(m,n)：把mR的内容传送给nR，其他单元不变，记为mnrr:4.条件转移指令（Jump）J(m,n,q)：定义4.1有穷指令的序列nIIIP21称为程序，程序中指令条数n称为它的长度，指令编号称为它的编号。若J(m,n,q)为第i条指令，则nmrr：M执行指令qInmrr：M执行指令1iIqk（程序长度），mr=nr时停机M执行一条指令时完成两项工作：1.改变寄存器中某单元的内容；2.指出下一步执行哪一条指令记号：1.),,(21aaP程序P在初始格局,,21aa下的计算；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收敛（converge）于b，如果),,,(21naaaP并且在最终格局中b在1R中，记为baaaPn),,,(21（2）PURM-计算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.零函数：00)(xOxZ2.后继函数：S1)(xxS3.投影函数：niPinnixxxxP),,,(21定理4.1基本函数是可计算函数4.2.1程序的连接程序P=1I2I……mI，Q='1I'2I……'nI简单连接成1I2I……mI1mI……nmI其中1I2I……mI为P，1mI……nmI为Q，则可能发生错误跳转。定义4.4如果程序P=1I2I……nI的每一条转移指令J（m,n,q）都有qn+1，则程序P是正规的（standardform）。引理4.1如果P为一程序，则存在正规程序*P使Zbaaan,,,,21,baaaPn),,,(21iffbaaaPn),,,(21证明：假定P=1I……SI，如下构造*P=*1I……*SI：若KI非条件转移指令，则*KI=KI；若KJ为条件转移指令J（m,n,q），则1)1,,(1*sqsnmJsqIIKK定义4.5正规程序P，Q的长度分别为s，t，P，Q的连接PQ或QP是程序tssssIIIIII2121，其中，sIIIP21，tsssIII21是由Q的指令把其中每一个条件转移指令),,(qnmJ修改为),,(qsnmJ而得到。定义4.6一个程序P由若干个程序nPPP21所组成，各部分间通过连接或转移（条件转移或无条件转移）指令连结，则每个)1(niPi称为P的子程序。若Q有一个子程序P，则考虑给P留下足够的存储单元，将Q所需存储单元放在较后部分，使其在执行P时内容不变。因为P有穷，故存在最小数u，使得对每一个vu，在P计算过程中VR内容不变，记)(Pu。编制Q时，用)(PR后的单元。],,,[21llllPn：表示一计算程序Q，其输入数据存放在nLLLRRR,,,21中，输出在LR中。T（1l，1）……T（nl，n）Z（n+1）Z（（P））计算PT（1，l）4.2.2生成可计算函数的方法1．代入定义4.7已知函数),,,(21kyyyf，),,,(211nxxxg，),,,(212nxxxg，……，),,,(21nkxxxg，在一n元组nxxx,,,21上函数kggg,,,21都有定义，并且)(),,,(,),,,,(),,,,(21212211fdomxxxgxxxgxxxgnknn，如果函数h由下式定义)),,,(,),,,,(),,,,((),,,(2121221121nknnnxxxgxxxgxxxgfxxxh，则称h是由f经过对它的变元kyyy,,,21分别代入kggg,,,21而得到。f称为被代入函数，kggg,,,21称为代入函数。定理4.2如果),,,(21kyyyf，),,,(211nxxxg，),,,(212nxxxg，……，),,,(21nkxxxg是可计算函数，则经代入而得到的函数)),,,(,),,,,(),,,,((),,,(2121221121nknnnxxxgxxxgxxxgfxxxh是可计算函数。证明：假定kGGGF,,,,21分别是计算kgggf,,,,21的程序，令))(,),(),(),(,,max(21kGGGFknm初始数据存入，输入nxxx,,,21存放在nmmmRRR,,,21中，相继使用kGGG,,,21计算kggg,,,21，并把结果放在knmnmnmRRR,,,21中，然后用程序F，以knmnmnmRRR,,,21的内容为初始数据计算f，以kGGGF,,,,21为子程序，用以上方法连接起来的程序H：)1,,,2,1(),2,1()2,2,1()1,2,1(),()2,2()1,1(21knmnmnmFknmnmmmGnmnmmmGnmnmmmGnmnTmTmTk显然，),,,(21nxxxHiff)1(),,,(),,,(2121kixrrFxxxGknmnmnmni因kgggf,,,,21是可计算函数，故上式右端成立，从而),,,(21nxxxH由设计过程知H是计算h的程序。nxxx,,,21nmmmRRR,,,21),,,(211nxxxg1nmR),,,(21nkxxxgknmR)),,,(,),,,,(),,,,((21212211nknnxxxgxxxgxxxgfR1即计算了函数),,,(21nxxxh。定理4.3如果),,,(21kyyyf是可计算函数，序列kiiixxx,,,21为nxxx,,,21中取k个变元的排列（允许重复），而),,,(),,,(2121kiiinxxxfxxxh，则h是可计算的。证明：)),,,(,),,,,(),,,,((),,,(21212121121nninninninxxxPxxxPxxxPfxxxhk由于nininikPPPf,,,,21是可计算的，故),,,(21nxxxh是可计算的。例42)(),(yxyxf是可计算的。2．原始递归定义4.8已知函数),,,(21nxxxf，),,,,,(21zyxxxgn，定义h如下：)),,,,(,,,,,()1,,,,(),,,()0,,,,(2121212121yxxxhyxxxgyxxxhxxxfxxxhnnnnn则称h由f，g经原始递归运算而得到。注：定义中不要求f，g为全函数。定理4.4如果),,,(21nxxxf，),,,,,(21zyxxxgn是可计算函数，则由f，g经原始递归运算而得到的函数),,,,(21yxxxhn是可计算函数。证明：设F，G是计算f，g的程序，编制计算h的程序如下：令))(),(,2max(GFnm，初始数据yxxxn,,,,21存入121,,,,nmnmmmRRRR，R2nm作计数器k，R3nm存放中间结果),,,,(21yxxxhn，如果y=0，用F计算),,,(21nxxxf，则)0,,,,(21nxxxh已得到；如果y0，则用G连续计算))0,,,,(,0,,,,(2121nnxxxhxxxg（即)1,,,,(21nxxxh），))1,,,,(,1,,,,(2121nnxxxhxxxg（即)2,,,,(21nxxxh），……，))1,,,,(,1,,,,(2121yxxxhyxxxgnn（即),,,,(21yxxxhn）用k计G执行次数，当r2nm=y时停止计算并输出结果。H：T(1，m+1)T(n+1，m+n+1)F[1，2，……，nm+n+3]Iq：J(m+n+2，m+n+1，p)G[m+1，……，m+n，m+n+2，m+n+3m+n+3]S(m+n+2)J(1，1，q)Ip：T(m+n+3，1)流程图：1x2x……nx3．极小化定义4.9对任意函数),,,,(21yxxxfn,定义否则无定义当使得最小0),,,,()ii(),,,,()i()0),,,,((212121yxxxfyzzxxxfyyxxxfynnny称为极小化算子或算子。定理4.5如果),,,,(21yxxxfn是可计算函数，则)0),,,,((),,,(2121yxxxfyxxxgnn是可计算函数。证明：假定F是可计算函数),,,,(21yxxxfn的程序，编制计算),,,(21nxxxg的程序G，对k=0，1，……用F逐个计数),,,,(21kxxxfn，直到0yk使得0),,,,(021yxxxfn为止，则y0就是),,,(21nxxxg的值。令))(,2max(Fnm，把nxxx,,,21存放在nmmmRRR,,,21中，用1nmR作k计数器，因为每次用F计算),,,,(21kxxxfn的结果在R1中，而r2nm=0，故可用r1是否等于r2nm作为循环终止判别条件。G：T(1,m+1)T(n,m+n)Ip：F[m+1,……,m+n+11]J(1,m+n+2,q)S(m+n+1)J(1,1,p)Iq：T(m+n+1,1)4.3.2部分递归函数定义4.10部分递归函数类是包含基本函数niPSO,,，并且在代入递归和极小化下封闭的最小类。（即是由基本函数经过有限次代入，递归和极小化可得到的函数类）。记URM可计算函数类为C，部分递归函数类R。定理4.6R=C证明：由前面知，RC设),,,(21nxxxf是URM一可计算函数，对应程序P=I1，I2…IS，称),,,(21nxxxP的一步为执行一条指令，考虑计算P时相联系的函数R1步内停机在若的最后内容步内未停机在若内容步后执行tPRtPRttxxxcn),,,,(1121步内停机在若步内未停机在若下一指令序号tPtPtxxxjn0),,,,(21显然),,,,(21txxxcn,),,,,(21txxxjn都是全函数若),,,(21nxxxf有定义，则),,,(21nxxxP恰在第t0步收敛)0),,,,((210txxxjttn则),,,,(),,,(02121txxxcxxxfnn；另一方面，若),,,(21nxxxf无定义，则),,,(21nxxxP发散，),,,,(21txxxjn永远不为0，从而)0),,,,((21txxxjtn无定义。从而两种情形下均有))0),,,,((,,,,(),,,(21212