The complexity of reversible cellular automata
The complexity of reversible cellular automata
复制标题
可逆元胞自动机的复杂性
DOI：
10.1016/j.tcs.2004.06.011
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Klaus Sutner
中科院分区：
文献类型：
--
作者：
Klaus Sutner
我们研究了可逆一维元胞自动机的轨道。结果表明，这些自动机的轨道的图灵度结构与一般元胞自动机的相同。特别地，存在可逆元胞自动机，其轨道具有任意递归可枚举度。
We study the orbits of reversible one-dimensional cellular automata. It is shown that the Turing degree structure of the orbits of these automata is the same as for general cellular automata. In particular there are reversible cellular automata whose orbits have arbitrary recursively enumerable degree.