Algebraic Circuits

Notes

Applications of Algebraic Circuits to Cellular Automata

The Connection:

The book defines algebraic circuits in two main ways:

1. Digital circuits whose behavior can be linked to an algebraic structure, often a polynomial, where the circuit's evolution mirrors the polynomial's algebraic properties. Cellular automata fall into this category.
2. Digital circuits designed to implement operations within specific algebraic structures, such as Galois fields (finite fields).

Conway's Game of Life, with its grid of cells evolving based on simple rules concerning their neighbors, is a prime example of a cellular automaton. Although its rules are non-linear, leading to complex emergent behavior, its operation can be conceptualized in terms of circuitry and analyzed using algebraic methods.

Applications and Interpretations:

• Computational Universality and Circuit Implementation: A key aspect of Conway's Game of Life is its Turing completeness, meaning it possesses the computational power of a universal Turing machine. This implies that any algorithmic computation, including the operations of digital logic circuits, can theoretically be performed within the Game of Life. Researchers have demonstrated how to construct logic gates (like NOT and AND gates) using specific patterns of live and dead cells, such as "gliders" and "glider guns," which interact in predictable ways to perform logical operations. These constructed logic gates are, in essence, a form of algebraic circuit implemented within the cellular automaton framework.

• State Transition and Algebraic Representation: The evolution of each cell in the Game of Life is determined by the state of its eight neighbors (the Moore neighborhood). This transition rule can be expressed as a logical function, which in turn can be implemented by a digital logic circuit. Furthermore, algebraic approaches, such as using state transition matrices, can be employed to represent and analyze the dynamics of the Game of Life, even for its complex, non-linear rules. While the provided book discusses characteristic polynomials primarily for linear CAs, the general concept of using algebraic structures to describe CA behavior is relevant.

• Modeling and Analysis: The study of cellular automata like the Game of Life often involves analyzing their emergent patterns, stability, and growth. Algebraic properties can aid in this analysis. For instance, understanding the algebraic structure underlying simpler CAs can provide insights into methodologies for analyzing more complex ones. The book "Algebraic Circuits" details how characteristic polynomials describe the temporal evolution of linear CAs, and similar algebraic thinking can be applied, albeit with more complexity, to non-linear systems.

• Hardware Implementation of CAs: The book "Algebraic Circuits" describes how cellular automata are structures composed of cells (like flip-flops) with local interconnections, making them suitable for hardware implementation. While Conway's Game of Life is often simulated in software, its rules could be directly translated into a hardware algebraic circuit consisting of an array of logic units, each representing a cell and connected to its neighbors.

Translating Conway's Game of Life to an Algebraic Circuit

Breaking down how a cellular automaton like Conway's Game of Life, with its specific neighborhood and rules, can be translated into an algebraic circuit representation:

The foundation for this translation lies in representing the state of each cell and the rules governing its transition to the next state using algebraic (specifically Boolean, in this case) expressions. These expressions then directly map to logic circuits.

The Algebraic Circuits book discusses how the behavior of Cellular Automata (CAs) can be described using algebraic structures like polynomials, particularly for linear CAs.

However, Conway's Game of Life is non-linear.

The principle of defining the local update rule algebraically still applies, though, so we can go through the step-by-step of constructing an algebraic circuit for a single cell in Conway's Game of Life.

Here's a step-by-step construction of the algebraic circuit representation for a single cell in Conway's Game of Life:

1. Define States and Neighborhood

• Cell States: Conway's Game of Life has two states for each cell:
  • Dead: Represented by the value 0.
  • Alive: Represented by the value 1.
  • These states naturally align with elements in the Galois Field GF(2)

• Neighborhood: The game uses a 2D grid. Each cell's next state is determined by its current state and the states of its eight immediate neighbors (the Moore neighborhood).
• Let c be the current state of the cell in question ($ c \in \{0,1\} $).
• Let $ n_1, n_2, \dots, n_8 $ be the states of the 8 neighbors, each neighbor being 0 or 1.

2. Define Conway's Game of Life Rules Algebraically:

• Rules of cell transition to next state:
  • Survival: Live cell c = 1 stay alive if there are 2 or 3 live neighbors.
  • Birth: Dead cell c = 0 becomes alive if there are 3 live neighbors.
  • Death: in all other cases, live cells will die (due to overpopulation or underpopulation)

• Let S be sum of states of 8 neighbors: $ S = \sum_{i=1}^{8} n_i $. This means S is an integer from 0 to 8

3. Construct Boolean Polynomial for Next State

Define a boolean indicator variable P2, P3 such that P2 = 1 if the cell has 2 neighbors (S = 2), and is 0 otherwise, and P3 = 1 if the cell has 3 neighbors, and is 0 otherwise

The conditions that must be met for the cell to be alive at the next generation is:

• it is currently alive, c = 1, and P2 = 1 or P3 = 1
• or,
• it is currently dead, c = 0, and P3 = 1

Translating into a boolean expression for the new cell state, c prime:

$ c^{\prime} = \left( c \land \left( P_2 \lor P_3 \right) \right) \lor \left( \neg c \land P_3 \right) $

We mentioned above the binary nature of the Game of Life lends itself to representation on the Galois Field GF(2), so this gives us a way to write and evaluate polynomials on GF(2).

On GF(2), the AND operation is multiplication, the NOT c operation is $ 1 \oplus c $, and the OR operation is $ A \oplus B \oplus AB $ (or just $ A \oplus B $ if independent)

Now there are two conditions where c will be alive at the end of the round:

• If c survives (is alive at the beginning), and meets those survival criteria
• If c is born (is dead at the beginning), and meets those birth criteria

So when we translate the logical expression for c prime above into a binary operation on GF(2), we can start by XORing those two expressions:

$ c^{\prime} = \mbox{SurvivalTerm} \oplus \mbox{BirthTerm} $

Now handle each term one at a time:

Survival term:

$ \mbox{SurvivalTerm} = c \cdot \left( P_2 \lor P_3 \right) = c \cdot \left( P_2 \oplus P_3 \right) $

Birth term:

$ \mbox{BirthTerm} = \left( 1 \oplus c \right) \cdot P_3 $

So now we have our algebraic expression for the next state:

$ c^{\prime} = \left[ c \cdot \left( P_2 \oplus P_3 \right) \right] \oplus \left[ \left( 1 \cdot c \right) \cdot P_3 \right] $

(note that the multiplication operator would involve AND gates, and the bitwise oplus operator would involve XOR gates)

The terms $ P_2(n_1, \dots, n_8), P_3(n_1, \dots, n_8) $ are symmetric boolean functions of the neighbor states.

4. Algebraic Circuit Representation

• Boolean polynomial derived above defines the algebraic circuit for a single cell

• Circuit components:
  • Neighbor summation circuit - takes the state of the 8 neighbors as input, calculates sum S; can be implemented using a network of full adders and half adders; outputs a 4-bit binary word (there are 9 possible states, requiring slightly more than 3 bits), representing the count S
  • Sum comparison logic - indicator circuits for P2 and P3, so that we know when we meet the P2 or P3 condition; P2 circuit outputs 1 if $ S = (0010)_2 $, 0 otherwise, and P3 circuit outputs 1 if $ S = (0011)_2 $, 0 otherwise

• Applying the logic:
  • Use logic gates and/xor/not, or GF(2) equivalents like multiplication/addition, to get the next state

Now, we'e assembled an algebraic circuit for a single cell, and it can be connected to 8 other algebraic circuits for the neighbor cells, and if all circuits were driven by a common clock, they could all update synchronously.

Connecting to Turing Completeness and Life in Life

This concept of treating each cell as a circuit, and treating the entire grid as a set of interconnected circuits, highlights a connection to the mind-blowing fact that you can use the Game of Life to implement circuits that perform logical operations like AND and XOR, which allow you to implement the circuits that run the Game of Life, in the Game of Life.

YouTube video: "Life in life" by user mrphlip (Philip Bradbury): https://www.youtube.com/watch?v=xP5-iIeKXE8

...

Video shows a large grid of Game of Life patterns where each "metapixel" (a large, stable or oscillating collection of Game of Life cells) itself represents a single cell of a higher-level Game of Life grid. The interactions between these metapixels are engineered to follow the rules of Conway's Game of Life, simulating the game at a macroscopic level using the game's own microscopic rules.

The Golly software (often mentioned in the descriptions of these videos, e.g.,) is a crucial tool for exploring such complex patterns and for running scripts that can generate and manage these "Life in Life" constructions like the OTCA Metapixel.

Emergent behavior: a set of simple rules can lead to layers upon layers of emergent complexity and computation.

Complications

As mentioned above, Conway's Game of Life is non-linear, so the rule to update an entire grid to find its next state is not simply an operation that can be applied to a bitvector or done in one go.

To express this a different way,

$ c^{\prime} = f(c, n_1, \dots, n_8) $

is a nonlinear function. But any boolaen function can be uniquely expressed as a polynomial in GF(2) (Reed-Muller expansion). The polynomial that represents the local update rule is the algebraic core of the circuit of a single cell.