The complexity of reversible cellular automata

被引：7
|
作者：
Sutner, K [1 ]
机构：
[1] Carnegie Mellon Univ, Sch Comp Sci, Dept Comp Sci, Pittsburgh, PA 15213 USA
来源：
THEORETICAL COMPUTER SCIENCE | 2004年 / 325卷 / 02期
关键词：
cellular automata; intermediate degrees;
D O I：
10.1016/j.tcs.2004.06.011
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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. (C) 2004 Elsevier B.V. All rights reserved.
引用
收藏
页码：317 / 328
页数：12
相关论文
共 50 条
12345