Solution of the Density Classification Problem with Two Cellular Automata Rules

Henryk Fukś
Department of Physics, University of Illinois, Chicago, IL 60607-7059
fuks@uic.edu
Recently, Land and Belew [Phys. Rev. Lett. 74, 5148 (1995)] have shown that no one-dimensional
two-state cellular automaton which classifies binary strings according to their densities of 1’s and
0’s can be constructed. We show that a pair of elementary rules, namely the “traffic rule” 184 and
the “majority rule” 232, performs the task perfectly. This solution employs the second order phase
transition between the freely moving phase and the jammed phase occurring in rule 184. We present
exact calculations of the order parameter in this transition using the method of preimage counting.

05.70.Fh,89.80.+h
arXiv:comp-gas/9703001v1 7 Mar 1997

I. INTRODUCTION If we think about the cellular automaton as a model

of a multicellular organism composed of identical cells,
In recent years, cellular automata (CA) [1] have re- or a single kind of “tissue,” we could say that evolution
ceived considerable attention as models of natural sys- reached a “dead end” here. In the biological evolution,
tems in which simple local interactions between compo- when the single-tissue organism cannot be improved any
nents give rise to a complex global behavior. Such sys- further, the next step is the differentiation of cells, or
tems have the ability of coordinated global information aggregation of cells into organs adapted to perform a
processing, often called “emergent computation,” which specific function. In a colony of insects, this can be in-
could not be achieved by a single component. Since emer- terpreted as a “division of labor,” when separate groups
gent computation occurs in many biological systems such of insects perform different partial tasks. For cellular au-
as the brain, the immune system, or insect colonies, it is tomata, this could be realized as an “assembly line,” with
natural to ask how the evolution produces such complex two (or more) different CA rules: the first rule is iterated
information processing capabilities in ensembles of simple t1 times, and then the resulting configuration is processed
locally interacting elements. by another rule iterated t2 times. Each rule plays the role
To model this process, genetic algorithms have been of a separate “organ,” thus we can expect that such a sys-
used to evolve cellular automata capable of performing tem will be able to perform complex computational tasks
specific computational tasks, in particular the so-called much better that just a single rule. In what follows, we
density classification task [2]. The CA performing this will show that for the density classification problem this
task should converge to a fixed point of all 1’s if the is indeed the case, and that the perfect performance can
initial configuration contains more 1’s than 0’s, and to a be achieved with just two elementary rules (184 and 232)
fixed point of all 0’s if the initial configuration contains arranged in the “assembly line” described above.
more 0’s than 1’s. This should happen within M time
steps, where, in general, M can depend on the lattice size
L (assuming periodic boundary conditions). II. RULE 184
The earliest proposed solution to this problem was the
two-state radius-3 rule constructed by Gacs, Kurdyumov, Let G = {0, 1} be called a symbol set, and let S be
and Levin (GKL) [3]. According to this rule, if the state the set of all bisequences over G, where by a bisequence
of a cell is 0, its new state is determined by a major- we mean a function on Z to G. The set S will be called
ity vote among itself, its left neighbor, and its second left the configuration space. A block of length n is an ordered
neighbor. If the state of the cell is 1, its new state is given set b1 b2 . . . bn , where n ∈ N, bi ∈ G. Bn denotes the set
by the majority vote among itself, its right neighbor, and of all blocks of length n. The number of elements of Bn
its second right neighbor. It has been demonstrated that (denoted by card Bn ) equals 2n .
the GKL rule performs the density classification task only A mapping f : {0, 1}3 7→ {0, 1} will be called an
approximately, i.e., not all initial configurations are clas- elementary cellular automaton rule. Alternatively, the
sified correctly. In particular, when the initial density function f can be considered as a mapping of B3 into
is close to 1/2, approximately 30% of the initial config- B0 = G = {0, 1}. Corresponding to f (also called a local
urations are misclassified. Attempts to evolve CA that mapping) we define a global mapping F : S → S such
perform density classification task resulted in rules com- that [F (s)]i = f (si−1 , si , si+1 ) for any s ∈ S.
parable to GKL in terms of proficiency, but not better, A block evolution operator corresponding to the local
typically classifying correctly about 80% of all possible rule f is a mapping f : Bn 7→ Bn−2 defined as
initial configurations [2]. In fact, it has been recently
proved by Land and Belew [4] that the perfect two-state f (b1 b2 . . . bn ) = (1)
rule performing this task does not exist. f (b1 , b2 , b3 )f (b2 , b3 , b4 ) . . . f (bn−2 , bn−1 , bn ),

