2023/01/25 by Maurice Margenstern, Margenstern, Maurice
Computer Science · Physics and Astronomy · #68R05 #Cellular Automata and Applications #Coding theory and cryptography #F.2.2 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Quantum chaos and dynamical systems
paper · pdf · doi:10.48550/arxiv.2301.10691
openalex publication_date 2023/01/25 · openalex created_date 2023/01/27 · openalex updated_date 2026/07/28
In this paper we prove that there is a weakly universal weighted cellular automaton in the heptagrid, the tessellation 7,3 of the hyperbolic plane, with 6 states. The present paper improves the same result deposited on arXiv:2301.10691v1 and also arXiv:2301.10691v2. In the deposited papers, the result is proved with 7 states. In the present replacement the number of states is reduced to 6. Such a reducing is not trivial and requires substantial changes in the implementation. The maximal weight is now 34, a very strong reduction with the best result with 7 states. Also, the table has 137 entries, signifcantly less than the 160 entries of the paper with 7 states. The reduction is obtained by a new implementation of the tracks which play a key role as far as without tracks there is no computational universality result.