Elementary Cellular Automaton and Its Applications in Computer Science
Sign up for FREE 1 month of Kindle and read all our books for free.
Get FREE domain for 1st year and build your brand new site
This article explains 1Dimensional Elementary Cellular Automaton, and its applications, and mathematical explanation of concept behind with code in python.
Introduction
Nature has inspired many fields of study, even in computer science. Genetic Algorithms, Machine Learning etc. Another such field, less known but highly impactful is Cellular Automaton.
Aim and PreRequisites
This article is a beginner's level introduction to Cellular Automaton with mathematical and coding support. Prerequisites for reading this article are the motivation to explore a new domain of study, and love of Nature and Computers.
These images explain how Cellular Automaton is not a concept created by Computer Scientists, but exists in nature. Look how patterns similar to Wolfram's Rule 30 of Cellular Automaton (below) is generated in the Textile Cone Shell (above).
What is Cellular Automaton
Cellular Automaton is an evolutionary algorithm, where certain Cell (smallest individual agent of the system) evolves/changes state, based on various rules of evolution. This agent can have multiple states, but exists in a single state at a given time/generation.
If the rules of evolution of a cell's state is based on the state of its neighbors, it is called an
Elementary Cellular Automaton
.
To simplify things, let us first describe a few things :

CELL
A cell is an individual data block, which can be in multiple states. These states can be Colors, Numbers, Boolean (True/False) etc. 
GENERATION
A set of Cells make up a generation. This generation evolves over time, i.e. some rules are applied on the cells so that its state changes. After each iteration of the application of rules, the Generation evolves to the next Generation.
Evolve(Generation_{i},Rules) = Generation_{i+1}
SYSTEM
A set of generations, form a System.
1D Cellular Automaton
Let us consider a 1D system, i.e. each generation is an array of Cells.
For simplicity, let us take the cell to be either in state Yes(1)
or No(0)
.
Now let us see evolution of a particular cell, C_{i}
For a particular Generation, let
{C_{i1},C_{i},C_{i+1}} = {1,1,0}
Now, we can assign a rule, for example, if {1,1,0} state is found for C_{i} and its neighbors, the next Generation of C_{i} will be 1.
This can be written as a MAPPING,
(Note that B_{0}, B_{1}...B_{m} are 0, 1,...m ^{th} bits (1 or 0) of the m bit binary number n
which is written as Rule n
or R_{n} )
Note that this forms a rule, which can be abbreviated as an 8 bit binary number, where its i^{th} bit represents the value B_{i}
Now we can abbreviate rule, from a set of 3x1 mapping to an 8 bit binary number, from 0 to 255.
Let us denote the rules as R_{0},R_{1},R_{2}...R_{255} for this article.
Let the Array for t^{th} generation be A_{t}. Now, one Dimensional cellular automaton can be viewed as an array (or vector) transformation :
Transform(A_{t},R_{n}) = A_{t+1}
And, the entire system becomes, a 2D matrix of m generations, each with n cells :
Code for the following transformation in python is
def cell_transform(a,b,c,R): # returns output of {C_(i1),C_(i),C_(i+1)} by rule R
n = (a<<2) + (b<<1) + c
return (R >> n) & 1
def transform(A,R): # R is a number between 0 and 255
B = []
for i in range(len(A)):
B.append(cell_transform(A[i1],A[i],A[(i+1)%len(A)]))
return B # next generation
Now, to generate a system, as a Matrix, which contains multiple generations,
# Initial State is A0 and rule is R, and the system consists of m generations
def generate_system(A0,R,m):
S = []
for i in range(m):
S.append(A0)
A0 = transform(A0,R)
return S
Question
If a 1Dimensional Cellular Automaton evolves based on its 1^{st} and 2^{nd} immediate neighbors(2 cells on both left and right of observed cell), what is the range of the Valid Rules for this system?
Applications of 1Dimensional elementary cellular automaton
1. Fractals Generation
Interestingly, the Sierpinski Triangle is a result of the result of 1D Elementary Cellular Automaton. It is a result of Rule 90.
Visualization, is 1 for color, and 0 for whitespace, in a 2D matrix.
Following are some visualizations and their rules mentioned
RULE 90  SierpiΕski triangle
RULE 30 Wolfram's Rule 30
2. Cryptography
Cellular Automaton is also Applied in Cryptography. The Rule 30 Can be used as a pseudorandom number generator.
I have worked on the cryptography application of the topic, and the code, theory and analysis of the same can be found here.
Notice now the wolfram's rule 30 image above can be random if initial conditions are changed. Using this, if we use a seed value for the initial conditions of Wolfram's Rule 30, we can get a Pseudo Random Number Generator, which can be used for Encryption. This is the basic idea of the algorithm for encryption provided in the github repository here.
3. Error Correction Coding
Cellular Automation is applied in error correction and detection codes. The advantage over conventional method is faster decoding time with Cell Automation.
D. Roy Chowdhury, S. Basu, I. Sen Gupta, and P. Pal Chaudhuri have published this paper discussing one such decoder, a single bit error correction, double bit error detection (SECDED) scheme.
4. Computer Processors
Multiple 1D and 2D Cellular Automaton systems have been proven Turing complete. This implies cellular Automaton systems, can be built as a processor.
There has been no existing implementations, but it can be argued, that taking quantum states of individual particles as CA States, or mimicing intercellular interactions by charge transfer, magnetism, vibration etc., nanoprocessors, or even quantum processors can be a reality.
5. Compression, Simulation, Graphics and Music Generation
This is another interesting application of cellular automaton. It is able to simulate simple multiagent independent systems, dynamic models like fluid flows etc. Cell Automation is used in image and Data compression also. Olu Lafe has written an excellent paper in this domain (link). It is also used in multimedia generation. Below is a video of generating piano music using 1D cellular automaton system.
Conclusion
In this article, we learnt about Cellular Automaton on an elementary level. This article's intention was to get us started towards cellular automaton, and try out some cool applications too maybe!
The next level of this is the 2D cellular transform, and then 3D cellular transform and Cellular Automaton Transform (CAT). If you found this interesting, then do explore the 2D variant, and there will you find the Game of Life (repo providing nice visualization, moderate explaination and code in javascript for the Conway's Game of Life),a zero player game, which has a lot to offer.