On the Prediction of Local Patterns in Cellular Automata.

Abstract

The class of deterministic one-dimensional cellular automata studied recently by Wolfram are considered. We represent a state of an automaton as a probability distribution of patterns of a fixed size. In this way information is lost but it is possible to approximate the stepwise action of the automaton by the iteration of an analytic mapping of the set of probability distributions to itself. Such nonlinear analytic mappings generally have nontrivial attractors and in the most interesting cases (Wolfram Class III) these are single points. The point attractors under appropriate circumstances provide good approximations to the frequencies of local patterns generated by the discrete rules from which they were derived. Two appropriate settings for such approximations are transient patterns generated from random starts and patterns generated in a noisy environment. In the case with noise, improvement is found by correction of the analytic mappings for the effects of noise. Examples of both types of approximations are considered.