chenm

人们可以很容易计算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)是不可计算，人们还是探讨图灵机计算程序，试图写出尽可能大的数。作
为游戏，世界记录还在不断刷新。