线性加速定理

在计算复杂性理论中，图灵机的线性加速定理是指：给定任意实数 c > 0 ，如果有任意图灵机在 f(n) 时间内可以解决一个问题 L 则一定存在另一个图灵机可以在 cf(n) + n + 2 的时间内解决这个问题 L。

简要证明

这里提供一个对于 c = 1/2 时的简要的证明思路。假设一个包含有 k 条带和 s 个状态的图灵机 M 可以在 f(n) 的时间内解决这个问题，构造一个新的图灵机 M' 包含 k³ 条带，每一个符号表示一个 M 中连续的三个符号的一个区块，即 M' 的带上的符号是 M 上的符号的压缩表示—— M' 的第 i 格上的符号表示 M 的第 2i-1 格、第 2i 格和第 2i+1 格的一个区块上的符号（注意：这些区块之间是交叠的）。在一个计算步骤中，M' 模拟 M 的计算步骤直到 M 的读写头离开 M' 当前读写头所表示的对应区块到左侧或右侧的下一格（这一模拟可以在一步中完成，因为 M 在不离开 M' 中对应区块或重复一个状态的情况下最多有 3sk³ 种状态）。在这一模拟过程中， M 有可能接受（解决此问题），对应的 M' 也会接受（解决此问题）；或者 M 会一直循环下去，对应的 M' 会什么也不做（或也对应的一直循环下去）。

最后一点需要注意的地方是：由于区块可以交叠，因此这些区块可能会在交叠出包含不连续的字符。在这种情况下，最接近当前读写头位置的区块才是正确的。当发生从一个区块到另一个区块的转换时，图灵机的状态被用来暂时记录开始区块的那些交叠的符号，直到其可以被复制到目的区块的对应位置。

这一构造需要 M' 的每一步计算要对应 M 的至少两步计算。因此 M' 在最初的花费线性步骤的将输入带转换为压缩表示的步骤之后，最多还需要不会超过 f(n)/2 步。

这一证明可以被很容易的推广到所有的 c > 0 的情况，通过让每个区块使用更多相邻的符号来实现。一种叫做“带压缩定理”的相似技术可以用来在图灵机所需的空间上去掉常因数。