正文

忙碌的河狸

(2022-10-09 13:24:37) 下一个

人们可以很容易计算4乘以3(4X3=12),但是机器是怎样计算4乘以3?图灵(TURING)提
出一个计算模型(图灵机),它可以做这种计算。图灵机由一条无限长度的纸带子(带
子上划分成许多格子),读写头,控制器和字母组等组成。读写头有读写功能:可以
从带子上读出数据,也可以往带子上写数据。控制器的功能是:把读写头向左(或向
右)移动一格和改变图灵机的工作状态。设想我们要计算4乘以3,我们用一元数(
“1”)来表示数字,即4可以表示为4个1,4乘以3就可以如此表示在纸带上(我们用
X分隔两数字):

1111X111

一图灵机计算程序是这样的:把读写头向左移动至第一个空格,然后写入*号:

*1111X111

然后把读写头向右移动至第一个1,将1写为空格:

*1111X11

然后把读写头向左移动至X左边第一个1,将1写为A:

*111AX11

然后把读写头向左移动至第一个空格,将1写入空格:

1*111AX11

重复上述小循环,我们得到:

1111*AAAAX11

然后将A改为1:

1111*1111X11

重复上述大循环,我们得到:

111111111111*AAAAX

最后抹掉*AAAAX,我们得到计算结果12:

111111111111

上述图灵机计算程序看起来很笨拙,但的确是在计算。图灵机计算模型虽然简单,
但它的功能和每秒运算数亿次的电子计算机是一样的。而且至今人们还没有找到比
图灵机功能更强的计算模型。

1962年,美国俄亥俄州立大学RADO教授提出“忙碌的河狸”问题:给出一N个状态的
图灵机,T(N),从读入空白纸带(上面全是“0”)开始,然后不断向纸带写出1;在
图灵机停止时,纸带上的1的最大数目M是多少?即

M(N) = MAX(ONES IN T(N) )

这时,图灵机的工作就像忙碌的河狸。当N比较大时,上述函数是不可计算的。这是
一个观念上的突破。以往人们认为,只要函数是准确定义的,它总是可以计算的。


假设B是一可以计算M(N)的图灵机,它有Q个状态。于是B应该从纸带上读入整数N然
后写出M(N)。N和M(N)可以是二进制数。设A是一可以转换空白纸带到整数N的图灵机,
它有LOG(N)个状态(这里LOG是对数)。设C是一可以转换二进制数到一元数(“1”)的
图灵机,它有R个状态。于是三个图灵机并在一起,ABC,是一可以从读入空白纸带
开始而计算M(N)的图灵机,但它只有LOG(N)+Q+R个状态。又设X是一可以计算M(N)的
图灵机,它有N个状态。于是对于任何N,只要 N > LOG(N)+Q+R,ABC可以和X一样计
算M(N),但有较少的状态。实际上,这是不可能的,因为M(N)是单调增函数。所以
B是不存在的,M(N)是不可计算的。

尽管M(N)是不可计算,人们还是探讨图灵机计算程序,试图写出尽可能大的数。作
为游戏,世界记录还在不断刷新。

 

[ 打印 ]
阅读 ()评论 (0)
评论
目前还没有任何评论
登录后才可评论.