Awk Programming III: the One-Dimensional Cellular Automaton

Cellular automata (CA) is a vast and interesting topic of computer science and mathematics with important applications in many areas of science. They are used to describe deterministic processes involving transitions (i.e. defined by rules) of the state of entities called cells. The game of life (see my previous post) is a famous example of a two-dimensional cellular automaton. However, even simpler cellular automata than the game of Life automata can show peculiar behavior. The famous mathematician Stephan Wolfram has dedicated a lot of time to study such peculiar computational creatures. In  A New Kind of New Science, he gives a detailed description of CA of different types. However, my first encounter with CA occurred in the ’80s within the pages of Le Science magazine (the Italian edition of Scientific American). In particular, I was inspired by the amusing A. K. Dewdney’s Computer Recreations department that every month was a source of very interesting programming ideas.  Dewdney described different types of cellular automata from the game of Life to the one-dimensional (1D) ones.  In this blog, I am going to present a program written in awk language that simulates 1D CA on a computer terminal.

A 1D CA is composed of a sequence of entities called cells each of them characterized by a state (designed by a number) and a set of rules that change this state in time. The CA is a dynamical system iterative system that changes the state of all the cells at the same time (parallelism) at each iteration step. The simplest CA  is characterized by a binary state (0,1, as for the game of Life). However, it is possible to design more complex automaton with more states. At the beginning of a CA interaction (step=0), each CA cell is assigned to an initial state. At each iteration step, the state of each cell is updated by the same set of transition rules (homogeneity) defined by the state of the neighbor cells (locality). In the simplest 1D CA, the two first neighbor cells are considered.

Transition functions. The transitions for this simple model of CA can be classified using a three-bit code system as shown in Figure 1. The three upper square defines a portion of the automaton, and we are interested to follow the transition of the central cell. The two side cells are the first neighbor cells. The single cell below represents the central cell after the transition. Each of the three cells can assume the 8 possible configurations depicted in Figure 1. We can assign 2^8=256 possible output states defined by the 8 binary digits. For example in Figure 1, the output state 11111111 is associated with the number decimal 255. In this way,  we can enumerate all the possible automata associated with the defined rule.

Automata.jpg

Figure 1: definition of the 255 rule of the 1D binary CA.

CA classification. We can extend the classification to automata by adding more states but the number of configurations will enormously increase. For example, an automaton defined by three states (0,1,2) can have 3^3=27 states and this gives 3^27\approx 10^13 possible rules! The same happens if we extend the number of neighborhood cells used to define the state of the central one. For example, by changing from 2 to 4, the number of neighborhood-states grows to 2^5=32 still skyrocketing, although less impressively than the previous case,  again the number of possible rules to 2^32\approx 10^10.

Boundary conditions. Three type of boundary conditions (BC) can be adopted for 1D CA (see Figure 2). In the reflective boundary conditions (RBC), the previous of the first and the subsequent of the last (n) cell of the automaton assume respectively the same state of the two considered cells. While in the Constant Boundary conditions (CBC) the two boundary cells of the automaton are keep to a constant state. Finally, in the Periodic Boundary Conditions (PBC), the extreme cells of the automaton are connected forming a ring.

Automata2

Figure 2: Type of boundary conditions for 1D CA.

A 1D CA implementation in AWK language

The awk program reported in the appendix implements the 1D CA described in the previous paragraph.  The evolution of the CA is represented by printing on the terminal a line at each generation where only the cells with value 1 are shown. For a better identification of the different generation, the program print in 7 different colors the different generation lines.

In the following figures, examples of outputs for some of the rules are reported. For a discussion of these results, the reader can refer to the reported literature.

rule126.jpeg

rule150.jpeg

Rule90

Rule30

Rule110

Bibliography

  1. S. Wolfram. A New Kind of Science.
  2. Helene Vivien. An Introduction to CELLULAR AUTOMATA. 
  3. A.K. Dewdney. The armchair Universe. WH. Freeman Company, 1988.
  4. M. Schroeder. Fractal, Chaos, Power Laws: minutes from an infinite paradise., Dover Ed., 1991.

 

