有限规则与可扩展纸带
图灵机具有有限个控制状态和有限的纸带符号种类,纸带划分为逐个可读写的格子。读写头每次观察一个格子,依据当前状态及符号决定写入内容、移动方向和下一状态。常见模型允许向左或向右移动,某些定义也允许不移动;这些细节需要按所采用的定义说明。
输入只占有限区域,其余格子为空白。纸带没有预先固定的可用容量,但一次有限步计算只能访问有限多个格子。这种设定把“没有足够存储器”从原则上的可计算性问题中分离出来,不要求现实中实际制造一条无限纸带。
读写如何成为工作记忆
可写纸带让机器能保存中间结果并重新访问它们。假设输入用连续的 1 表示非负整数,空串表示零,读写头起初位于输入左端。一个加一过程可以向右越过所有 1,在遇到的第一个空白格写入 1,然后停机。于是 111 变成 1111,空输入变成 1。
这个小例子的规则数不随输入长度增加,运行步数却会随长度增加。对更复杂的任务,机器还可用额外符号标记已经处理的位置,再左右往返扫描。有限控制与可持续使用的纸带共同工作,使它不同于只靠有限状态记忆过去的自动机。
参考:[1]
把机器描述也当作输入
一台图灵机的状态和规则是有限的,因此可以编码为有限字符串。通用图灵机接收另一台机器的描述和待处理输入,解释该描述并逐步模拟它。通用性是能执行被编码机器的计算,不是能预先知道它将来会怎样。
如果被模拟的机器一直运行,通用机器也可能一直模拟下去。停机问题表明,不存在对任意机器与输入都正确且必定结束的统一停机判定算法。能够运行程序与能够完全预测所有程序,是两个不同的要求。
模型的等价不等于硬件相同
多纸带机器可用单纸带机器模拟,非确定图灵机也可用确定机器模拟。这些等价性讨论的是哪些语言能被识别、哪些函数能被计算,并不保证模拟前后的运行时间相同。把所有模型的能力说成一样,也不能据此忽略计算复杂性。
图灵在 1936—1937 年的论文中用抽象机器研究可计算数及判定问题;后来常用的形式定义与原文并非每个细节都相同。现代计算机有有限内存、具体指令和工程限制,图灵机则提供便于证明的理想化框架。它解释算法的原则边界,而不是把处理器、电路或操作系统逐项复制成纸带装置。