Random Walks in Cellular Automata

摘要

The topological defects or phase boundaries discerned in a number of one-dimensional cellular automata appear to perform random walks as well as simpler motions. We analyze their properties rigorously using probabilistic and graph theoretic methods. This results in a complete classification in the strictly subpermutive case. The paper complements a paper by the author (1992) where the general framework of tilings and subpermutivity was introduced and non-probabilistic properties were analyzed.