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

篇首语：本文由编程笔记#小编为大家整理，主要介绍了为什么图灵计算=递归函数计算？相关的知识，希望对你有一定的参考价值。

已知函数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的图灵机指令集(转移函数δ)    

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

表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年。