图灵机是什么？定义了“什么是可计算”的抽象机器

图灵机（Turing Machine）是英国数学家艾伦·图灵在 1936 年提出的一种抽象的计算模型。它并不是一台真实存在的机器，而是一个思想实验，用最简单的方式来精确地描述“计算”到底是什么。它是计算机科学最重要的理论基础之一。

它是怎么构成的

图灵机由几个非常简单的部分组成：一条无限长的纸带，被划分成一个个的格子，每个格子里可以写一个符号，比如 0、1 或者空白；一个读写头，它每次可以读取当前所在格子里的符号，可以擦掉并写入新的符号，也可以向左或向右移动一格；一个状态寄存器，记录机器当前处于什么状态；以及一张规则表，也就是机器的“程序”，它规定了：在某个状态下，读到某个符号时，应该写入什么符号、向哪个方向移动、转到哪个新的状态。机器从一个初始状态开始，按照规则一步一步地运行，直到进入一个停机的状态。

这个模型看起来简单得近乎简陋，但图灵认为，它能模拟一个人用纸和笔按照明确的规则进行计算的全过程：任何能够被一步步机械地执行的计算过程，都可以用一台图灵机来完成。

图灵为什么提出它

图灵提出这个模型，是为了回答德国数学家大卫·希尔伯特提出的“判定问题”：是否存在一种通用的、机械的方法，能够判断任何一个数学命题是否可以被证明？要回答这个问题，首先需要精确地定义什么是“机械的方法”，也就是算法。图灵用他的机器给出了这个定义，并证明了答案是否定的：存在一些问题，是任何算法都无法解决的。几乎同一时期，美国逻辑学家阿隆佐·丘奇用另一种方式，λ 演算，也得出了同样的结论。后来人们证明，这两种模型的计算能力是等价的。

两个重要的概念

通用图灵机：图灵还提出了一个非常深刻的想法：可以设计一台特殊的图灵机，它能够读取另一台图灵机的规则描述和输入，然后模拟那台机器的运行。也就是说，一台机器就能执行任何程序，只要把程序作为数据输入给它。这就是“通用图灵机”，它预示了现代存储程序计算机的核心思想：程序和数据一样存储在内存中，同一台计算机通过运行不同的软件就能完成各种各样的任务。

停机问题：图灵证明了，不存在一个通用的算法，能够判断任意一个程序在给定的输入下最终是会停下来，还是会永远运行下去。这是计算机科学中最著名的“不可判定”问题之一，它说明了计算本身存在着根本性的极限。

深远的影响

丘奇-图灵论题认为：任何在直观上“可以计算”的问题，都能用图灵机来计算。如果一种编程语言或计算系统能够模拟图灵机，就称它是“图灵完备”的。我们今天使用的几乎所有编程语言都是图灵完备的。尽管现代计算机的结构与图灵机看起来完全不同，但从理论上说，它们能计算的问题范围是一样的，区别只在于效率。计算复杂性理论研究问题需要多少时间和空间才能解决，也是以图灵机为基础建立起来的。为了纪念图灵的贡献，计算机领域的最高奖项被命名为“图灵奖”。图灵在 1950 年还提出了著名的“图灵测试”，用来探讨机器能否思考，对人工智能的发展产生了深远的影响。