图灵机

定义

图灵机是英国数学家艾伦·图灵于一九三六年提出的抽象计算模型。它由一条无限长的纸带、一个可左右移动的读写头以及一组状态转移规则组成。纸带被划分为格子，每格存放一个符号；读写头根据当前状态和读到的符号，决定写入新符号、移动方向和切换状态。

原理

图灵机的行为完全由其状态转移函数刻画。给定当前状态与读取符号，机器执行三个动作：改写当前格的内容、向左或向右移动一格、进入新状态。当机器进入接受状态或停机状态时计算结束。尽管结构极其简单，图灵机却能模拟任何算法过程，这一论断被称为「丘奇图灵论题」。

意义

图灵机奠定了可计算性理论的基石，它把「可计算」这一直觉概念形式化，使人们能够严格讨论哪些问题原则上无法被任何算法解决。通用图灵机能够读取另一台图灵机的描述并模拟其运行，这一思想直接启发了存储程序计算机的设计。今天判断一个计算模型能力强弱时，常以「是否图灵完备」作为标准。