发布时间 : 星期一 文章可计算性与计算复杂性更新完毕开始阅读
第6页
（2）yf(x,y)=[x] y设[x]=t，则ty≤x＜(t+1)y ∴[x]=min(t+1)y＞x
t?xy∵xy是原始递归函数，x＞y是原始递归谓词，∴(t+1)y＞x是原始递归谓词，∴f(x,y)是原始递归函数。 （3）
f(x)?[log2x]
设[log2x]=t，则2t≤x＜2t+1 ∴ [log2x]=min2t+1＞x
t?x∴f(x)是原始递归函数。
（4）f(x)表示x各位数字之和 设x为n位数，n=[log2x]+1
f(x)??[R(x,10i?1)?R(x,10i)]?10?i
i?0n?1∴f(x)是原始递归函数。
（5）设an=f(n), bn=g(n)都是递增的原始递归函数，将an，bn（n＝0，1，2，……）混合在一起，再从小到大排列得到函数cn=φ(n)，证明φ(n)是原始递归函数。 φ(n)递归定义如下： φ(0)=min{a0,b0} φ(n+1)=
t?max{an,bn}min{((?i)?n(t?ai)?(?j)?n(t?bj))?(t??(n))}
∵min{a0,b0}= a0??(sub(a0,b0)) + b0??(sub(b0,a0))?d(a0,b0)
max{an,bn}= bn??(sub(an,bn)) + an??(sub(bn,an))?d(an,bn)
∴min{a0,b0}，max{an,bn}是原始递归函数，∴φ(n)是原始递归函数。
（6）将任意两个素数乘积按从小到大排成一个序列，令这个序列通项即第n项为f(n)，证明f(n)是原始递归函数。
f(n)可递归定义如下：
f(1)=4 ;2*2
?i)?n(?j)?n(t?Pi?Pj)?t?f(n)} f(n+1)= min{(2t?Pn∴f(n)是原始递归函数。
（7）称三边均为整数的直角三角形的斜边为勾股数，将它们从小到大排列，第n个勾股数记作R(n)，证明R(n)是原始递归函数。
word文档可自由复制编辑
第7页
R(n)可递归定义如下： R(1)=5
R(n+1)=min{(?i)?R2(n)(?j)?R2(n)(i?j?t)?(t?R(n))} 2t?R(n)222∴R(n)是原始递归函数。
2、计算3*2＝？
3=20×31＝[0,1]，2＝21＝[1]，3*2＝[0,1,1]＝20×31×51＝15
3、用原语言程序（限用五条基本指令）计算谓词“x1=x2”的特征函数。 0 ，x1=x2 δ(x1,x2)= 1 ，x1≠x2
[C] TO A IF X1≠0 TO D IF X2≠0 TO E [D] Y=Y+1 TO E [A] TO B IF X2≠0 TO D [B] X1=X1-1 X2=X2-1 TO C 4、用原语言程序证明每个原始递归函数都是可计算函数。
A、证明初始函数是可计算的 S（X）=X+1
X=X+1
n(X)=0
X=X+1 Y=X Y=0
…… …… word文档可自由复制编辑