Ternary gate automata

3 Jan 2024

$$ \newcommand{\Z}{\mathbb{Z}} $$

In high school, I learned that if you draw lines on a sheet of graph paper according to a simple set of rules, it generates a Sierpinski triangle:

Specifically, the rules are:

Start at the top, and add lines one row at a time.
A single diagonal line splits into two diagonal lines in the next row.
But when two lines collide, they “cancel” and don’t create any lines in the next row.

I realized at the time that this process could be generalized to a large number of variants. In particular, I came up with the following rule, which includes vertical lines in addition to diagonal lines:

A single vertical line splits into two diagonal lines.
A single diagonal line splits into a vertical line along with a diagonal line in the opposite direction.
When two or three lines collide, they cancel.

This rule can be illustrated with the following diagram:

The diagram shows what happens to each of the seven possible inputs. In this rule, all of the two- and three-line inputs cancel (produce no output), but one can imagine other rules in which that is not the case.

If you start with a single vertical line and repeatedly apply the rule above (in this case, for 100 rows or “generations”), you get the following image:

(You may notice that lines sometimes cross without cancelling. That’s because the rule operates in discrete steps, so lines always go from one row to the next without affecting each other.)

The sides of this triangular pattern have slopes of 2, and repeat every 10 or 20 rows (depending on how much you count as the “side”). The center, meanwhile, appears to behave chaotically. Along the line of symmetry, there is a vertical gutter which (after the first few rows) contains only “V” shapes. These “V” shapes repeat at irregular intervals, occuring in chains in which several “V” shapes are each separated by just one row, with larger gaps in between these chains. The lengths of the chains are, from top to bottom, 1, 6, 1, 1, 1, 1, 1, 6, 7, 3, …

By generating 600 rows of the pattern instead of just 100, one finds that the next values in this sequence are 4, 9, 1, 1, 1, 1, 1, 4, 11, 6, 1, 5, 1, 7, 7, 3, 6, 1 (!), 2, 4, 5, 13, 5, 6, 1, 1, 1, 6, 1, 1, 6, 7, 1, 6, 1, 1, 5, 4, 1, 1, … The exclamation point marks a location in which the central gutter briefly widens into a triangular bubble, something I had not expected. (Here’s the 600-row version of the image, if you’re curious. It’s 36 times larger, so it may take some time to load.)

The following pattern is what generates the vertical chains of “V” shapes:

Unlike the triangular pattern from before, this pattern doesn’t grow as you go down, and instead repeats itself every 2 rows. If you’re familiar with Game of Life terminology, this means it’s a “period-2 oscillator.”

As I suggested earlier, this rule is just one of a large class of rules which I call “ternary gate automata.”

Ternary gate automata

A ternary gate automaton is like an elementary cellular automaton, except that information is not stored in the “cells” themselves, but in signals (drawn as lines) that go from one point to another. Every time-step (or “generation”, represented visually as a row), each point can send a signal to one or more of its three neighbors, including itself. Which signals it sends out depends on which signals it receives, in a way that differs between rules. There are 2³ = 8 inputs a point can receive, and 2³ = 8 possible outputs:

A ternary gate automaton is defined by a function from the set of input configurations to the set of output configurations. This means that there are 8⁸ = 2²⁴ = 16,777,216 ternary gate automata in total. However, it is often useful to consider the subset of TGAs that map the empty input to the empty output. I call these “vacuum-preserving TGAs,” and they are easier to simulate on a computer (or by hand) because finite patterns remain finite. There are 8⁷ = 2²¹ = 2,097,152 vacuum-preserving TGAs.

A TGA can be specified by a diagram showing what happens to each of the eight input configurations. However, it is often useful to have a more compact, text-based representation. The first step in creating such a representation is assigning each input and output configuration a digit:

If you’re familiar with binary, it should be clear why I chose the correspondence above. For example, 6, or 110 in binary, represents the configuration where the left and middle signals are on, and the right signal is off.

With this correspondence in mind, a TGA can now be specified by eight digits: the first digit is the output when the input is 0, the second digit is the output when the input is 1, and so on. I will call this the “rulestring” of the automaton. For example, the chaotic automaton from earlier has the rulestring 03506000. An automaton is vacuum-preserving if and only if its rulestring begins with the digit 0, so vacuum-preserving automata can be specified with just seven digits by dropping the leading zero.

Counting TGAs up to equivalence

I said earlier that there are 2²⁴ ternary gate automata. While this is correct, certain TGAs are essentially equivalent. For example, the rules 5176002 and 3405072 are reflections of each other:

Although these are two different TGAs, they are related by a simple transformation. This raises the question: how many essentially different TGAs are there? To answer this, we must first define what it means for two automata to be equivalent.

There are four simple and reversible ways to transform a TGA into another TGA:

Do nothing.
Reflect across the vertical axis.
Replace “on” signals with “off” signals and vice versa.
Swap “on” signals with “off” signals and reflect across the vertical axis.