APPENDIX

Usage:

Wolfram.awk code1 code2 ncycles random 

#!/usr/local/bin/gawk -f
#======================================================================
#
# NAME: Wolfram.awk
#
#======================================================================
# DESCRIPTION: Calculate mono dimensional automata
#
# USAGE
# Wolfram code1 code2 ncycles random
#
# INPUT:
#
# RULES SPECIFICATION
# The rules is specified with a decimal value from 0-255.
# It is possible to run different rules in sequence by
# specifying the starting and ending values
# ird : starting rule code (0-255)
# erd : end rule code
# TOPOLOGY SPECIFICATIONS
# N: lenght of the automaton
# BC: boundary conditions (not yet implemented)
# 0: reflective
# 1: constant
# 2: periodic
# SIMULATION SPCIFICATIONS
# ncycles: number of cycles
# STARTING CONFIGURATION
# random = 1 : Random generation
# random = 0 : with one cell at value 1 in position (pos)
# pos: position on the sequence for random=0 (1-N)
# OUTPUT:
#======================================================================
# DEVELOPED USING: gawk
# REQU. FUNCTIONS:
#
# get01string(innum, t, retstr, i) {
# This function return the binary representation of a decimal number
# and it was found on internet and written by Tim Sherwood
#
#======================================================================
# Author: Danilo Roccatano
# Version: 0.2
# Copyright (C): 2016 Danilo Roccatano
# Created: 2016-07-07 20:33
#======================================================================

BEGIN {
#
# INPUT SECTION
#
if (ARGC <3) {
print "SYNTAX: Wolfram code1 code2 ncycles "
exit -1
}
ird= ARGV[1]
erd= ARGV[2]
ncycles = 10
ncycles= ARGV[3]
BC=2 # set as periodic conditions
#
# Calculate the terminal size
#
TermSize()
#
# Take the lattice size from the number of column in the current
# terminal
#
N=cols
random = 0
pos = int(N/2)
#
# Uncomment the following line to have
# if you want to override the default values
# N= ARGV[3]
# random= ARGV[4]
# pos= ARGV[5]
# BC= ARGV[6]

nrl = erd-ird
for (i=0;i<=nrl;i++) {
lrule[i]=ird
ird++
}
#
# Define the automata transition rules and symbols
#
defrule()
#
# === PROGRAM START
# Loop on the rules
#
for (rl = 0; rl <= nrl;rl++) {
rd = lrule[rl]
tt=get01string( rd)
if (length(tt) <8) {
tt = "00000000" tt
rb = substr(tt,length(tt)-7,8)
} else {
rb = tt
}
print "AUTOMATA N:",rl," RULE TYPE: ",rb," (",rd,")"
#
# Generate the starting configuration
# random == 1 : Cells are randomly set to 1 or 0.
# random == 0 : Central cell set to 1 the rest to zero.
#
atms=GenConf(random,BC,N, atm)

#
# Time evolution of the automata
#
tatm=""
print substr(atms,2,length(atms)-2)
for (k=1;k<=ncycles;k++) {
#
# Loop on the automata
#
for (i=2;i<=N+1;i++) {

ncel=substr(atms,i-1,3)
#
# Apply the transition on the triplet ncel
#
for (j=0;j<8;j++) {
if (crul[j] ~ ncel) {
vv=substr(rb,j+1,1)
grap=grap sym[vv]
tatm=tatm vv
}
}
}
#
# Apply the BC conditions to the string tatm
# by adding to the offset cell at the beginning (0) and
# to the to the end (N) values accordingly to the BC variable setup as follows
#
# =0: reflective: add the values of the first and to the last cell of the current lattice, respectively.
# =1: constant: add the value in ccel variable
# =2: periodic: add the values of the last and the first cell of the current lattice, respectively.
#
if (BC == 0) {
tatm = substr(tatm,1,1) tatm substr(tatm,length(tatm),1)
}
else if (BC ==1) {
tatm = ccel tatm ccel
} else {
tatm = substr(tatm,length(tatm),1) tatm substr(tatm,1,1)
}
atms=tatm
tatm=""
#
# Print the new generation line in color with period 4
#
if (k%7 == 0) color(grap,"red")
if (k%7 == 1) color(grap,"blue")
if (k%7 == 2) color(grap,"green")
if (k%7 == 3) color(grap,"yellow")
if (k%7 == 4) color(grap,"purple")
if (k%7 == 5) color(grap,"cyan")
if (k%7 == 6) color(grap,"lightgray")
printf "\n"
grap=""
}
} # end cycle on the list of rules
}
function color(s,co) {
switch (co) {
case "red":
printf "\033[1;91m"s"\033[0m"
break
case "green":
printf "\033[1;32m"s"\033[0m"
break
case "blue":
printf "\033[1;34m"s"\033[0m"
break
case "yellow":
printf "\033[01;33m"s"\033[0m"
break
case "purple":
printf "\033[01;35m"s"\033[0m"
break
case "cyan":
printf "\033[01;36m"s"\033[0m"
break
case "lightgray":
printf "\033[01;37m"s"\033[0m"
}
}

