张寅生的个人博客分享 http://blog.sciencenet.cn/u/zhangbeijing 探索者:数理逻辑、人工智能

博文

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

已有 4154 次阅读 2016-5-6 18:30 |个人分类:超数学|系统分类:观点评述

作者:张寅生

 

已知函数gx1…, xn),hx1xn, y, z),则函数 f :

fx1xn,0)= gx1xn)                                               (1

fx1xny+1)= hx1xn, y, fx1xny))  (2

是由hg经过递归得到的。

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

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

定义2  图灵机M)是一个6元组: 

M=<Q,Σ,Г,δ,q0, F> 

其中:

Q:有限状态集合。

Σ:输入的字母表。

Г:数据带的字母表。

δ:转移函数

q0:初始状态。

F:停机状态

Accept:接受状态。

Reject:拒绝状态。

Accept≠Reject 

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

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

当前状态
B被扫描时的写、移动、状态转移
0被扫描时的写、移动、状态转移
1被扫描时的写、移动、状态转移            
q1
1Lq7
0Rq1
1Rq2
q2
BRq3
0Rq2
1Rq2
q3
0Lq4
0Rq3

q4
BLq5
0Lq4

q5

1Lq5
0Lq6
q6
BRq1
0Lq6
1Lq6
q7
Accept
BLq7

       表1示为递归函数WDQ 

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

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


   
设:

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

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

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

W(qi,xj)=xij                           (3

D(qi,xj)=dij                     (4

Q(qi,xj)=qij                     (5 

       上述图灵机的结构(格局,即参数赋值)T可以表示为 

T(0,x,d,q)=q0                                              (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年。




http://blog.sciencenet.cn/blog-320682-975432.html

上一篇:百度和Google的科学分野
下一篇:两个字定义“智能”!

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2019-12-7 08:18

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部