Two automata are equivalent if one can be transformed into the other via one of these transformations. Since this set of transformations is closed under composition, we can use a very useful theorem from group theory known as Burnside’s lemma to find the number of classes of equivalent automata.

Burnside’s lemma states that this number is (n₁ + n₂ + n₃ + n₄) / 4, where n_i is the number of automata fixed by transformation i. Clearly, all 2²⁴ automata are fixed by transformation 1 (doing nothing). Moreover, 2¹⁴ automata are fixed by transformation 2 (reflection), 2¹² automata are fixed by transformation 3 (signal inversion), and another 2¹² automata are fixed by transformation 4 (reflection and signal inversion). Thus the number of TGAs up to equivalence is (2²⁴ + 2¹⁴ + 2¹² + 2¹²) / 4 = 2²² + 2¹² + 2¹¹ = 4,200,448.

We can use the same method to calculate the number of vacuum-preserving TGAs up to equivalence, arriving at an answer of 2¹⁹ + 2¹⁰ + 2⁸ = 525,568.

In summary:

Number of TGAs	Total	Up to equivalence
All	2²⁴ = 16,777,216	2²² + 2¹² + 2¹¹ = 4,200,448
Vacuum-preserving	2²¹ = 2,097,152	2¹⁹ + 2¹⁰ + 2⁸ = 525,568

Connection with cellular automata

Elementary cellular automata are a well-known class of cellular automata. Like ternary gate automata, they are one-dimensional (or two-dimensional if you count time as a dimension). However, in an ECA, the information is stored in the points themselves rather than in signals passing between them. An equivalent framing is that the points do send signals between them, but they must send the same signal to each of their neighbors. In other words, an ECA is a TGA where the only outputs are “0” and “7”:

Conversely, ternary gate automata can be emulated by cellular automata, though not usually by elementary cellular automata. One way to do this is to associate each output configuration with a block of three cells.

In a TGA, the output at a point in the next generation is determined by the “right” signal coming from the point to its left, the “down” signal coming from itself, and the “left” signal coming from the point to its right. So in the corresponding cellular automaton, the state of each cell in a block in the next generation is determined by

The rightmost cell of the block to its left,
The center cell of the block,
The leftmost cell of the block to its right.

In other words, if we number the cells such that the center cell of each block is a multiple of three, then the states of the cells 3n - 1, 3n, and 3n + 1 in the next generation are determined by the current states of the cells 3n - 2, 3n, and 3n + 2.

General gate automata

The name “ternary gate automata” is due to the fact that each point has three neighbors (points that it directly affects): itself, and the points to its left and right. In general, the points in a gate automaton can have more than three neighbors, and the automaton need not be one-dimensional. There can also be more than two signal types. (In a TGA, the only signal types are “off” and “on”.) Gate automata are similar to cellular automata, the difference being that in a gate automaton, points can send a different signal to each of their neighbors, while in a cellular automaton, points must send the same signal to each of their neighbors.

Before laying out the general definition of “gate automaton,” I will give a formal definition of “ternary gate automaton.” A TGA is defined by a local transition function $f : B^3 \to B^3$, where $B$ is the set $\{0, 1\}$ and 3 is the set $\{-1, 0, 1\}$, so that elements of $B^3$ correspond to input/output configurations in a natural way. The global transition function $f' : (B^3)^\Z \to (B^3)^\Z$ is then defined in terms of the local transition function as $f'(s)(n) = f(s(n - 1)(1), s(n)(0), s(n + 1)(-1))$. In words, this says that “given the current global state $s$, represented as an integer-indexed sequence of output configurations, the output in the next generation at point $n$ is the result of applying the local transition function to the rightward signal coming from point $n - 1$, the downward signal coming from point $n$, and the leftward signal coming from point $n + 1$.”

The formal definition of a general gate automaton is similar, but with more parameters. Explicitly, a gate automaton is specified by the following:

A positive integer $n$, the dimension.
A set $S$ of signal types.
A finite subset $U \subset \Z^n$ of output signal directions.
A local transition function $f : S^{-U} \to S^U$, where $-U$ is the set of input directions $\{-u : u \in U\}$.

The global transition function $f' : (S^U)^{(\Z^n)} \to (S^U)^{(\Z^n)}$ is then defined as $f'(s)(p) = f(u \mapsto s(p + u)(-u))$. It is kind of confusing to keep track of all of the sets and functions involved in this definition, but I promise it makes sense if you look at it for a while.

A ternary gate automaton is a gate automaton in which $n = 1$, $S = B = \{0, 1\}$, and $U = 3 = \{-1, 0, 1\}$.

Computer program

I wrote a computer program for running ternary gate automata, which I used to generate some of the images in this article. The program is written in C, consists of just one file, and doesn’t require any non-standard or OS-specific libraries, so you should be able to compile it easily on any computer. The way the image generation works is very simple: the program just creates an SVG file and adds text to it.