Variance histogram

The first of these, corresponding to the option S, surveys all of the automata of the class corresponding to the combination of the program, with the intention of displaying their variances. Various details emerge from such a calculation; for example all the rules with zero variance are candidates for reversible rules, since zero variance implies that every configuration has the same number of ancestors. As it happens, this is a necessary but not a sufficient condition for reversibility.

Sometimes there is an evident gap between rules of zero variance and the others; unfortunately the gap narrows as the complexity of the automaton increases, so there is no general ``gap theorem.'' In any event, the overall shape of the histogram is interesting.

The ancestor matrices do not directly determine the first moment of a distribution, nor do the sums of their tensor squares determine the second moment. In both cases, the moments arise from taking the traces of powers of the respective matrices, so the quantity of principal interest is the largest eigenvalue, which will eventually dominate all large powers.

Harold V. McIntosh