Cellular Automata and Percolation: an Overview of Selected Connections
摘要
Cellular automata and percolation theory have been mutually enriching for some time now. Percolation theory studies the connectivity properties of random subgraphs of a regular network, and provides tools for studying probabilistic cellular automata. In some cases, it is also a great help for analysing the evolution of deterministic cellular automata which evolve from random configurations. Conversely, the theory of cellular automata provides new insights into some percolation properties, and raises many questions. In the present survey article, we recall some well-known connections between cellular automata and percolation, together with a more recent development, the study of a percolation game.