The Injectivity of the Global Function of a Cellular Automaton in the Hyperbolic Plane is Undecidable

• Autorzy: Margenstern M.
• Języki publikacji: EN

Abstrakty

EN

In this paper, we look at the following question. We consider cellular automata in the hyperbolic plane, see [6, 22, 9, 12] and we consider the global function defined on all possible configurations. Is the injectivity of this function undecidable? The problem was answered positively in the case of the Euclidean plane by Jarkko Kari, in 1994, see [4]. In the present paper, we show that the answer is also positive for the hyperbolic plane: the problem is undecidable.

Słowa kluczowe

EN

cellular automata; hyperbolic plane; tessellations

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 94, nr 1
• Strony: 63--99
• Opis fizyczny: Bibliogr. 24 poz., wykr.

Twórcy

autor

Margenstern M.

• Laboratoire d'Informatique Théorique et Appliquée, EA 3097, Université de Metz, I.U.T. de Metz, Département d'Informatique,Ile du Saulcy, 57045 Metz Cedex, France,

Bibliografia

• [1] Berger R., The undecidability of the domino problem, Memoirs of the American Mathematical Society, 66, (1966), 1-72.
• [2] K. Chelghoum, M. Margenstern, B. Martin, I. Pecci, Initialising Cellular Automata in the Hyperbolic Plane, IEICE Transactions on Information and Systems, 387-D(3), (2004), 677-686.
• [3] Goodman-Strauss, Ch., A strongly aperiodic set of tiles in the hyperbolic plane, Inventiones Mathematicae, 159(1), (2005), 119-132.
• [4] Kari J., Reversibility and Surjectivity Problems for Cellular Automata, Journal of Computer and System Sciences, 48, (1994), 149-182.
• [5] Kari J., The Tiling Problem Revisited, Lecture Notes in Computer Science, 4664, (2007). 72-79.
• [6] M. Margenstern, New Tools for Cellular Automata of the Hyperbolic Plane, Journal of Universal Computer Science 6(12), (2000), 1226-1252.
• [7] Margenstern M., About the domino problem in the hyperbolic plane, a new solution, arXiv:cs.CG/0701096, (2007), January, 60p.
• [8] Margenstern M., About the domino problem in the hyperbolic plane, a new solution, Technical report, 2007-102, LITA, Universitè Paul Verlaine - Metz, (2007), 106p., available at: http://www.lita.sciences.univmetz. fr/˜margens/new hyp dominoes.ps.gzip
• [9] Margenstern M., On a characterization of cellular automata in tilings of the hyperbolic plane, arXiv:cs/0702155, (2007), February, 17p.
• [10] Margenstern M., The Domino Problem of the Hyperbolic Plane Is Undecidable, arXiv: 0706.4161, (2007), June, 18p.
• [11] Margenstern M., Constructing a uniform plane-filling path in the ternary heptagrid of the hyperbolic plane, arXiv: 0710.0232, (2007), October, 22p.
• [12] Margenstern M., Cellular Automata in Hyperbolic Spaces, Volume 1, Theory, OCP, Philadelphia, (2007), 422p.
• [13] Margenstern M., The Domino Problem of the Hyperbolic Plane is Undecidable, Bulletin of the EATCS, 93, (2007), October, 220-237.
• [14] Margenstern M., Constructing a uniform plane-filling path in the ternary heptagrid of the hyperbolic plane. Computer Science Journal of Moldova, 15, (2007), 3-45.
• [15] Margenstern M., Is the injectivity of the global function of a cellular automaton in the hyperbolic plane undecidable? arXiv:0712.2577, (2007), December, 16p.
• [16] Margenstern M., The injectivity of the global function of a cellular automaton in the hyperbolic plane is undecidable, arXiv:0806.1602, (2008), June, 29p.
• [17] M. Margenstern, On a Characteriztion of Cellular Automata in Tilings of the Hyperbolic Plane, International Journal of Foundations of Computer Science, 19(5), (2008), 1235-1257.
• [18] M.Margenstern, The domino problem of the hyperbolic plane is undecidable, Theoretical Computer Science, 407, (2008), 29-84.
• [19] M. Margenstern, About the periodic tiling problem in the hyperbolic plane and connected questions, International Workshop on Combinatorial and Computation Aspects of Tilings, Imperial College, London, July 30 - August 1, 2008.
• [20] Margenstern M., Cellular Automata in Hyperbolic Spaces, Volume 2, Implementation and Computations, OCP, Philadelphia, (2008), 360p.
• [21] M. Margenstern, On the injectivity of the global function of a cellular automaton in the hyperbolic plane (extended abstract), Electronic Proceedings in Theoretical Computer Science, to appear.
• [22] M. Margenstern, K. Morita, NP problems are tractable in the space of cellular automata in the hyperbolic plane, Theoretical Computer Science, 259, 99-128, (2001)
• [23] Moore E.F., Machine Models of Self-reproduction, Proceedings of the Symposium in Applied Mathematics, 14, (1962), 17-33.
• [24] Myhill J., The Converse to Moore's Garden-of-Eden Theorem, Proceedings of the American Mathematical Society, 14, (1963), 685-686.