跳到主要内容

计算历史

阐述

MMTuring 机ww 是输入,定义

  • 接受计算历史是序列 C1,,ClC_1,\cdots,C_lC1C_1 是起始组态而 ClC_l 是接受组态
  • 拒绝计算历史定义类似,其中 ClC_l 是拒绝组态

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

实例

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

性质

相关内容

参考文献