func get01string(innum, t, retstr, i) {

# Return the binary representation of a decimal number
# by Tim Sherwood
retstr = "";
t=innum;
while( t )
{
if ( t%2==0 ) {
retstr = "0" retstr;
} else {
retstr = "1" retstr;
}
t = int(t/2);
}
return retstr;
}
func defrule() {
crul[0]="111"
crul[1]="110"
crul[2]="101"
crul[3]="100"
crul[4]="011"
crul[5]="010"
crul[6]="001"
crul[7]="000"
sym["0"]=" "
sym["1"]="█"
}

function TermSize() {
cmd="tput lines"
cmd | getline lines
lines=lines-2
cmd="tput cols"
cmd | getline cols
}
function GenConf(random,BC,N, atm,atms)
{
#
# Generate the starting configuration
# random == 1 : Cells are randomly set to 1 or 0.
# random == 0 : Central cell set to 1 the rest to zero.
#
if (random == 1) {
srand()
for (i=1;i<N+1;i++) {
a=rand()
val =1
vals = "1"
if (a<0.5) {
val = 0
vals = "0"
}
atm[i]=val
atms = atms vals
if (i==1) first = vals
}
} else {
atms=""
for (i=1;i<N+1;i++) {
vals = "0"
val=0
if (i== pos) { vals = "1";val=1}
atms = atms vals
atm[i]=val
if (i==1) first = vals
}
}
#
# Assign the last cell the same value of the first one
#
tatm=atms
if (BC == 0) {
tatm = substr(tatm,1,1) tatm substr(tatm,length(tatm),1)
}
else if (BC ==1) {
tatm = ccel tatm ccel
} else {
tatm = substr(tatm,length(tatm),1) tatm substr(tatm,1,1)
}
atms=tatm
return atms
}

 

 

About Danilo Roccatano

I have a Doctorate in chemistry at the University of Roma “La Sapienza”. I led educational and research activities at different universities in Italy, The Netherlands, Germany and now in the UK. I am fascinated by the study of nature with theoretical models and computational. For years, my scientific research is focused on the study of molecular systems of biological interest using the technique of Molecular Dynamics simulation. I have developed a server (the link is in one of my post) for statistical analysis at the amino acid level of the effect of random mutations induced by random mutagenesis methods. I am also very active in the didactic activity in physical chemistry, computational chemistry, and molecular modeling. I have several other interests and hobbies as video/photography, robotics, computer vision, electronics, programming, microscopy, entomology, recreational mathematics and computational linguistics.
This entry was posted in Leonardo's Corner, Programming, Science Topics. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s