通用图灵机

概述

通用图灵机是能够模拟任何其他图灵机行为的特殊图灵机，由阿兰·图灵在1936年的论文中提出，是现代可编程计算机的理论原型。

关键内容

1. 定义与原理：
2. 一台能够模拟任意图灵机M行为的特殊图灵机U
3. 工作方式：在纸带上放置目标图灵机M的描述编码，以及M的输入数据，U会逐步"解释执行"M的行为

4. 体现了"程序"和"数据"统一存储的思想——机器描述（程序）和输入数据都存储在同一纸带上

5. 历史意义：

6. 在概念层面预言了可编程计算机的出现，比第一台电子计算机ENIAC早十年
7. 直接启发了冯·诺依曼的存储程序计算机架构

8. 证明了固定硬件可以通过加载不同程序来执行任意计算任务的可能性

9. 工作方式：

10. 接收两个输入：图灵机M的描述（转移函数表的编码）和M的输入数据
11. 模拟M在给定输入上的执行过程

12. 输出结果等同于M直接计算的结果

13. 现代对应：

14. 今天的通用计算机本质上都是通用图灵机的物理实现
15. 安装App或运行程序的行为相当于给通用图灵机加载不同的"纸带描述"
16. 硬件固定，通过软件执行不同任务的理念完全对应通用图灵机的机制

来源

• 01-turing-on-computable-numbers — 原始定义与论述
• 论可计算数及其在判定问题上的应用 — 创立

相关

• 图灵机 — basis
• 阿兰·麦席森·图灵 — creator
• 存储程序计算机 — engineering_implementation
• 冯·诺依曼架构 — engineering_realization
• 可编程计算机 — practical_application