因此，

图灵机，

我们刚刚看到，

可以计算后继函数。

很直观，

它们也可以进行组合。

如果我有

一台图灵机，

计算一个函数 f 。

之后停机。

以及另一台图灵机，

计算另一个函数 g 。

之后停机。

我可以通过以下方式组合这两个函数

运行其中一台图灵机，

然后运行另一台。

我真正的意思是

我会建造

第三台图灵机

它具有两个图灵机

状态空间的组合，

当第一个停止

并完成其工作时，

这使得转换

到第二台图灵机的

初始状态，

然后继续工作

直到它停止。

事实上，它可能不会让你感到惊讶

图灵机可以做

部分递归函数

可以做的所有事情。

但是，

图灵还发现了一个非常可爱的东西，

他实际上设计了一个，

通用的图灵机

可以模拟

任何其他图灵机。

我们如何做到这一点？

好，你知道，就像一个程序一样，

可以简单地

视为一个文本文件，

你可以将它作为输入

传递给另一个程序，

我刚刚告诉你，

图灵机就它们的转移功能而言。

可以完全描述。

所以我可以

把一台图灵机的描述

放在磁带上

另一个图灵机，

连同一个输入，

我可以设置

这个通用图灵机

理论上，

模拟这个图灵机

在那个输入上

并产生结果。

事实上，

有图灵机

可以做到这一点。

我们可以称他们为 U，

而 U 所做的

是将一对事物作为输入，

P，您可以将其

视为程序

或另一台

图灵机的描述，

和输入 x 和

U 给定的对，

P, x

产生

x 的 P：

给定输入 x，

P 会做什么。

在现今时代，

这听起来并不特别

有趣或令人惊讶，

因为什么是操作系统？

操作系统是

运行程序的程序。

所以现在在你的笔记本电脑上

或你的手机

或者你有什么，

是一个一直在运行的程序

当你给它一个程序时，

它说，好吧，我会为你

运行这个程序。

它是一个运行程序的程序。

解释器

是将另一个程序

作为输入的程序

并一步一步地进行

并模拟它。

事实上，

人们编写解释器

在本科编程课程中。

在 1936 年，

当图灵提出这个想法时，

这是一个重大而深刻的事实。

再次，思考

经典数学。

你能想出一个函数，

你可以把它作为输入，

描述其他函数，

它会执行

你给它的任何函数吗？

这听起来很荒谬。

为了执行一个函数，

你需要一些更高阶的东西，

像数学家

或计算器。

函数不执行

其他函数。

而且肯定没有

通用功能

可以执行

任何函数。

然而，

在图灵机的世界里，

正是这样。

图灵最初的通用机

很大，

符号很多，

状态也很多。

但实际上聪明的人

已经想出了非常小的

通用图灵机，

例如只有

四个磁带符号

和六个状态。

所以，这种普遍计算

的现象

非常普遍，

你甚至不需要

那么大的机器

能够具有普遍性。