Periodicity and Immortality in Reversible Computing
Periodicity and Immortality in Reversible Computing
复制标题
可逆计算中的周期性和不朽性
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Nicolas Ollinger
中科院分区：
文献类型：
--
作者：
J. Kari;Nicolas Ollinger
本文研究了可逆计数器机、可逆图灵机和可逆一维元胞自动机三种可逆计算模型中周期性和不朽性问题的可判定性。不朽性和周期性是描述模型从任意初始配置开始的行为的性质：不朽性是至少有一个非停止轨道的性质，而周期性是最终总是返回到初始配置的性质。结果表明，在这三个模型中，周期性和永生性问题都是不可判定的。我们还表明，它是不可判定的（不一定可逆）图灵机与移动磁带是否有一个周期轨道。
We investigate the decidability of the periodicity and the immortality problems in three models of reversible computation: reversible counter machines, reversible Turing machines and reversible one-dimensional cellular automata. Immortality and periodicity are properties that describe the behavior of the model starting from arbitrary initial configurations: immortality is the property of having at least one non-halting orbit, while periodicity is the property of always eventually returning back to the starting configuration. It turns out that periodicity and immortality problems are both undecidable in all three models. We also show that it is undecidable whether a (not-necessarily reversible) Turing machine with moving tape has a periodic orbit.