计算历史

阐述

若 $M$ 是 Turing 机而 $w$ 是输入，定义

• 接受计算历史是序列 $C_1,\cdots,C_l$，$C_1$ 是起始组态而 $C_l$ 是接受组态
• 拒绝计算历史定义类似，其中 $C_l$ 是拒绝组态

确定性 Turing 机对每个输入至多有一个组态。

实例

计算历史方法可以用于证明 $E_{\rm LBA}$ 和 $ALL_{\rm CFG}$ 是不可判定的。

性质

相关内容

参考文献