为什么图灵计算=递归函数计算？

作者：张寅生

（作者授权转载）

已知函数g（x₁，…, x_n），h（x₁，…，x_n, y, z），则函数 f :

f（x₁，…，x_n，0）= g（x₁，…，x_n）               （1）

f（x₁，…，x_n，y+1）= h（x₁，…，x_n, y, f（x₁，…，x_n，y））  （2）

是由h和g经过递归得到的。

f 的计算与m-极小值计算称为m-递归函数计算；比它更为广义的递归函数类（包括阿克曼递归函数计算等，在此不述）-----广义递归计算即所说的递归函数计算。 

定义1  邱奇-图灵论题（Church-Turing Thesis, CTT，即图灵定理）：每个能行可计算（图灵计算）函数都是递归函数。 

定义2  图灵机（M）是一个6元组： 

M=<Q,Σ,Г,δ,q₀, F> 

其中：

Q：有限状态集合。

Σ：输入的字母表。

Г：数据带的字母表。

δ：转移函数。

q₀：初始状态。

F：停机状态。

Accept：接受状态。

Reject：拒绝状态。

Accept≠Reject。 

例1  函数Y=f(x)= 2^x的图灵机T见例11.1的转移函数δ（见表1），现用递归函数加以表示，它表明图灵计算为什么是递归的。 

表1  Y=f(x)=2^x的图灵机指令集(转移函数δ)    

当前状态	B被扫描时的写、移动、状态转移	0被扫描时的写、移动、状态转移	1被扫描时的写、移动、状态转移
q1	1，L，q7	0，R，q1	1，R，q2
q2	B，R，q3	0，R，q2	1，R，q2
q3	0，L，q4	0，R，q3	-
q4	B，L，q5	0，L，q4	-
q5	-	1，L，q5	0，L，q6
q6	B，R，q1	0，L，q6	1，L，q6
q7	Accept	B，L，q7	-

表示为递归函数W、D、Q：

 

状态	x
q1	W, D, Q
q2
q3
q4
q5
q6
q7

表2  由自变量x, q 确定的函数 

设：

W是确定当前所读出带中字母并写入字母x的函数；

D是确定读写头写出字母后转向的函数；

Q是确定下一个状态的函数。

即

W(q_i,x_j)=x_ij                         （3）

D(q_i,x_j)=d_ij                     （4）

Q(q_i,x_j)=q_ij                     （5） 

       上述图灵机的结构（格局，即参数赋值）T可以表示为 

T(0,x,d,q)=q₀                                           （6）

T(t′, x, d, q)=T(t,W(q,x), D(q,x), Q(q,x))   （7） 

       其中t是标志不同格局的时间变量，t＇是t的后继。

       比较图灵转移函数（6）、（7），形式上等同于递归函数（1）、（2），所以图灵计算即递归计算。

  这样，图灵将一个物理装置（可物理实现的设计蓝图）完全对应了数学的函数----递归函数。须知递归函数是极其强大的，描述了及其广阔的数学函数种类，因此图灵机才能够计算这么多函数。现在发现的图灵不能计算的离散函数实际上只找到了很少很少。

 详见张寅生 《证明方法与理论》，国防工业出版社，2015年。