1
where n > 2. snn snn+1 = 00, or using our transformation, snn snn+1 = ⋆α.
Rule 184 has been studied as a simplest model for the Since all blocks of α’s are moving with constant speed,
road traffic flow [5] . Its rule table this means that at t = 0 we must have s01 s02 = ⋆α or,
using the original notation, s01 s02 = 00, which means that
000 → 0, 001 → 0, 010 → 0, 011 → 1, α travels from i = 2 to i = n + 1 in n time steps. It
100 → 1, 101 → 1, 110 → 0, 111 → 1 can travel this distance “safely,” if and only if it does not
collide with another β-block. This can happen if all β-
can be interpreted in terms of “cars” (ones) and “empty blocks are annihilated before they hit our α, or in other
spaces” (zeros). “Cars” are moving to the right. If the words, if for every k such that 2 ≤ k ≤ 2n + 2 the num-
“car” has an “empty space” in front of it, it will move ber of β’s in the subblock s03 s04 . . . s0k is smaller than the
there, i.e., it will move one unit to the right. Under this number of α’s. Translating this back to the original no-
rule, the number of “cars” does not change, or in other tation (i.e., using 0’s and 1’s) we obtain the conclusion
words, the density of 1’s is conserved. of Proposition 1.
In order to understand the dynamics of rule 184, let us The s3 s4 . . . s2n+2 part of the preimage of 00 can there-
define a preimage of a finite block a ∈ Bk as a block b ∈ fore be constructed by using the following algorithm: we
Bk+2 such that f (b) = a. Similarly, a n-step preimage of start with an initial “capital” equal to 2. Every time
the block a ∈ Bk is a block b ∈ Bk+2n such that f n (b) = a, we choose 0, our “capital” increases by 1, and when
where the superscript n denotes multiple composition of we choose 1, it decreases by 1. We have to find a
f , i.e., iterating f n-times. For a given elementary rule, path such that the “capital” never reaches zero – the
the number of n-step preimages of a given block b (we problem known in the probability theory as the “gam-
will denote this number by card f −n (b)) can be anything bler’s ruin problem” [11]. Let us denote the “capital”
from 0 to 22+2n . For many rules, an exact expression for Pt
at time t by c(t) = i=3 ξ(si ), and let c(2) = 2. Our
card f −n (b) can be found [6], and the “traffic” rule 184 is string s3 s4 . . . s2m+2 can be now represented by a path
among such exactly solvable cases. c(2)c(3) . . . c(2m + 2). Geometrically, this can be viewed
For convenience, let us consider the preimages of the as a two-dimensional polygonal line joining points [t, c(t)]
block 00 under f184 . We will first prove the following starting at (2, 2) and ending at (2m + 2, y) which neither
proposition: touches nor crosses the horizontal axis. The number of
Proposition 1 The block s1 s2 . . . s2n+2 is an n-step all such paths can be computed using well known combi-
preimage of 00 under rule 184 if and only if s1 = 0, natorial theorems (see, for example, [11]) and is equal to
Pk
s2 = 0 and 2 + i=3 ξ(si ) > 0 for every 3 ≤ k ≤ 2n + 2, N2m,y−2 − N2m,y+2 , where
where ξ(0) = 1, ξ(1) = −1.  
a
Na,b = 1 , (2)
We will present only a sketch of the proof here, based 2 (a + b)
on the concept of “defects” [7–10]. Since the dynam-
ics of rule 184 can be viewed as “particles” or “defects” and Na,b = 0 if b > a.
(blocks of two or more 0’s or 1’s) propagating in the reg- In the path from (2, 2) to (2m+2, y) we have (2m+y −
ular background (periodic pattern of alternating 1 and 0, 2)/2 zeros and (2m−y+2)/2 ones. If we randomly choose
. . . 101010101 . . .), it will be useful to introduce a trans- 1’s with probability p and 0’s with probability 1 − p, then
formation eliminating the background. Let us consider the probability of selecting admissible path with a given
a block of length 2n + 2, and let us check whether it is “finite capital” y is
a preimage of 00 or not. To eliminate the background,
we first identify all continuous clusters of at least two ze- (N2m,y−2 − N2m,y+2 )p(2m−y+2)/2 (1 − p)(2m+y−2)/2 (3)
ros. Each site in such a cluster is replaced by the symbol
Taking into account the fact that y must be even and
α, except the leftmost 0, which is replaced by ⋆. Sim-
that the first two digits of the preimage must be 00, we
ilarly, in every cluster of at least two ones, every 1 is
conclude that the probability that a randomly selected
replaced by the symbol β, except the rightmost 1, which
string (if we select ones with probability p and zeros with
is replaced by ⋆. All remaining sites are replaced by ⋆.
probability 1 − p) of length 2m + 2 is an m-step preimage
For example, the string 1010001011000010 will be trans-
of 00 is
formed into ⋆ ⋆ ⋆ ⋆ αα ⋆ ⋆β ⋆ ⋆ααα ⋆ ⋆. The dynamics of
the rule can now be understood as a motion of blocks of m+1
X
α’s and β’s in the background of ⋆’s. Every time step, Pm (00) = (1 − p)2 (N2m,2k−2 − (4)
each block of α’s moves one unit to the right, and each k=1
block of β’s one unit to the left. When α and β blocks −N2m,2k+2 )pm−k+1 (1 − p)m+k−1 .
collide, each block decreases its length by one per time
step, until one of them (or both) disappear. Let us now Note that if we start from an infinite random initial con-
consider the block s1 s2 . . . s2n+2 iterated n times with figuration with the density of ones p, then the probability
rule 184. The state of the cell i at time t will be denoted of the occurrence of the block 00 after m iterations of rule
by sti . Block s01 s02 . . . s02n+2 can be a preimage of 00 when 184 will also be given by Pm (00).

