Universal pattern generation by cellular automata

We construct a reversible, one-dimensional cellular automaton that has the property that a finite initial configuration generates all finite patterns over its state alphabet. We also conjecture that a related cellular automaton satisfies the stronger property that every finite pattern gets generated in every position, so that the forward orbit of the finite initial configuration is dense.

Authors

• Jarkko Kari

Keywords

• Cellular automata
• Universal constructor
• Pattern generation
• Collatz problem