Computation Universality of One-Dimensional Reversible (Injective) Cellular Automata

Morita Kenichi

Harao Masateru

The Transactions of the IEICE

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). 1-PCA 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.

reversible computing

cellular automata

computational universality

英語

電子情報通信学会

Copyright (c) 1989 IEICE

[ISSN] 0913-574X

[NCID] AA10684666

[URI] https://search.ieice.org/bin/summary.php?id=e72-e_6_758&category=E&lang=E&year=1989&abst=

[URI] https://search.ieice.org/