Abstract
We show how to construct reversible computers in a simple reversible and conservative two-dimensional cellular space. We introduce the framework of an elementary square partitioned cellular automaton (ESPCA), and use a particular ESPCA with the hexadecimal ID number “01caef”, which is denoted by ESPCA \(P_0\) for short in this paper. A cell of ESPCA \(P_0\) consists of four parts each of which has two states 0 and 1. The class of ESPCAs is the simplest subclass of square partitioned cellular automata, and each of their local functions is described by only six local transition rules. ESPCA \(P_0\) is not only reversible, but also conservative in the sense that the total number of state 1’s is conserved throughout its evolution process. We show that a space-moving pattern called a glider exists in \(P_0\). Colliding a glider with another pattern called a blinker, several interesting phenomena appear. We give a method of constructing reversible Turing machines (RTMs) using such phenomena. We first implement a reversible logic element with memory (RLEM), rather than a reversible logic gate, using only three of these phenomena. Then, we compose reversible Turing machines out of RLEMs. In this systematic and modularized way, we can construct any RTM out of only two small patterns in a simple reversible and conservative cellular space.
Currently Professor Emeritus of Hiroshima University.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bennett, C.H.: Logical reversibility of computation. IBM J. Res. Dev. 17, 525–532 (1973). https://doi.org/10.1147/rd.176.0525
Morita, K.: Theory of Reversible Computing. Springer, Tokyo (2017). https://doi.org/10.1007/978-4-431-56606-9
Morita, K.: A universal non-conservative reversible elementary triangular partitioned cellular automaton that shows complex behavior. Nat. Comput. 18(3), 413–428 (2019). https://doi.org/10.1007/s11047-017-9655-9
Morita, K.: Data set for simulating a reversible elementary square partitioned cellular automaton with the ID number 01caef on Golly. Hiroshima University Institutional Repository (2021). http://ir.lib.hiroshima-u.ac.jp/00051576
Morita, K.: How can we construct reversible Turing machines in a very simple reversible cellular automaton? In: Yamashita, S., Yokoyama, T. (eds.) Proceedings of RC 2021. LNCS, vol. 12805, pp. 3–21 (2021). https://doi.org/10.1007/978-3-030-79837-6_1
Morita, K., Harao, M.: Computation universality of one-dimensional reversible (injective) cellular automata. Trans. IEICE E72, 758–762 (1989). http://ir.lib.hiroshima-u.ac.jp/00048449
Morita, K., Suyama, R.: Compact realization of reversible Turing machines by 2-state reversible logic elements. In: Ibarra, O.H., Kari, L., Kopecki, S. (eds.) Proceedings of UCNC 2014. LNCS, vol. 8553, pp. 280–292 (2014). https://doi.org/10.1007/978-3-319-08123-6_23
Morita, K., Ueno, S.: Computation-universal models of two-dimensional 16-state reversible cellular automata. IEICE Trans. Inf. Syst. E75-D, 141–147 (1992). http://ir.lib.hiroshima-u.ac.jp/00048451
Trevorrow, A., Rokicki, T., Hutton, T., et al.: Golly: an open source, cross-platform application for exploring Conway’s Game of Life and other cellular automata (2005). http://golly.sourceforge.net/
Wolfram, S.: A New Kind of Science. Wolfram Media Inc. (2002)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Morita, K. (2022). Computing in a Simple Reversible and Conservative Cellular Automaton. In: Das, S., Martinez, G.J. (eds) Proceedings of First Asian Symposium on Cellular Automata Technology. ASCAT 2022. Advances in Intelligent Systems and Computing, vol 1425. Springer, Singapore. https://doi.org/10.1007/978-981-19-0542-1_1
Download citation
DOI: https://doi.org/10.1007/978-981-19-0542-1_1
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-19-0541-4
Online ISBN: 978-981-19-0542-1
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)