2010/11/01 by Johannes Gütschow, Vincent Nesme, Gütschow, Johannes +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #28A80 #68Q80 #Cellular Automata and Applications #Computability, Logic, AI Algorithms #DNA and Biological Computing #Discrete Mathematics (cs.DM) #F.1.1 #FOS: Computer and information sciences #FOS: Physical sciences #I.3.7 #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.1011.0313
openalex publication_date 2010/11/01 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
It is well-known that the spacetime diagrams of some cellular automata have a fractal structure: for instance Pascal's triangle modulo 2 generates a Sierpinski triangle. Explaining the fractal structure of the spacetime diagrams of cellular automata is a much explored topic, but virtually all of the results revolve around a special class of automata, whose typical features include irreversibility, an alphabet with a ring structure, a global evolution that is a ring homomorphism, and a property known as (weakly) p-Fermat. The class of automata that we study in this article has none of these properties. Their cell structure is weaker, as it does not come with a multiplication, and they are far from being p-Fermat, even weakly. However, they do produce fractal spacetime diagrams, and we explain why and how.