图灵机

图灵机是一个计算的数学模型，描述了一个抽象的机器，它根据一个规则表来操作磁带上的符号。尽管这个模型很简单，但它能够实现任何计算机算法。机器在一个无限的存储带上运行，存储带被分成离散的单元，每个单元可以容纳从一个有限的符号集中抽取的一个符号，这个符号集被称为机器的字母表。它有一个磁头，在机器运行的任何时候，都位于这些单元的上方，并有一个从有限的状态集中选择的状态。在其运行的每一步，头部读取其单元中的符号。然后，根据该符号和机器自身的当前状态，机器将一个符号写入同一单元，并将头部向左或向右移动一步，或停止计算。选择写哪个替换符号和移动哪个方向是基于一个有限表，该表规定了对当前状态和所读符号的每种组合该做什么。

有了这个模型，图灵就能回答两个问题，即否定的。是否存在一台机器可以确定其磁带上的任何任意机器是否循环，是否存在一台机器可以确定其磁带上的任何任意机器是否曾经打印出一个给定的符号？图灵机证明了对机械计算能力的基本限制的存在。虽然它们可以表达任意的计算，但它们的最小化设计使它们不适合在实践中进行计算：现实世界的计算机是基于不同的设计，与图灵机不同，它们使用随机存取存储器。图灵完备性是指一个指令系统模拟图灵机的能力。

图灵机是中央处理单元（CPU）的一般例子，它控制计算机所做的所有数据操作，典型的机器使用顺序存储器来存储数据。更具体地说，它是一种机器（自动机），能够枚举一个字母表的有效字符串的一些任意子集；这些字符串是一个可递归枚举集的一部分。图灵机有一个无限长的磁带，它可以在上面进行读写操作。假设是一个黑盒子，图灵机无法知道它最终是否会用一个给定的程序列举出子集中的任何一个特定字符串。这是由于停顿问题是无法解决的，这对计算的理论极限有重大影响。图灵机能够处理无限制的语法，这进一步意味着它能够以无限多的方式稳健地评估一阶逻辑。

一个能够模拟任何其他图灵机的图灵机被称为通用图灵机（UTM，或简称通用机）。图灵机确实抓住了逻辑和数学中有效方法的非正式概念，并提供了一个模型，人们可以通过它来推理算法或机械程序。研究它们的抽象属性会产生许多对计算机科学和复杂性理论的见解。

在任何时候，机器中都有一个符号；它被称为扫描的符号。机器可以改变扫描的符号，其行为在一定程度上由该符号决定，但磁带上其他地方的符号并不影响机器的行为。然而，磁带可以在机器中来回移动，这是机器的基本操作之一。因此，磁带上的任何符号最终都可能有一个局。

图灵机在数学上建立了一个机器模型。