Table 9: Lengths of Distinct Blocks of Sites Newly Excluded at Time t

Lengths of distinct blocks of sites newly excluded at time .

Most cellular automaton rules are irreversible, so that even starting from all possible initial configurations, only a subset of configurations can occur after time steps. In this subset of configurations, only certain blocks of site values can occur. The subset can be specified by giving the blocks which are excluded. In some cases (such as rule 128), the number of distinct excluded blocks is finite; in other cases, it is countably infinite. Irreversibility leads to an increase in the size of the set of excluded blocks with time.

The table gives the lengths of the shortest blocks which are newly excluded after exactly time steps. Such blocks can occur in configurations up to time , but cannot occur at time or after. The lengths of the shortest blocks newly excluded at time obey the inequality (see pages 159--202 in this book) .

The notation --- in the table indicates that no blocks are newly excluded at a particular time step. This implies that the rule has reached a stable set of configurations, which can occur after any number of steps. It should be noted, however, that this table takes no account of the probabilities with which different configurations may occur.

Table by Lyman P. Hurd (Mathematics Department, Princeton University). (Original program by S. Wolfram.)

previous  l  next