图灵与“图灵机”

摘要

１９３６年，２４岁的英国皇家科学院研究员阿兰·图灵发表了一篇名为《论可计算数及其在判定问题中的应用》的论文。在论文中，图灵提出了一种十分简单但运算能力极强的理想计算装置。该装置由一个控制器和一根假设无限长的工作带组成。工作带起着存储器的作用，它被划分为大小相同的方格，每一格上可以书写一个给定字母表上的符号。控制器可以在带上左右移动，控制带有一个读写头，读写头可以读出控制器访问的格子上的符号，也能改写和抹去符号。这种装置是一种理想的计算模型，或者说是一种理想中的计算机。这就是电脑史上著名的“图灵机”。在这篇载入计算机发展史册的开创性论文中，图灵给“可计算性”下了一个严格的数学定义，并提出了“图灵