为什么 阿克曼函数不是原始递归函数
阿克曼函数是非原始递归函数的例子它需要两个自然数作为输入值,输出一个自然数。它的输出值增长速度非常高,仅是(4,3)的输出已大得不能准确计算。1920年代后期,数学家大卫·希尔伯特的学生GabrielSudan和威廉·阿克曼,当时正研究计算的基础。Sudan发明了一个递归却非原始递归的Sudan函数。1928年,阿克曼又独立想出了另一个递归却非原始递归的函数。他最初的念头是一个三个变量的函数A(m,n,p),使用康威链式箭号表示法是m→n→p。阿克曼证明了它是递归函数。希尔伯特在OntheInfinite猜想这个函数不是原始递归。阿克曼在OnHilbert’sConstructionoftheRealNumbers证明了这点。后来RozsaPeter和RaphaelRobinson定义了一个类似的函数,但只用两个变量。定义:?????????{n1;??????????????m=0,n>0???A(m,n)={A(m-1,1);???????????n=0,m>0???????????{A(m-1,A(m,n-1))?????n>0,m>0?求ack(3,3)的返回值:int?ack(int?m,int?n)??{??????if(m?==?0)??????????return?n1;??????else?if(n?==?0)??????????return?ack(m-1,1);??????else??????????return?ack(m-1,ack(m,n-1));??}0,ack(0,1)=2;??ack(1,0)=ack(0,1)=2;??ack(1,1)=ack(0,ack(1,0))=ack(1,0)1=3;??//容易口算出来的几个值1,ack(1,n)=ack(0,ack(1,n-1))1=ack(1,n-1)1;??//递推式??由递推式得:ack(1,n)=n1;??ps:递推式形如?A(n)?=?A(n-1)??1,求A(n)。??????用的是高中数学知识,方法是“累加法”(加起来然后消掉),是否想起来了?2,ack(2,n)=ack(1,ack(2,n-1))=ack(2,n-1)2;??//递推式??由递推式得:ack(2,n)=2n3;??ps:A(n)?=?A(n-1)??2,方法同?13,ack(3,n)=ack(2,ack(3,n-1))=2*ack(3,n-1)3;?//递推式??即:ack(3,n)3=2(ack(3,n-1)3)??得:?ack(3,n)3=(ack(3,1)3)*2n-1;??又ack(3,1)=2ack(3,0)3????ack(3,0)=a(2,1)=5??所以ack(3,1)=13;??所以?ack(3,n)=2n3?-?3;??ps:递推式形如?A(n)?=?2*A(n-1)??3,求A(n)。??????方法是“拆分常数”,拆分常数3后?A(n)??3?=?2*(?A(n-1)??3?),??????令B(n)?=?A(n)??3,即有?B(n)?=?2*B(n-1),等比数列啊,B(n)=B(1)*2n-1,??????求出B(1),得到B(n),即可得到A(n)。所以:ack(3,3)=61;计算机运行该程序时一共调用了ack()函数2432次……