Surjectivity

Surjectivity is the important concept; injectivity is subordinate and can be treated later. The differences between cyclic, quiescent, and general boundary conditions are likewise secondary. In the analysis which we have presented, the results depend upon the frequency distribution of counterimages, and consequently upon its moment problem. The moments can be estimated from fragments of the de Bruijn matrix, determined individually for each automaton.

There are two tantalizing aspects to the problem so formulated. If the matrices involved were irreducible and not just nonnegative, several strong conclusions would be available which have to be established by other means. Likewise if more information about the moments existed, useful conclusions could be drawn about the existence of gaps or other nonuniformities in the frequency distribution.

In spite of the lack of convenience, the primordial connection between zero variance (balanced distribution of counterimages) and surjectivity (lack of a Garden of Eden) can be established by arguments which still make use of fundamental properties of the de Bruijn matrix. Moreover, the proofs are still quite relevant to the moment problem; for example the knowledge that the variance increases exponentially with the length of a configuration leaves zero variance as the only bounded possibility.

It may still be a surprise, even to those who have calculated numerous subset diagrams and perhaps read Amoroso and Patt's paper [22], that an unbalanced evolutionary rule necessarily has a Garden of Eden.

---

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