2
 Although eq. (4) is rather complicated, asymptotic ex- 000 → 0, 001 → 0, 010 → 0, 011 → 1,
pansion for large t is possible. Using the Stirling formula 100 → 0, 101 → 1, 110 → 1, 111 → 1,
to approximate binomial coefficients, after some algebra
one obtains: which could be also written as
[4p(1 − p)]t

 1 − 2p + p
 √ if p < 12 , st+1
i → majority(sti−1 , sti , sti+1 ). (7)
πt

Pt (00) ≃ (5)
 [4p(1 − p)]t Let us assume that the initial configuration includes no 11
 (1 − p)
 √ otherwise, blocks, but at least one 00 block. It is easy to check that
πt
the only preimages of 11 under f232 are 0110, 0111, 1011,
and therefore 1101, 1110, and 1111, and all of them contain at least one
subblock 11. This means that if the initial configuration
1 − 2p if p < 12 ,

P∞ (00) = (6) contains no 11 block, then all subsequent configurations
0 otherwise. contain no block 11 either. Consequently, all entries in
the rule table which contain 11 (i.e., 110, 111, and 011)
As we can see, P∞ (00) plays here a role of the order pa-
do not matter, and we can change them without affecting
rameter in a second order kinetic phase transition, with
the dynamics. Assuming that they are mapped to zero
the control parameter p. The critical point is exactly at
we obtain a “simplified” rule
p = 1/2, and at the critical point Pt (00) approaches its
stationary value as t−1/2 . Away from the critical point, 000 → 0, 001 → 0, 010 → 0, 011 → 0,
the approach is exponential, and it slows down as p comes
closer to 1/2. For finite configurations (with periodic 100 → 0, 101 → 1, 110 → 0, 111 → 0,
boundary condition) the performance of rule 184 in elim-
which has the code number 32. The following property
inating 00 blocks for p > 1/2 is even better.
of rule 32 can be easily proved by induction:
Proposition 2 If the finite initial configuration consists
Proposition 3 The block b ∈ B2n+1 is the n-step preim-
of N0 zeros and N1 ones, and N0 < N1 , then after at
most ⌊(N0 + N1 − 2)/2⌋ time steps all 00 blocks disappear age of 1 if, and only if, b = 101 . . . 01, i.e., it is an alter-
nating sequence of 1’s and 0’s starting with 1 and ending
(⌊x⌋ denotes the largest integer less or equal to x).
with 1.
To see this, let us first consider N0 + N1 even, so that
N1 −N0 ≥ 2. Let us further assume that after (N0 +N1 − Now, if L is odd, the [(L − 1)/2]-step preimage of 1
2)/2 time steps we still have at least one 00 block. This has to have the length L, so it has to be the entire initial
means that we can write our entire initial configuration configuration. If the entire initial configuration does not
as a1 a2 . . . aN0 +N1 satisfying hypothesis of Proposition 1, have the form required by Proposition 3, it cannot be the
[(L−1)/2]-step preimage of 1. Therefore, after [(L−1)/2]
i.e., a1 = 0, a2 = 0 and 2 + ki=3 ξ(ai ) > 0 for every k
P
iterations of rule 232 the system converges to a state of
such that 3 ≤ k ≤ N0 +N1 . Note, however, that if a1 = 0,
PN0 +N1 all zeros. For even L this happens after (L − 2)/2 itera-
a2 = 0 then 2 + i=3 ξ(ai ) ≤ 0, and since it contra- tions. Similarly, if the initial configuration includes no 00
dicts the previous statement, a1 a2 . . . aN0 +N1 cannot be blocks, but at least one 11 block, the system converges
a preimage of 00. The proof for odd N0 + N1 is similar. to a state of all ones. If the initial configuration contains
Also, due to the self-duality of rule 184, the same theorem neither 00 nor 11, it stays in this state forever.
holds for the block 11 when N0 > N1 . When N0 = N1 , Using Propositions 2 and 3, our final result follows im-
both 00 and 11 blocks disappear after (N0 + N1 − 2)/2 mediately:
time steps, and the configuration becomes an alternating
sequence of 0 and 1, . . . 01010101 . . .. Proposition 4 Let s be a configuration of length L and
To summarize, we found that for a finite lattice of density ρ, and let n = ⌊(L − 2)/2⌋, m = ⌊(L − 1)/2⌋.
length L and the density ρ, after ⌊(L − 2)/2⌋ iterations m n
Then F232 (F184 (s)) consists of only 0’s if ρ < 1/2 and
of rule 184 the resulting configuration m n
of only 1’s if ρ > 1/2. If ρ = 1/2, F232 (F184 (s)) is an
alternating sequence of 0 and 1, i.e., . . . 01010101 . . ..
• contains no 00 blocks if ρ > 1/2,
As we showed, first n iterations of rule 184 eliminate all
• contains no 11 blocks if ρ < 1/2,
blocks 11 if ρ < 1/2 (or 00 if ρ > 1/2), and the subsequent
• contains neither 00 nor 11 blocks if ρ = 1/2. m iterations of rule 232 produce homogeneous configura-
tion of of all 0’s (or all 1’s). Configurations with ρ = 1/2
are also treated properly, i.e., their density remains con-
III. RULE 232 served and the converge to . . . 01010101 . . .. Examples
are shown in Figure 1.
Rule 232, also called the “majority rule,” has the fol-
lowing rule table:

