“活”过来的经典计算机——图灵机

陈凯

图灵机是一个数学模型，这个模型很有用。例如，人们可以借助图灵机证明世界上存在的某些问题，是不可能被任何有步骤的、确定性的算法解决的。又如，人们可以借助图灵机证明，在不改变机械结构的前提下，让机器做不同的运算。但除了狂热的电子发烧友，世界上并没有多少人真正利用图灵机来解决工作中的实际问题，不过，或许可以把图灵机当成一台考验智力的游戏机，不同的任务就像一道道游戏关卡，通关之后，便会对图灵机的深刻内涵有所领悟。

如果在搜索引擎中搜索“turing machine simulator”，可以找到许多不同的图灵机模拟器，本文以https：//turingmachinesimulator.com网站提供的图灵机模拟器为例（如下图），边玩边学，看看图灵机是怎么工作的。

由上图可以看出，图灵机构造很简单，由一条纸带、一个指向纸带的读写头构成。“Load”窗口用于设置纸带上原始的数据。

程序运行的原理很容易理解，读写头只要读到“0”，就往右移动，并且机器状态总是在q0和q1两者间发生变化，最后若变回q0，则说明读了偶数次“0”。如果读写头读到的数字和写的数字一样，其实就是保持纸带数据不变。如果读写头更改纸带上的数据，便会使纸带和读写头的变化更复杂。

活动表情包

有了上面的基础，就可以编写出一些好玩的程序。：-）是一张眯着眼睛的笑脸，8-（是一张瞪大眼睛愤怒的脸，可以借助图灵机让两张脸快速切换，程序如下。图灵大概没想到他的模型还能产生动画片的效果。