图灵雕像

 

1936年5月28日，艾伦·图灵发表《论可计算数及其在判定问题上的应用》，提出图灵机模型。

图灵机，又称图灵计算、图灵计算机，是由数学家阿兰·麦席森·图灵（1912～1954）提出的一种抽象计算模型，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人们进行数学运算。

所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。

整台图灵机的秘密在于读写头的状态转移表，它指示着读写头的状态和当前读写头正对格子的符号如何变化。它只有一种非常简单的规则，就是“如果在状态A的读写头对着符号x，那么对当前格子写入符号y，将纸带左移一格/右移一格/保持不动，然后转移到状态B”。状态转移表就是由一系列这样的简单规则组成的。可以说，状态转移表就相当于图灵机的源代码。

图灵机的一大优点，就是它的简单。只要给出状态转移表，任何一个人都可以模拟图灵机的计算。对工程师而言，在现实中用机械建造一台图灵机也并非什么难事。

 

纳什与图灵：爱与宽容两场戏

 

本作品为“科普中国-科技创新里程碑”原创 转载时务请注明出处

 

史上今日：1936年5月28日 图灵提出图灵机模型

图灵机 机器 计算机

图文简介

1936年5月28日，艾伦·图灵发表《论可计算数及其在判定问题上的应用》，提出图灵机模型。