3
 IV. REMARKS
αα
?? β In conclusion, we have demonstrated that the density
(a) classification task can be performed perfectly in L time
steps with two cellular automata rules, rule 184 used in
the first L/2 steps and rule 232 used in the remaining
time steps. The advantage of this “assembly line” pro-
cessing over a single rule is evident, as the single rule can
never be 100% successful in density classification.
The existence of this perfect solution does not mean,
⇐ of course, that the evolutionary process could (or could
not) produce such a pair of rules. Therefore, it would
be interesting to design a genetic algorithm experiment
in which pairs of CA rules are evolved, and find out how
easy (or difficult) it is to produce pairs of “cooperating”
rules performing better than single rules evolved in earlier
experiments. Since the exact solution exists, we may
speculate that the average performance of a pair obtained
in such an experiment should be significantly better.
Although the solution proposed here performs the task
(b) in L time steps, it is straightforward to construct a faster
algorithm, providing that we allow rules of larger radius.
If f is a radius-1 rule, than f n , the rule iterated n times,
is itself a CA rule of radius n. Therefore, the pair (g, h),
n n
where g = f184 and h = f232 , performs the classification
task in L/n time steps, assuming that we iterate both g
and h for L/2n time steps.
⇐ Another interesting question is the possibility of con-
structing a general algorithm to discriminate configura-
tions according to an arbitrary critical density ρc . One
promising approach to this problem involves generalized
traffic rules, for example rules with higher “speed limits”
[5], where the occupied site can move to the right by up
to m units if the sites in front of it are empty. Rules of
this type exhibit a phase transition at ρc = 1/(m + 1)
similar to the phase transition in rule 184. Any config-
uration with ρ = ρc converges to the periodic state of
(c) isolated 1’s separated by blocks of m zeros. Blocks of
zeros longer than m are α-type defects, propagating to
the right, while blocks of 1’s longer than 1 are defects
of β-type, propagating to the left. As in rule 184, β
defects are eliminated when ρ < ρc , and α defects dis-
appear when ρ > ρc . One can also construct an analog
of rule 232 which grows α defects if β defects are not
⇐ present and conversely, and such a pair of radius-m rules
can perform the ρc = 1/(m + 1) classification task for
any integer m > 0 (details of this construction will be
presented elsewhere). It is not clear, however, how to
generalize this method for arbitrary ρc .

