Intro Soup Recipe Shelf Sink Chef
Take me higher...

Ladder Cellular Automata

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 as desired.

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 [13].)

    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.


Take me higher...
Intro Soup Recipe Shelf Sink Chef