On Completeness and Decidability of Phase Space Invertible Asynchronous Cellular Automata

• Autorzy: Wacker S. , Worsch T.
• Języki publikacji: EN

Abstrakty

EN

While for synchronous deterministic cellular automata there is an accepted definition of reversibility, this is not the case for asynchronous cellular automata. We first discuss a few possibilities and then investigate what we call phase space invertible asynchronous cellular automata. We will show that for each Turing machine there is a phase space invertible purely asynchronous cellular automaton simulating it and that it is decidable whether an arbitrary-dimensional purely and a one-dimensional fully asynchronous cellular automaton is phase space invertible.

Słowa kluczowe

EN

completeness theorem; decidability; cellular automata; turing machines; dimensional analysis; machine theory

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 126, nr 2-3
• Strony: 157--181
• Opis fizyczny: Bibliogr. 13 poz.

Twórcy

autor

Wacker S.

• Department of Informatics, Karlsruhe Institute of Technology, D-76128 Karlsruhe, Germany

autor

Worsch T.

• Department of Informatics, Karlsruhe Institute of Technology, D-76128 Karlsruhe, Germany

Bibliografia

• [1] Amoroso, S., Patt, Y. N.: Decision Procedures for Surjectivity and Injectivity of Parallel Maps for Tessellation Structures, Journal of Computer and System Sciences, 6(5), 1972, 448-464.
• [2] Fates, N., Gerin, L.: Examples of Fast and Slow Convergence of 2D Asynchronous Cellular Systems, ACRI (H. Umeo, S. Morishita, K. Nishinari, T. Komatsuzaki, S. Bandini, Eds.), 5191, 2008.
• [3] Golze, U.: (A-)Synchronous (Non-)Deterministic Cell Spaces Simulating Each Other, Journal of Computer and System Sciences, 17(2), 1978, 176-193.
• [4] Kari, J.: Reversibility and Surjectivity Problems of Cellular Automata, Journal of Computer and System Sciences, 48(1), 1994, 149-182.
• [5] Kari, J.: Reversible Cellular Automata, Developments in Language Theory (C. de Felice, A. Restivo, Eds.), 3572, 2005.
• [6] Lee, J., Adachi, S., Peper, F., Morita, K.: Asynchronous Game of Life, Physica D, 194(3-4), 2004, 369-384.
• [7] Morita, K., Harao, M.: Computation Universality of One-Dimensional Reversible (Injective) Cellular Automata, IEICE Transactions, E72, 1989, 758-762.
• [8] Nakamura, K.: Asynchronous Cellular Automata and Their Computational Ability, Systems, Conputers, Control, 5(5), 1974, 58-66.
• [9] Regnault, D., Schabanel, N., Thierry, E.: Progresses in the Analysis of Stochastic 2D Cellular Automata: A Study of Asynchronous 2D Minority, Theoretical Computer Science, 410(47-49), 2009, 4844-4855.
• [10] Sarkar, A., Das, S.: On the Reversibility of 1-dimensional Asynchronous Cellular Automata, Automata (N. Fates, E. Goles, A. Maass, I. Rapaport, Eds.), 2011.
• [11] Toffoli, T.: Computation and Construction Universality of Reversible Cellular Automata, Journal of Computer and System Sciences, 15(2), 1977, 213-231.
• [12] Wacker, S.: Reversibilitat asynchroner Zellularautomaten, Diploma thesis, Karlsruhe Institute of Technology, Department of Informatics, 2012.
• [13] Wolfram, S.: Statistical Mechanics of Cellular Automata, Reviews of Modern Physics, 55, 1983,601-644.