×
Morita, Kenichi

Constructing reversible Turing machines in a reversible and conservative elementary triangular cellular automaton. (English) Zbl 1517.68113

J. Autom. Lang. Comb. 26, No. 1-2, 125-144 (2021).
Summary: We study the problem of how we can construct reversible Turing machines (RTMs) compactly in a two-dimensional reversible cellular automaton (CA). The CA model used here is an elementary triangular partitioned CA (ETPCA) having an extremely simple local transition function. It has been shown that any RTM is realized in a reversible and non-conservative ETPCA No. 0347, where 0347 is an identification number in the class of 256 ETPCAs. In this paper, we show that it is also possible to construct RTMs in a reversible and conservative ETPCA 0137, which has very different features from ETPCA 0347, by a systematic and hierarchical manner. Here, a reversible logic element with memory (RLEM), rather than a reversible logic gate, is used in the basic level of the construction. In particular, a special type of an RLEM No. 4-31 is implemented in ETPCA 0137. Then RTMs are constructed using the RLEM pattern. By this, the construction of configurations that simulates RTMs is greatly simplified.

Cited in 2 Documents

MSC:

68Q04 Classical models of computation (Turing machines, etc.)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q80 Cellular automata (computational aspects)

Keywords:

reversible computing; elementary triangular partitioned cellular automaton; reversible logic element with memory; reversible Turing machine; universality

Software:

Golly
Cite Review PDF
Full Text: Link

References:

[1] C.-H. Bennett, Logical reversibility of computation.IBM Journal of Research and Development17(1973), 525-532. · Zbl 0267.68024
[2] E. Fredkin,T. Toffoli, Conservative logic.International Journal of Theoretical Physics21(1982), 219-253. · Zbl 0496.94015
[3] K. Imai,K. Morita, A computation-universal two-dimensional 8-state triangular reversible cellular automaton.Theoretical Computer Science231(2000), 181-191. · Zbl 0951.68086
[4] M. Margenstern, Cellular automata in hyperbolic spaces. In:A. Adamatzky(ed.), Advances in Unconventional Computing, Volume 1: Theory. Springer, 2017, 343-389.
[5] K. Morita, Universality of 8-state reversible and conservative triangular partitioned cellular automata. In:S. E. Yacoubi,J. Wa¸s,S. Bandini(eds.),Cellular Automata, 12th International Conference on Cellular Automata for Research and Industry, ACRI 2016, Fez, Morocco, September 5-8, 2016, Proceedings. LNCS 9863, Springer, 2016, 45-54. Slides with movies of computer simulation: Hiroshima University Institutional Repository,http://ir.lib.hiroshima-u.ac.jp/00039997. · Zbl 1392.68277
[6] K. Morita, Making reversible Turing machines in a reversible elementary triangular partitioned cellular automaton. In:A. Dennunzio,E. Formenti,L. Manzoni, A. E. Porreca(eds.),AUTOMATA 2017, 23rd International Workshop on Cellular Automata and Discrete Complex Systems, Exploratory Papers. University of MilanoBicocca, 2017, 77-84.
[7] K. Morita, Reversible World: Data Set for Simulating a Reversible Elementary Triangular Partitioned Cellular Automaton on Golly. Hiroshima University Institutional Repository,http://ir.lib.hiroshima-u.ac.jp/00042655, 2017.
[8] K. Morita,Theory of Reversible Computing. Springer, Tokyo, 2017. · Zbl 1383.68002
[9] K. Morita, A universal non-conservative reversible elementary triangular partitioned cellular automaton that shows complex behavior.Natural Computing18(2019) 3, 413- 428. Slides with movies of computer simulation: Hiroshima University Institutional Repository,http://ir.lib.hiroshima-u.ac.jp/00039321. · Zbl 1530.68183
[10] K. Morita,M. Harao, Computation universality of one-dimensional reversible (injective) cellular automata.Transactions of IEICE JapanE72(1989), 758-762. Hiroshima University Institutional Repository,http://ir.lib.hiroshima-u.ac.jp/00048449.
[11] K. Morita,T. Ogiro,A. Alhazov,T. Tanizawa, Non-degenerate 2-state reversible logic elements with three or more symbols are all universal.Journal of Multiple-Valued Logic and Soft Computing18(2012), 37-54. · Zbl 1236.94102
[12] K. Morita,R. Suyama, Compact realization of reversible Turing machines by 2-state reversible logic elements. In:O. H. Ibarra,L. Kari,S. Kopecki(eds.),Unconventional Computation and Natural Computation, 13th International Conference, UCNC 2014, London, ON, Canada, July 14-18, 2014, Proceedings. LNCS 8553, Springer, 2014, 280-292. Slides with figures of computer simulation: Hiroshima University Institutional Repository,http://ir.lib.hiroshima-u.ac.jp/00036076. · Zbl 1445.68099
[13] K. Morita,Y. Tojima,K. Imai,T. Ogiro, Universal computing in reversible and number-conserving two-dimensional cellular spaces. In:A. Adamatzky(ed.), Collision-based Computing. Springer, 2002, 161-199.
[14] A. Trevorrow,T. Rokicki,T. Hutton,et al., Golly: An Open Source, Crossplatform Application for Exploring Conway’s Game of Life and Other Cellular Automata.http://golly.sourceforge.net/, 2005.
[15] S. Wolfram,A New Kind of Science. Wolfram Media Inc., 2002. · Zbl 1022.68084
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.