- We will call a ladder a one-dimensional periodic structure,
which grows in one direction in a straight horizontal or vertical line.
Then define a ladder CA as one in which:
- There are finite seeds which give birth to horizontal or vertical
ladders and nothing else.
- Ladders can be turned: there are finite structures with which
they can collide, producing a new ladder 90° from the old one
and nothing else.
- One ladder can block another: a horizontal ladder (say) can collide
with a vertical one which is already there in such a way that it stops
without generating anything else.
- We assume that the CA rule is rotationally symmetric, so that
ladders and turns work in all four lattice directions. If these collisions
are sensitive to the ladders' spatial or temporal phase, then we also
require the following:
- Ladders can be shifted or delayed so that their phase can be adjusted
- Two more behaviors follow from these requirements, as shown in Fig. 1:
- Ladders can be delayed by arbitrary times, by executing
a sequence of turns in a square spiral.
- Ladders can end.
Fig. 1. Birth, turns, and blocking. With sequences of turns,
we can also delay ladders, or end them by blocking them with themselves.
- The blocking collision will be our main building block for Boolean circuits.
If the presence or absence of a ladder corresponds to a wire being true
or false, blocking acts as a logical gate as shown in Fig. 2, with inputs
a and b and outputs b and a and not b. (If necessary, we delay a so that it arrives after b does if b is present.)
Fig. 2. The logical effects of a blocking collision.
A ladder emerges on the right only if a is present and b is not. If a is always present, blocking negates b. We can also make copies of a wire.
- By setting a to TRUE, i.e., giving birth to a ladder which is
always there, we can use blocking to negate wires. Then by combining
blocking with negation, we can construct AND and OR gates,
a and b = a and not(not b),
a or b = not((not a) and (not b)).
- We can also make a wire 'fan out' by making multiple copies of it, so that
it can be used as input for more than one gate.
- In two dimensions, since our ladders cannot cross each other, our circuits
have to be planar. But if negation is available, we can simulate non-planar
circuits by building a crossover gadget as shown in Fig. 3; the reader can
check that with inputs a on the left and b on the right,
the outputs are b on the left and a on the right as advertised.
(In contrast, the majority-vote CA cannot express negation, and so can
only express planar circuits in d=2; see .)
Fig. 3. A crossover gadget with 8 blocking gates;
perhaps a clever reader can find a smaller one.
- Because of a ladder CA's ability to do crossover, CIRCUIT VALUE for planar circuits is just as hard as the general case. Now suppose we want to know whether a finite seed will grow to infinity. If we design the seed to let the corresponding circuit's output ladder grow, and kill off all the others, then the CA will grow to infinity if and only if its circuit's output is true. Thus growth model prediction is at least as hard as Boolean circuit prediction.