词条 | 递归函数 |
释义 | digui hanshu 递归函数(卷名:数学) recursive function 数论函数的一种,其定义域与值域都是自然数集,只是由于构作函数方法的不同而有别于其他的函数。处处有定义的函数叫做全函数,未必处处有定义的函数叫做部分函数。最简单又最基本的函数有三个:零函数O(x)=0(其值恒为0);射影函数 ![]() 代入(又名复合或叠置)是最简单又最重要的造新函数的算子,其一般形状是:由一个m元函数ƒ与m个n元函数 g1,g2,…,gm 造成新函数 ƒ (g1(x1,x2,…,xn),g2(x1,x2,…,xn),…,gm(x1,x2,…,xn)),亦可记为ƒ(g1,g2,…,gm)(x1,x2,…,xn)。另一个造新函数的算子是原始递归式。具有n个参数u1,u2,…,un的原始递归式为: ![]() ![]() 由初始函数出发,经过有限次的代入与原始递归式而作出的函数叫做原始递归函数。由于初始函数显然是全函数且可计算,故原始递归函数都是全函数且可计算。通常使用的数论函数全是原始递归函数,可见原始递归函数是包括很广的。但是W.阿克曼证明了,可以作出一个可计算的全函数,它不是原始递归的。经过后人改进后,这个函数可写为如下定义的阿克曼函数: ![]() 另一个重要的造新函数的算子是造逆函数的算子,例如,由加法而造减法,由乘法造除法等。一般,设已有函数ƒ(u,x),就x解方程ƒ(u,x)=t,可得x=g(u,t)。这时函数g叫做ƒ的逆函数。至于解一般方程ƒ(u,t,x)=0而得x=g(u,t)可以看作求逆函数的推广。解方程可以看作使用求根算子。ƒ(u,t,x)=0的最小x根(如果有根的话),记为μx[ƒ(u,t,x)=0]。当方程没有根时,则认为μx[ƒ(u,t,x)=0]没有定义。可见,即使ƒ(u,t,x)处处有定义且可计算,但使用求根算子后所得的函数μx[ƒ(u,t,x)=0]仍不是全函数,可为部分函数。但只要它有定义,那就必然可以计算。这算子称为μ算子。如果ƒ(u,t,x)本身便是部分函数,则 μx[ƒ(u,t,x)=0]的意义是:当ƒ(u,t,n)可计算且其值为0,而x<n时ƒ(u,t,x)均可计算而其值非0,则 μx[ƒ(u,t,x)=0]指n;其他情况则作为无定义。例如,如果ƒ(u,t,x)=0根本没有根,或者虽然知道有一根为n,但ƒ(u,t,n-1)不可计算,那么 μx[ƒ(u,t,x)=0]都作为没有定义。在这样定义后,只要 μx[ƒ(u,t,x)=0]有值便必可计算。由初始函数出发,经过有穷次使用代入、原始递归式与 μ算子而作成的函数叫做部分递归函数,处处有定义的部分递归函数称为全递归函数,或一般递归函数。 原始递归函数类里还有一个重要的子类称为初等函数类,它是由非负整数与变元经过有穷次加、算术减(即|α-b|)、乘、算术除 ![]() 波兰人A.格热高契克把原始递归函数类按定义的复杂程度来分类,称为格热高契克分层或波兰分层。 要把递归函数应用于谓词,首先要定义谓词的特征函数。谓词R(x,y)的特征函数是 ![]() ![]() 递归函数也可以用来处理符号串。处理的办法是对符号及符号串配以自然数。这方法是K.哥德尔开始引进的,因此称为哥德尔配数法。例如,在要处理的符号系统{α1,α2,α3,…}中,可以用奇数1,3,5,7,…作为α1,α2,α3,α4,…的配数,符号串 ![]() ![]() |
随便看 |
百科全书收录78206条中英文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。