V. ACKNOWLEDGEMENTS

FIG. 1. Spatiotemporal diagrams for the (184,232) pair for The author is grateful to Prof. Nino Boccara for useful
lattice size L = 100 and the initial density a) 0.52 b) 0.5 c) discussions and reading of the manuscript.
0.48. An example of two α defects colliding with the β defect
is shown in a). Both rules were iterated 50 time steps (open
arrows indicate where the iteration of rule 232 starts).

4
 [1] S. Wolfram, Cellular Automata and Complexity
(Addison-Wesley, Reading, Massachusetts, 1994).
[2] M. Mitchell, P. T. Hraber, and J. P. Crutchfield, Complex
Syst. 7, 89 (1993).
[3] P. Gacs, G. L. Kurdymov, and L. A. Levin, Probl.
Peredachi. Inf. 14, 92 (1987).
[4] M. Land and R. K. Belew, Phys. Rev. Lett. 74, 5148
(1995).
[5] M. Fukui and Y. Ishibashi, J. Phys. Soc. Jpn. 65, 1868
(1996).
[6] H. Fukś, (unpublished).
[7] N. Boccara, J. Nasser, and M. Roger, Europhys. Lett.
13, 489 (1990).
[8] N. Boccara, J. Nasser, and M. Roger, Phys. Rev. A 44,
866 (1991).
[9] J. E. Hanson and J. P. Crutchfield, J. of Stat. Phys. 66,
1415 (1992).
[10] J. P. Crutchfield and J. E. Hanson, Physica D 69, 279
(1993).
[11] W. Feller, An Introduction to Probability Theory and its
Applications (Wiley and Sons, Inc., New York, 1968).