Computation and Construction Universality of Reversible Cellular Automata
Computation and Construction Universality of Reversible Cellular Automata
复制标题
可逆元胞自动机的计算与构造普适性
DOI：
10.1016/s0022-0000(77)80007-x
复制
发表时间：
1977
期刊：
影响因子：
--
通讯作者：
T. Toffoli
中科院分区：
文献类型：
--
作者：
T. Toffoli
一个任意的d维元胞自动机可以构造性地嵌入到一个d+ 1维的可逆元胞自动机中。特别是，存在计算和构造通用可逆细胞自动机。因此，我们明确地显示了一种方法，实现非平凡的不可逆过程中的可逆介质。最后，我们得出新的结果的边界问题的配置，无论是在一般情况下，可逆的细胞自动机。
An arbitrary d-dimensional cellular automaton can be constructively embedded in a reversible one having d+ 1 dimensions. In particular, there exist computation-and construction-universal reversible cellular automata. Thus, we explicitly show a way of implementing nontrivial irreversible processes in a reversible medium. Finally, we derive new results for the bounding problem for configurations, both in general and for reversible cellular automata.