解释理论计算机科学（TOC）中的通用图灵机

图灵机 (TM) 相当于数字计算机的机器级别。

它是由数学家图灵在1930年提出的，并且已成为可计算性和复杂性理论中最广泛使用的计算模型。

该模型由输入和输出组成。输入以二进制格式提供到机器的磁带上，输出包括机器停止时磁带的内容。

图灵机的缺点是，必须为每个要执行的新计算（针对每个输入输出关系）构建不同的机器。

这就是引入通用图灵机的原因，它除了磁带上的输入外，还包含机器 M 的描述。

通用图灵机可以继续模拟 M 对输入磁带其余内容的操作。

因此，通用图灵机可以模拟任何其他机器。

连接多个图灵机的想法给了图灵一个想法——

  • 能否创建一个可以“模拟”其他机器的通用机器？

  • 这台机器被称为通用图灵机。

这台机器将为它模拟的机器提供三条信息：

  • 机器的基本描述。
  • 机器磁带的内容。
  • 机器的内部状态。

通用机器将通过查看磁带上的输入和机器的状态来模拟机器。

它将通过根据输入更改其状态来控制机器。这导致了“计算机运行另一台计算机”的想法。

它将通过根据输入更改其状态来控制机器。这导致了“计算机运行另一台计算机”的想法。

通用图灵机的示意图如下：

更新于：2023年10月31日

57K+ 次浏览

启动您的职业生涯

完成课程获得认证

开始
广告