A NEW UNIVERSAL CELLULAR AUTOMATON ON THE PENTAGRID
Abstract
In this paper, we significantly improve a result of the first author, published in an issue of Theoretical Computer Science in 2003. In this paper, the authors showed the existence of a weakly universal cellular automaton on the pentagrid with 22 states. The simulation used a railway circuit which simulates a register machine. In the present paper, using the same simulation tool, we lower the number of states for a weakly universal cellular automaton down to 9.
References
- Theoretical Computer Science 296, 327 (2003), DOI: 10.1016/S0304-3975(02)00660-6. Crossref, ISI, Google Scholar
- Computer Science Journal of Moldova 9, 1 (2001). ISI, Google Scholar
- Scientific American 90 (1994). Google Scholar
M. Margenstern , Cellular Automata in Hyperbolic Spaces 1 (OCP, Philadelphia, 2007) p. 422. Google Scholar- Lecture Notes in Computer Sciences 2731, 48 (2003), DOI: 10.1007/3-540-45066-1_4. Crossref, Google Scholar
M. Margenstern , Cellular Automata in Hyperbolic Spaces,Implementation and computations 2 (OCP, Philadelphia, 2008) p. 360. Google Scholar- Journal of Universal Computer Science 6(12), 1226 (2000). ISI, Google Scholar
-
M. Margenstern , Implementing Cellular Automata on the Triangular Grids of the Hyperbolic Plane for New Simulation Tools , ASTC'2003 ( 2003 ) . Google Scholar - Theoretical Computer Science 259, 99 (2001), DOI: 10.1016/S0304-3975(99)00328-X. Crossref, ISI, Google Scholar
-
M. Margenstern , On a characterization of cellular automata in tilings of the hyperbolic plane , ACMC'2007 ( 2007 ) . Google Scholar -
M. Margenstern and Y. Song , A new universal cellular automaton on the pentagrid , Proceedings of AUTOMATA'2008 ( UWE , UK , 2008 ) . Google Scholar - Electronic Notes in Theoretical Computer Science 223, 167 (2008), DOI: 10.1016/j.entcs.2008.12.038. Crossref, Google Scholar


