图灵机

图灵机是一种抽象设备，具有有限的控制器和无限的纸带，它捕捉了算法的直观概念，并作为可计算性问题的标准参考模型。

Definition

图灵机由一组有限的状态和一个双向无限的单元格纸带组成；在每一步中，它读取磁头下的符号，写入一个符号，向左或向右移动，并根据转换函数改变状态，当它进入接受或拒绝状态时停止。

Scope

本主题涵盖图灵机的定义和操作、配置和计算、模型在多纸带和非确定性等变体下的鲁棒性、可以模拟任何其他机器的通用图灵机，以及将机器编码为数据以实现自指和不可判定性论证的可能性。

Core questions

• 一个简单的读-写-移动设备如何捕捉算法的完整概念？
• 为什么模型的许多变体计算的函数完全相同？
• 什么是通用机器，它的存在为什么意义重大？
• 将机器编码为字符串如何能够证明其自身行为？

Key theories

普适性

存在一台单一的通用图灵机，给定任何机器及其输入的编码，它就能模拟该机器的计算，这预示着程序本身就是数据的存储程序计算机的出现。

模型的鲁棒性

增加纸带、多个磁头、二维纸带或非确定性并不会改变可计算函数的类别，因此图灵机捕捉了一种对这些细节不敏感的计算概念。

Clinical relevance

图灵机是衡量编程语言和计算机体系结构能力的标准，而通用图灵机是所有现代计算所依赖的通用存储程序计算机的概念祖先。

History

图灵在1936年引入他的机器，以精确阐明数字可计算的含义，并解决希尔伯特的判定问题。通用机器的思想，即存储的描述控制一个通用设备，影响了冯·诺依曼在十年后对存储程序计算机的设计。

Key figures

• Alan Turing
• Emil Post
• John von Neumann

Seminal works

• turing1937
• sipser2013

Frequently asked questions

图灵机是真正的计算机吗？

不，它是一个数学抽象，具有无限的纸带，不考虑速度或内存成本。它的价值在于概念性：它精确地确定了原则上可以计算什么，并且任何真实计算机可以执行的任务，只要有足够的纸带和时间，图灵机也可以执行。

通用图灵机为什么重要？

它表明一台固定的机器在给定其他机器的描述作为输入时，可以执行任何其他机器的行为。这是通用可编程计算机的理论基础，其中软件是输入给单个解释设备的数据，而不是为每个任务重新布线。