第五章：图灵机

[murphywuwu]

在第3章和第4章，我们研究了简单计算模型的能力。我们已经看到如何识别复杂性逐渐增加的字符串、如何匹配正则表达式，以及如何解析编程语言，而且都是使用不太复杂的基本机器完成的。但我们也看到，这些机器--有限自动机和下推自动机---都有很严格的限制，这些限制影响了它们作为现实计算模型的使用。我们的小型系统还要多强大，才能摆脱这种限制并完成正常计算机的所有工作？

• [ ] 5.1 确定型图灵机
  • [ ] 5.1.1 存储
  • [ ] 5.1.2 规则
  • [ ] 5.1.3 确定性
  • [ ] 5.1.4 模拟
• [ ] 5.2 非确定型图灵机
• [ ] 5.3 最大能力
  • [ ] 5.3.1 内部存储
  • [ ] 5.3.2 子例程
  • [ ] 5.3.3 多纸带
  • [ ] 5.3.4 多维纸带
• [ ] 5.4 通用机器
  • [ ] 5.4.1 编码
  • [ ] 5.4.2 模拟

[murphywuwu]

怎样才能设计一台能实际运行程序而不总是执行某个硬编码任务的机器呢？

确定型图灵机

存储

能访问一条无限长纸带的有限状态自动机叫作图灵机（Turing Machine，TM）。这个名字通常指一条拥有确定性规则的机器，但我们也可以毫无歧义地叫它确定性图灵机(Deterministic Turing Machine，DMT）

提供一条纸带的目的就是允许在纸带上的任何位置存储任意量的数据，并以任意顺序读取，那么我们如何设计一台能与整条纸带交互的机器呢？

• 一种选择是让纸带可以被随机寻址访问，就像计算机的RAM一样给每个方格标记一个独立的数字地址，这样机器可以立即读取和写入任何位置。这增加了不必要的复杂性，而且需要规划出细节上的东西，比如如何给一条无限纸带的所有方格分配地址，以及如何在它需要访问方格时如何指定方格的地址。

• 用一个纸带头(tape head)指向纸带的一个特定位置，并且只能在那个位置读取或写入字符。每一步计算后，纸带头都可以向左或向右移动一个方格，这意味着一台图灵机为了达到远处的位置只能费力地在纸带上往复移动

规则

这个统一的规则格式有5部分：

• 机器的当前状态

• 必须出现在纸带头当前位置的字符

• 机器的下一状态

• 要写入纸带头当前位置的字符

• 写入纸带之后纸带头的移动方向（向左还是向右）

[murphywuwu]

确定性

要根据图灵机的当前状态和当前纸带头下的字符来选择它的下一个动作，因此一台确定性机器只能由状态和字符组成的一个规则——“无矛盾”规则，这是为了避免下一个动作有任何歧异。 简单起见，我们会像处理 DPDA时那样，放松“无遗漏”规则，并假设在没有规则可用的时候机器可以进入一个隐含的卡死状态，而不是坚持对于每一个可能的情况都要有一个规则。

[murphywuwu]

模拟

标签：a/b:L，表示一条规则，它从纸带上读取字符a，写入字符b，然后把纸带头向左移动一个方格。

递增一个二进制数

字符串识别问题

[murphywuwu]

我们使用配置一词来代表下推自动机状态和栈的组合，同样的理念在这里也很有帮组。可以说一个图灵机的配置是一个状态和一条纸带的组合

[murphywuwu]

知道一个规则能在一个特定的配置下应用之后，我们需要能够通过写入一个新字符、移动纸带头以及按照规则改变机器状态来更新配置