计算历史

对于一个 有限状态机 ，配置很简单 机器的当前状态以及剩余输入。 第一个配置必须是的初始状态M 和完整的输入。 从配置的转换 (S,I) 到配置 (T,J) 在以下情况下允许 I=aJ 。对于某些输入符号 a ，如果在输入a的情况下， M 有一个从S 到 T 的变换时。 最终的配置必须有空字符串 ε 作为它的剩余部分输入； M是否接受或拒绝当前的输入取决于最终状态是否是一个接受状态。 ^[1]

计算历史更常用于参考 图灵机。 单磁带图灵机的配置包括磁带内容、磁带上读/写头的位置以及相关状态机的当前状态； 这通常是写的 ...0011010101q00110101010... 其中 q 是机器的当前状态，用某种方式来将它与磁带语言区分，同时 q 位于读/写头的位置之前并且紧挨着读/写头。

考虑图灵机 M 在输入w 时。 第一个配置必须是 q₀ w₀ w₁...，其中 q₀ 是图灵机的初始状态。 机器状态的最终配置必须是q_a (接受态)或 q_r (拒绝态)。 如果从配置 Ci 可以变换到配置 C_i+1 那么配置 C_i+1 会继承配置 C_i 。这个过程是通过操纵磁带移动读/写磁头将产生结果写入到 C_i+1 。 ^[2]

2.1 可判定性结果

计算历史可以用来表明下推自动机 是 不可判定的。 这是因为图灵机 M 的计算历史是不可接受的这种语言 是一种 上下文无关语言, 可被非确定性下推自动机识别。

我们编码图灵计算历史 c₀,c₁,...,c_n 作为一个序列 C₀#C₁^r #C₂#C₃ ^r#...#C_n ，其中C_i 是配置 c_i 编写而成，并且每隔一个配置都是反向写的。 在阅读一个特定的配置时，下推自动机会做出非确定性的选择要么忽略配置，要么将其完全读入堆栈。

• 如果下推自动机决定忽略该配置，它只需完全读取和丢弃它，并为下一个选择做出相同的选择。
• 如果它决定处理配置，它会将其完全推到堆栈上，然后根据 M 的规则验证下一个配置是有效的后继配置 。 由于连续的配置总是以相反的顺序写入，因此对于新配置中的每个磁带符号，可以通过从堆栈中弹出一个符号并检查它们是否相同来完成。 如果他们不同意，必须通过 M 的有效转换 。 如果在任何时候，自动机判定转换无效，它会立即进入一个特殊的接受状态，忽略其余的输入并在最后接受。

此外，自动机会验证第一个配置是否正确初始配置(如果不是，它接受)和最终状态历史的配置是接受状态(如果不是，它接受)。 因为如果有任何有效的方法让非确定性自动机接受，这里描述的自动机将发现历史是否无效接受历史，如果接受，就会接受，如果不接受，就会拒绝。 ^[3]

同样的技巧不能用来识别 可接受 计算历史因为非决定论可以被用来跳过一个测试否则会失败。 线性有界图灵机足以识别可接受计算历史。

这个结果让我们能够证明 ALL_PDA ，即接受所有输入的下推自动机的语言是不可判定的。 假设我们对此有个决定器 D 。 对于任何图灵机 M 和输入 w ，我们可以形成下推自动机 P 它接受该机器所不接受的计算历史。 只有 D(P) 在没有接受计算历史记录的情况下才会接受 M 上的 w ；这将会让我们做出决定 A_TM 这让我们知道这是不可不可判定的。