Computation universality of one-dimensional reversible (injective) cellular automata
Computation universality of one-dimensional reversible (injective) cellular automata
复制标题
DOI：
--
复制
发表时间：
1989-06
期刊：
影响因子：
--
通讯作者：
K. Morita;M. Harao
中科院分区：
文献类型：
--
作者：
K. Morita;M. Harao
可逆元胞自动机（CA）是一种“后向确定性”的CA，即它的每个构型最多有一个前驱。Toffoli证明了二维可逆元胞自动机具有计算通用性。他提出了一个开放的问题，即一维可逆CA是否具有计算通用性。本文积极地解决了这一问题。利用Morita等人先前的结果证明了1带可逆图灵机具有计算通用性，给出了一种模拟给定1带可逆图灵机的可逆CA的构造方法。为此，我们引入了“一维分区元胞自动机”（1-PCA）。1PCA具有局部可逆性（即局部函数的注入性）与全局可逆性等价的特性，便于设计可逆CA。
A reversible cellular automaton (CA) is a "backward deterministic" CA, i. e_, every configuration of it has at most one predecessor. Toffoli showed that a two-dimensional reversible cellular automaton is computation universal. He posed an open problem whether a one-dimensional reversible CA is computation universal. In this paper, we solve this problem affirmatively. This result is proved by using the previous result of Morita et al. that a 1-tape reversible Turing machine is computation universaL We give a construction method of a reversible CA which simulates a given 1-tape reversible Turing machine. To do this, we introduce a "one-dimensional partitioned cellular automaton" ( 1-PCA). 1PCA has the property that the local reversibility (i. e., injectivity of a local function) is equivalent to the global reversibility, and thus it facilitates to design a reversible CA.