http://people.csail.mit.edu/jaffer/Cell/CAN4S3 | |

## 4-Neighbor 3-State Universal Cellular Automaton |

Described here is a infinitely-configurable universal (Turing machine) automaton. Its equilateral triangular cells tile the plane and are isotropic; the transitions for each cell depends only on (itself and) the multiplicities of the values in the three cells directly abutting it. Generations are discrete; all cells switch to their successor states simultaneously.

rule | neighbors | cell | -> | next | (used for) |
---|---|---|---|---|---|

[j] | 444 | 0 | -> | 4 | (junction repair) |

[d] | 441 | 4 | -> | 1 | (junction) |

[k] | 441 | 0 | -> | 4 | (junction) |

[e] | 440 | 1 | -> | 0 | (junction) |

[g] | 440 | 0 | -> | 4 | (gap repair, collision, and junction) |

[f] | 411 | 0 | -> | 4 | (junction) |

[c] | 410 | 0 | -> | 4 | (wire) |

[a] | 410 | 4 | -> | 1 | (wire) |

[i] | 410 | 1 | -> | 0 | (junction) |

[b] | 400 | 1 | -> | 0 | (wire) |

[h] | 100 | 1 | -> | 4 | (collision, junction) |

[m] | 100 | 4 | -> | 1 | (repair wire end; period 3 oscillator) |

[n] | 000 | 1 | -> | 4 | (repair wire end) |

rest | ??? | x | -> | x | (no change) |

There are 10 possible combinations of states of three neighbors. Times the 3 possible states of the cell itself yields 30 possible transitions. Only the transitions which change the cell's state are listed; the others leave it unchanged.

In the automata diagrams state "1" is coded by red (half-size triangle), state "4" by black, and state "0" by white. In figure 1 nine successive generations scanning from the top left to right are shown. Subsequent figures show just the initial state and are linked to PDFs showing one generation per page.

There are interesting symmetries in the application of these rules to the examples here.

- "4" never becomes "0";
- "1" never stays "1"; and
- "0" never becomes "1".

Rules [a], [b], and [c] are needed for signal propagation in wires shown
in figure 1. Wires can bend 60 degrees. A bend behaves like a straight
wire because the rules do not distinguish between one neighbor and
another. The minimum radius is 2; a turn can wrap around the minimal
hexagon.

Rules [d], [e], [f], and [g] give the junction the property that a
signal coming in on one leg exits via the other two; demonstrated
twice in figure 4. The minimum distance between junction points such
that they don't interfere is 3.

Rule [i] allows the junction to function even if the signals are one
step out of phase on arrival. The result, as shown in the bottom of
figure 6 is that one signal exits on the remaining leg. This is in
effect the same as if the delayed signal were delayed more than one
step; being annihilated by the earlier signal having split through the
junction.

- A pulse on just one leg exits on the two adjacent legs;
- pulses on opposite legs exit on their two adjacent legs;
- pulses on adjacent legs exit on the two opposite legs; and
- three simultaneous pulses combine to one exiting the other leg.

The two synchronizers in figure 14 receive pulses at different times showing the full 12-clock (out of 18) window for inputs to suppress the synchronized output pulse. Notice that the sequence of pulses exiting to right is the same, even though the input pulse arrivals differ by 12 generations.

The machinery of mathematical proofs rarely makes practical devices. What sort of computations is this automaton suited for?

- Acting as storage, long folded delays lines (wires) approach 1/6
bit per cell in density. Individual bit storage would require 15
cells at a minimum; a hexagon plus half of its shared 18-cell border.
- With a crossover 15 times larger than an exclusive-or gate,
bit-parallel busses would be space-inefficient. But serial logic is
small and quite well suited to delay-line storage.

Copyright 1974, 2002, 2004 Aubrey Jaffer

I am a guest and not a member of the MIT Computer Science and Artificial Intelligence Laboratory.
My actions and comments do not reflect in any way on MIT. | ||

Nano-Cellular Automata | ||

agj @ alum.mit.edu | Go Figure! |