架构思维训练之自己推导图灵机(14)

图灵正是受此启发,假想了一个机器脑袋,它拥有上面全部要素包括:能够读写存储带的输入/输出,通过在存储带上移动进行读写定位;固化的运算逻辑实现为机器内置的固定程序;代表状态存储的记忆实现为存储设备即内部状态存储器。图灵把这样一个机器脑袋称为读写头,读写头和存储带就构成了图灵机模型。

(四)图灵机模型

下面我们将简单描述图灵机模型的运行机制:

开始,读写头在存储带上定位到算法的起始位置进入初始状态。接着,读入算法指令,内置固定程序解析指令含义,并结合内部状态控制计算、移动读写头输入输出,于此同时内部状态存储器保存当前状态。不断重复上述过程,直到全部指令执行完,算法结束,读写头进入停机状态。

这段描述如果让大家感到晦涩,有胸闷之感。不妨把之前题目“10-3*2+(6-2)/2=?”用上述机制在脑中模拟运行,症状便可缓解一二。如不奏效,也无妨,下节“图灵完备”咱们还会通过一个示例进行讲解,相信届时自无大碍,还请诸位宽心。

图灵认为有了机器脑袋这宝贝,天下所有可计算的问题,都能解决绝无例外。从此读写头便可在存储带上肆意驰骋,破尽天下可算之题,破解德军密码那绝对是分分钟的事。想至此,图灵心生欢喜,不禁放声大笑。“嘿!嘿!嘿!上铺的兄弟,你这是肿么了?这大半夜的又是梦话,又是大笑,多渗人啊!”。图灵闻此方才惊醒,原来只是一梦。虽说是梦,但那读写头和存储带的形象却在心中了了分明。(注:以上情境纯属虚构)于是图灵画下此图:

推荐阅读