内容发布更新时间 : 2024/5/19 6:16:28星期一 下面是文章的全部内容请认真阅读。

龙源期刊网 http://www.qikan.com.cn

怎样动手“造”一台图灵机

作者：陈凯

来源：《中国信息技术教育》2018年第09期

在基础教育阶段的信息技术教材中，如果是回顾计算机发展历程的章节，常会提到图灵和他的图灵机，教材编写者通常会强调图灵机的重要意义，但对图灵机本身的描述却不多，涉及文字也很少，恐怕最多只能让人知道一个人的名字再加上一种机器的名称，更何况图灵在论文中提到的图灵机是一个理论上的模型，他没有亲自把图灵机造出来（对于他的论文来说，也没有真正制作出来的必要）。而现在，人们也并不真正需要按图灵构想的原样实现一台图灵机来当作计算工具使用，一个没有实物对应的抽象模型，是比较难让普通初学者产生深入探索的兴趣的，也就更难让初学者自发产生动力，去思考为什么图灵机对于后来通用的电子计算机发展有着非常重要的意义。

如果只有40分钟的课时来介绍一下图灵机，那么应该怎样充分利用好这短暂的时间呢？其实只要40分钟，就可以将一台图灵机的搭建过程大致演示出来。这里讲的并不是用程序来模拟图灵机，而是怎样用基础的电子元件来搭建一台图灵机，因为，当前绝大部分程序设计语言都与图灵等价，用程序语言来模拟图灵机，就体现不出“造”的过程。为了使图灵机的工作过程更生动直观地展现出来，笔者“请”来一群变色龙来做游戏，游戏过程实际上就对应着图灵机的一般工作过程。

● 一只大变色龙和一只小变色龙的相遇（10分钟）

想象一个有趣的场景，假设大变色龙A可变两种颜色——绿色和黄色，小变色龙B也可变两种颜色——绿色和黄色（如图1）。当变色龙A遇到变色龙B时，则总共可能出现四种情况：绿色—绿色；绿色—黄色；黄色—绿色；黄色—黄色。

现实中变色龙的变色能力很强，还能变出其他颜色来，不过这里为了简化问题描述，就假设它们只能变两种颜色。

既然变色龙具有变色的能力，那么，当两只变色龙相遇后，它们各自的颜色有可能会变，也有可能不变。假如有一个能力强大的变色龙驯兽师，能够让两只变色龙相遇后，按驯兽师预先设置的规则来改变，或不改变颜色。例如，对于大变色龙A，它从驯兽师那里得到的命令是这样的：如果自己（A）是绿色，对方B也是绿色，那么，下一时刻就仍然是绿色，考虑相遇后存在四种不同的情况，很容易理解表1中的规则。

龙源期刊网 http://www.qikan.com.cn

至于小变色龙B，它从驯兽师那里得到的命令如表2所示。

至于为什么要按这样的规律来变色，先暂且看成是驯兽师的个人喜好，实际上，驯兽师制订其他规则也是可以的。

龙源期刊网 http://www.qikan.com.cn

想象一下，绿色A遇见绿色B，变化之后，下一时刻A自己不变，而B变了，于是就变成了绿色A和黄色B，如果这两只变色龙还要继续玩“瞪一眼再变色”的游戏，那再下一时刻就变成了黄A和黄B，再下一时刻变成黄A和绿B，再下一时刻变为黄A和黄B，之后它们就总在最后两种状态中来回切换，似乎可以用来当作开派对时的绚彩LED了（如图2）。 ● 一只大变色龙和一群小变色龙的相遇（10分钟）

假设大变色龙A遭遇的是一大群小变色龙B1、B2、B3等，除了相互瞪眼、变色之外，大变色龙还会在变色后改变自己瞪眼的对象，考虑到变色龙通常行动缓慢，大变色龙A只是移动了一个身位，要么向左移，要么向右移，假设移动的方向也受到了驯兽师的控制，规则如表3所示。