发信人: ssos (存在与虚无), 信区: Algorithm
标 题: Ackermann函数与μ递归函数
发信站: 哈工大紫丁香 (2001年06月30日19:42:50 星期六), 站内信件
Ackermann函数与μ递归函数
定义 对于一个n元函数f(x_1,...,x_n)，如果存在一个机械的实现过程使得对于任意赋
值(a_1,...,a_n)，该过程在有限的步骤内产生出f(a_1,...,a_n)，那么就称f(x_1,...
,x_n)是可计算的（或能行可计算的）。“可计算、可计算性”指的是非形式的能行可计
算概念。
Turing命题 可计算的函数集等于图灵机可计算的函数集。
Church命题 可计算的函数集等于递归函数集。
Turing可计算和递归可计算都是形式可计算的同义词。历史上看，Turing命题和Church
命题都是不可证明的（因为“能行可计算”的定义不是形式化的），但数学家都相信这
两个命题是对的（可能是因为Turing和Church太有名气，或者是由于他们的理论太庞大
以至于“不识庐山真面目”，更有说服力的是迄今没有发现该命题的什么反例，反正如
今这两个命题合二为一了。没有人对“能行可计算”的这个论断提出质疑——包括我）
。
人们对能行可计算的语义是有一个认识过程的，开始对递归函数的理解局限于原始递归
函数，直到有一天，一个叫Ackermann的德国人发现了下面的递归函数：
定义 A(0,n)=n+1, A(m,0)=A(m-1,1)且 A(m,n)=A(m-1,A(m,n-1))
[注] 1928年，Wilhelm Ackermann (1896 - 1962，David Hilbert的学生) 发现x的y次
幂的z-重积分 A(x,y,z)是递归的但不是原始递归的。Rosza Peter将A(x,y,z)简化到二
元函数，初始条件由Raphael Robinson简化。
[实验] 看看Ackermann函数随自变量增长的情况：
A(1,n)=A(0,A(1,n-1))=A(1,n-1)+1=A(1,0)+n=A(0,1)+n=n+2
A(2,n)=2n+3
A(3,n)=2n+3-3
A(4,n)=EXP(n+4)-3
……
其中，函数EXP2(n)指的是：
EXP(1)=2
EXP(2)=2EXP(1)=22
EXP(3)=2EXP(2)=24
EXP(4)=2EXP(3)=216
EXP(5)=2EXP(4)=265536
……
第一个变元稍微变一点儿，函数就要疯狂地增长——我分特，太可怕了！我只算到A(4,
n)，往后会是个啥样子，简直不敢想象。下面是Ackermann函数不是原始递归函数的严格
证明。既然原始递归函数不能够概括所有能行的可计算函数，我们就必须对之加以扩充
—— μ操作（或极小化操作）就是由此而来的。
定义 基本的原始递归函数：
后继函数：S(x)=x+1
零函数：N(x)=0
单位函数：U_i(x_1,x_2,...,x_n)=x_i
定义 基本操作
复合操作：一个函数作为另外一个函数的参变量
S(S(S(S(S(x)))))=x+5
U_2(N(x),S(N(x)))=1
原始递归操作：函数的定义调用其自身
/*ADD运算*/
ADD(0,y)=y
ADD(x+1,y)=S(ADD(x,y))
/*MUL运算*/
MUL(0,y)=0
MUL(x+1,y)=ADD(MUL(x,y),y)
/*阶乘*/
Factorial(0)=1
Factorial(n+1)=MUL(S(n),Factorial(n))
定义 从基本的原始递归函数出发，反复使用各种可能的复合操作和原始递归操作而得的
函数的全体称为原始递归函数类。
定理 Ackermann函数不是原始递归函数。
[证明] 分为以下几步：
Ackermann函数对两个变元都是单调增：
首先，A(m,n)>n
其次，A(m,n+1)>A(m,n)
由Ackermann函数的定义可得:
若n_1>n_2,则A(m,n_1)>A(m,n_2)
/*若m_1>m_2,则A(m_1,n)>A(m_2,n)亦可证。*/
对任意的原始递归函数f(x_1,x_2,...,x_n)，存在一个仅仅依赖于f的常数M使得f(x_1,
x_2,...,x_n)<A(M,max{x_1,x_2,...,x_n})
首先，对基本原始递归函数成立；
其次，对原始递归函数成立。
Ackermann函数不具有上述性质（即Ackermann函数不是原始递归函数）。
（反证）如果Ackermann函数是原始递归函数，则存在M使得
A(x,y)<A(M,max{x,y})
令x=y=M,上式即为A(M,M)<A(M,M)。矛盾！
返回
定义 给定一个函数f(x_1,x_2,...,x_n)，h(x_1,x_2,...,x_n)=μy[f(y,x_1,x_2,...,
x_n)]定义了一个新函数h(x_1,x_2,...,x_n)满足：
h(a_1,...,a_n)=y，其中y是使f(y,a_1,a_2,...,a_n)=0最小的y值
返回
定义 基本的原始递归函数经过复合操作、递归操作和μ操作反复使用而得到的函数类称
为μ递归函数类或部分递归函数类（若一个部分递归函数处处有定义，则称之为全递归
函数）。
定理 Ackermann函数是全递归函数。/*这个证明非平凡，别企图用两句话证得！*/
定理 函数f是图灵机（TM）可计算的当且仅当f是μ递归函数。/*我faint，按照我的信
念，在数学中，“可构造”与“存在”是同义词。μ算子只具有半可构造性，对不存在
整数解的函数，μ算子用无限次的操作指代解不存在——这个特点和图灵机一样。*/
[证明] 分别考察三个基本的原始递归函数和三个基本操作：
三个基本的原始递归函数
三个基本操作
思考中……，不好意思啦。
定理 不可计算的函数类的势是连续统。/*God，我服了u*/
[非构造性证明] 全体函数的集合的势是连续统，可计算函数全体的势是可列的，所以不
可计算函数类的势是连续统。（非构造性证明总让人感到心里没底……）
/*补充的详细证明*/
a[1] 往证A(m,n)>n(对m做数学归纳)
m=0时，A(0,n)=n+1>n
假设结论对某个m成立，现在对n做归纳：
n=0时，由定义和归纳假设知A(m+1,0)=A(m,1)>1>0
假设对某个n成立，则A(m+1,n+1)=A(m,A(m+1,n))>A(m+1,n)>n
故，A(m+1,n+1)>n+1
返回
a[2] 往证A(m,n+1)>A(m,n)(对m做数学归纳)
m=0时，A(0,n+1)=n+2>n+1=A(0,n)
假设结论对某个m成立，利用定义和A(m,n)>n有：
A(m+1,n+1)=A(m,A(m+1,n))>A(m+1,n)
返回
a[3] 分为以下三步：
往证A(m+1,n)>=A(m,n+1)
首先证明A(m+1,n)>=A(m,n+1)（对n用数学归纳法）
n=0时，A(m+1,0)=A(m,1)
假设结论对某个n成立，利用定义和已有的结果得：
A(m,n+1)>=A(m,n)+1>=n+2
所以，A(m+1,n+1)=A(m,A(m+1,n))>=A(m,A(m,n+1))>=A(m,n+2)
往证A(m,n)>m
反复利用(i)的结果
A(m,n)>=A(0,m+n)=m+n+1>m
往证“若m_1>m_2,则A(m_1,n)>A(m_2,n)”
反复使用(m_1-m_2)次结论(i)
A(m_1,n)>=A(m_2,n+m_1-m_2)>A(m_2,n)
返回
b[1] 分别考察基本的原始递归函数：
S(x)=x+1<x+2=A(1,x)
N(x)=0<x+2=A(1,x)
U_i(x_1,x_2,...,x_n)=x_i<x_i+2=A(1,x_i)<=A(1,max{x_1,...x_n})
返回
b[2] 分别考察复合操作和递归操作：
复合函数h=f(g_1,...,g_m)，其中g_i是关于x_1,...,x_n的函数，f和g_i都是原始递归
函数。由归纳假设，存在m个常数M_i和M_0，使得
g_i(x_1,...,x_n)<A(M_i,max{x_1,...,x_n})
f(g_1,...,g_m)<A(M_0,max{g_1,...,g_m})
令M=max{M_0,M_1,...,M_m}，则有
g_i(x_1,...,x_n)<A(M,max{x_1,...,x_n})
于是，f(g_1,...g_m)<A(M,max{g_1,...,g_m})<A(M,A(M,max{x_1,...,x_n}))<A(M,A(M
+1,max{x_1,...,x_n}))<A(M+1,max{x_1,...,x_n}+1)<=A(M+2,max{x_1,...,x_n})
在证明之前，我们先证明
[引理1] A(m+2,n)>A(m,2n)
（数学归纳法）n=0时，A(m+2,0)>A(m,0)；
假设对某个n结论成立；由定义和归纳假设知：
A(m+2,n+1)=A(m+1,A(m+2,n))>A(m+1,A(m,2n))>=A(m,A(m,2n)+1)>=A(m,2n+2)。得证。
原始递归操作：
h(0,x_2,...,x_n)=f(x_2,...,x_n)
h(x_1+1,x_2,...,x_n)=g(x_1,h(x_1,...,x_n),x_2,...,x_n)
其中，f和g都是原始递归函数，且有
f(x_2,...,x_n)<A(M_1,max{x_2,...,x_n})
g(y_1,y_2,x_2,...,x_n)<A(M_2,max{y_1,y_2,x_2,...,x_n})
令M=max{M_1,M_2}+3；记X=max{x_2,...,x_n}
[引理2] h(x_1,x_2,...,x_n)<A(M-2,X+x_1)
（数学归纳法）x_1=0时，h(0,x_2,...,x_n)<A(M_1,X)<A(M-2,X)；
假设对于某个x_1结论成立，往证x_1+1的情形：
h(x_1+1,x_2,...,x_n)=g(x_1,h(x_1,...,x_n),x_2,...,x_n)
<A(M_2,max{x_1,h(x_1,...,x_n),X})
<A(M-3,A(M-2,X+x_1))
=A(M-2,X+x_1+1)
[正式部分] /*嘿嘿，不好意思，用了两个引理*/
h(x_1,...,x_n)<A(M-2,X+x_1)
<=A(M-2,2*max{X,x_1})
<A(M,max{X,x_1})
=A(M,max{x_1,x_2,...,x_n})
返回
--
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]