Local structure theory for cellular automata (Q1097204)

In the present paper the local structure theory (LST) for cellular automata (CA) is presented. The LST is a sequence of finitely- parameterized models of the statistical features of a cellular automaton's evolution. The n-th model in the sequence takes into account correlations in terms of the probability of blocks of n states. A class of measures, the n-block measures, is introduced. The local structure operator of order n maps n-block measures to n-block measures in a manner which reflects the CA map on blocks of states. The fixed points of the map on measures approximate the invariant measures of the CA. The ability of the LST to model evolution from uncorrelated initial distributions is studied. The theory gives exact results in simple cases. In more complex cases, Monte Carlo numerical experiments suggest that an accurate statistical portrait of CA evolution is obtained. The invariant measures of CA and the stability of these measures may be obtained from the LST. Nearest neighbour CA with two states per cell are studied using the method of the LST. To the results of the paper directly belong the results of the reviewer's paper, Izv. Akad. Nauk Ehst. SSR, Fiz. Mat. 20, 205-208 (1971; Zbl 0218.92002).