Block probabilities

Another extensive addition which has been made to the programs is to be found in the series PROB.C, which can be invoked by typing t in the main menu (the old totalistic rule number can still be utilized by typing T); in fact their inclusion more than doubles the size of the programs. These new programs permit a statistical survey of the properties of the automaton.

Originally they calculated simple probabilities on the basis of ideas which go by the name of ``mean field theory,'' whose results were plausible but not entirely convincing. At about the time the programs were being updated, two interesting articles appeared in the literature:

W. John Wilbur, David J. Lipman and Shihab A. Shamma,
On the prediction of local patterns in cellular automata,
Physica 19D 397-410 (1986).

Howard A. Gutowitz, Jonathan D. Victor and Bruce W. Knight,
Local structure theory for cellular automata,
Physica 28D 18-48 (1987).

These articles, from differing points of view, showed how to take correlations between cells into account by calculating the probabilities of strings of cells. Rather than taking individual probabilities as fundamental and deducing the probabilities of combinations, the process is inverted; self consistent probabilities for strings (or blocks) of a certain length are found from which the probabilities of individual cells are obtained by an averaging process.

The calculations of these articles were then included among the options of the t submenu, so that probabilities derived from blocks of length up to 6 could be compared with simpler estimates and with the actual performance of the automaton.



Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx