Linear Algebric Approach to GoL Rules and 3-state GoL

[AtlasYang]

Due to image uploading problem, please check the link below.
https://www.reddit.com/r/cellular_autom ... e_of_life/

So, I recently studied Linear Algebra and suddenly, I thought that maybe I could represent the various rules of CGoL in the form of Matrix. So, I came up with the idea that, in 3 * 3 grid, determining the next state of center cell (which is the role of GoL rules) using 1 matrix T and 2 vectors n and s.
T stands for “state Transition matrix”, and is namely the transition matrix in a * b space, given that a is the number of all states that single cell can have, and b is the number of all cells constituting a judgment unit (in original 2D GoL, b is 9).[1]
n stands for “number of both Neighboring and surviving cells vector” and is so called ‘one-hot encoded vector’. For example, if one cell is neighboring 5 surviving cells, the n of the cell can be expressed as [0 0 0 0 0 1 0 0 0]^T(row vector form).
s stands for “current State of the cell vector” and is also one-hot encoded vector. For example, in original CGoL, if one cell has a living state, the s of this cell can be expressed as [0 1]^T(row vector form).
And not surprisingly, I decided to call this notation “TNS notation”. And I also I found the following small rules.

T∈R^(a×b)
n∈R^b
s∈R^a
Where a and b are given as in [1]



Here is example representation of one cell in Conway’s original rule, S/B = 23/3.
T=[■(0&0&0&1&0&0&0&0&0@0&0&1&1&0&0&0&0&0)]

n=[█(0@0@0@1@0@0@0@0@0)],s=[█(1@0)]

Tn=[█(1@1)],(Tn)^T s=1

From vector n, you can find that this cell has 3 neighboring live cells, and from vector s, current state is ‘dead’. And through basic matrix vector algebra, you can find that (Tn)^T s=1, where ‘1’ means “next state of this cell is live”.
I personally think that the TNS notation is the simplest way for both visualizing and calculating purpose. When you code CGoL simulation program, all you need is state transition matrix, two cell vectors, and some basic LA operations! (Numpy works well)
However, I did not want to stop here. So, I decided to expand the dimension of the matrix and vectors, which means adding another states cell can have (a) or increasing neighboring cells(b). As a matter of fact, I found that I could represent the general rules of 3D CGoL by making b=27.
Sadly, I could not make Pygame program that can visualize 3D CGoL. So, I increased a value, which leads to additional 3rd state. In this article and related code, 0 represents dead cell, 1 represents live cell, and 2 represents another state of live cell.

T=[■(0&0&0&1&2&0&0&0&0@0&0&1&2&0&0&0&0&0@0&0&2&1&0&0&0&0&0)]

This is 9 * 3 state transition matrix I made for 3-state GoL simulation. The matrix above means that, if the number of neighboring live (either 1 or 2) cells is 0 or 1, the cell will die. And if the number is 2, the cell will not change its state. And If the number is 3, 0-state(dead) changes to 1-state, 1-state to 2-state, and 2-state to 1-state. If the number is 4, 0-state changes to 2-state, and all live cells die. If the number is larger than 5, all cells die.
You will need lots of “If” in your program in order to code it without state transition matrix. With T, you can express the rule of your own GoL clearer than any other method.

Thank you for reading this article. And I leave some aesthetic patterns 3-state GoL generates.
In my github link below, there is a source code of Python CGoL Simulation code using Pygame. It’s very lite (190 lines) and can be easily customized. Please download it and try some of 3-state transition function. And if you find cool transition matrix playing with this program, please share it wherever you want to.
Github Link:
(Actually, I have no idea about how exactly Github works. It is just another Dropbox to me)

And if you have any question, opinion, or ideas, please send it to my email. I really appreciate it.
Email: [email protected]

[wzkchem5]

It is always possible to write a finite mapping as a matrix, and this provides no additional insight or computational convenience. Yes by writing the transformation rule as a matrix operation you avoid some if's, but you also slow down the simulation considerably, so this is not really worthwhile.

[AtlasYang]

Thank you for your advice!

[saolof]

The totalistic step is a linear map on the other hand. Convolution with the kernel [1 1 1; 1 0 1; 1 1 1] . Followed by a very nonlinear elementwise operation (mapping 2 or 3 to one and other values to zero), and is what many of the 1-line code golf variants you'll see on the internet do.

Mapping 2 or 3 to 1 and other numbers to zero can be done rather efficiently using bitwise operations though. For example, something like (!sum >> 3) & (!sum >> 2) & (sum >> 1) & (center | sum) should give the correct answer, and is completely branchless. No ifs required.

If you are working in Python, using a trick like this one with numpy is probably one of the easiest ways to get a game of life implementation running reasonably fast.

[pcallahan]

I didn't read your framework carefully, but the problem is that it's not a linear system. An example of a linear CA rule is XOR in which the next state of a cell is the sum of its neighbors mod 2. Because it's linear, you can compose generations using matrix operations, and it's easy to predict.

In CGOL, the sum of neighbors is linear, but the threshold rule is not. You can make the non-linear part very simple. E.g. if you find 2*(sum of neighbors)+cell then the next generation is 1 as long as that value is between 5 and 7 (2*2 + 1, 3*2 + 0, 3*2 +1). This might help you optimize the generation step with certain kinds of hardware (who knows?) but it is still non-linear. If you try to compose the rule over several generations, the thresholds become increasingly complex (E.g. Write out a simple piecewise linear function f(x) and now write f(f(x)), f(f(f(x))), etc. It gets hairy very fast)

So an understanding of linear algebra may provide some tools for representing CA rules, but they don't really get you that far in analysis. Because CGOL is a universal system, it is as intractable as any other universal computer.

[saolof]

It's maybe worth noting that a few other rules can be expressed as linear maps over other rings however. For example, looking at 1d cell automata, the state transition for rule 90 is a linear map over the field with two elements. For that rule, any initial state can be viewed as a xor sum of single-cell excitations. So if you have the time evolution for the initial state with only one cell on, sums of shifts of that state will give you the time evolution of any other initial state.

In that sense, there is an exact analogy between rule 90 and linear differential equations. But that applies only to a tiny subset of rules, the game of life is not among them, and nonlinearity is likely required for interesting behaviour. Afaik for 2d cell automata, the Fredkin and Replicator rules are linear.

There might also be some equivalent of integrable models for cell automata, where the time evolution is not linear, but where you can still break it up into soliton excitations (which are preserved during interactions up to a phase shift, so their interaction is nonlinear but constrained) and get a reasonably simple time evolution, but that is also unlikely to lead you anywhere for the GOL.

Both of these viewpoints could be useful for specific engineered patterns though. For example, the replicator in Highlife emulates rule 90.