Reply to comment

Last night (4/12/10) I presented this conjecture ("there does not exist a single set of rules and initial conditions that will generate all possible linear arrays") to the Haverford College Problem Solving Group for its consideration. This is a collective of BiCo and high school students who have been meeting weekly (since fall 2005) to discuss interesting and challenging mathematical problems. They succeeded in proving the conjecture, assuming the "array" is of a fixed size (cyclically closed upon itself, as usual) and contains more than one cell. (They noted that the conjecture is false for a one-cell array, but that's not a useful model of any universe!)

The two least "interesting" states of any CA are those in which all cells are in the same condition: all on or all off. The group proved that a CA that reaches at least one of these uninteresting states cannot visit all possible states, no matter what the initial state is.

This result suggests the conjecture would be more interesting and important were it modified to exclude such trivial departures from the "perfect explorer" behavior. Many such modifications are possible; I won't go into them here, except to note that the behavior of a CA in a universe with a prime number of cells differs in some important ways from the behavior of a CA (using the same rule) in universes with composite numbers of cells. This is because composite-size universes admit states that are effectively those of strictly smaller universes; namely, states that remain the same after a nontrivial cyclic permutation of the cells. (The two uninteresting states can be seen from this point of view as being the two states of a one-cell universe, cyclically repeated.)

With the onset of end-of-semester pressures, no participant was willing to commit to writing down the details, but I'm sure several of them (one at BMC, one at HC, one at Friends' Central) are able and might be interested in discussing these ideas further. If we do manage to document the discussion, it will eventually appear on the group's Web page, which is in the process of migrating from Blackboard to the HC math department pages.