1 Dimensional Boolean Cellular AutomataWritten by Paul BourkeSeptember 1997
A boolean cellular automata is a collection of cells that can be in one of two states, on and off, 1 or 0. The states of each cell varies in time depending on the connections, called rules, between the cells. While there can be any arbitrary set of connections/rules governing the system a particular one will be considered here, namely, a linear strip of cells where the output at each time step of each cell is a function of the current state of the cell and the state of its two immediate neighbours. As an extra nicety, the two ends of the strip of cell are connected together to form a continuous band. For any particular cell its next value is determined by 3 values, its state and the state of its neighbours. This leads to at most 8 different transitions. For example, the rules might be as follows: 100 -> 1, 101 -> 0, 110 -> 0, 111 -> 0 While not necessary, the rules decided upon apply to each cell in the strip. There are plenty of interesting dynamics possible without having variable rules across the strip. The simulation is "run" by setting an initial state and iteratively applying the rules for a number of time steps. In the first example the following rules are used. 100 -> 0, 101 -> 0, 110 -> 0, 111 -> 0 If this is written as a binary string in reverse, 00001010, it equals the decimal value 10 and is therefore called rule 10. The first few iterations are shown below for a strip of 78 cells, time runs down the page.
** * **** * *** * ****** ** *** ** ** ** ** * *** * **** ** * * *
* * * ** * ** ** ** ** ** * * * * * *
* * ** * ** ** ** ** ** * * * * * **
* * ** * ** ** ** ** ** * * * * * **
* * ** * ** ** ** ** ** * * * * * **
* * ** * ** ** ** ** ** * * * * * **
* * ** * ** ** ** ** ** * * * * * **
* ** * ** ** ** ** ** * * * * * ** *
* ** * ** ** ** ** ** * * * * * ** *
* ** * ** ** ** ** ** * * * * * ** *
** * ** ** ** ** ** * * * * * ** * *
** * ** ** ** ** ** * * * * * ** * *
** * ** ** ** ** ** * * * * * ** * *
** * ** ** ** ** ** * * * * * ** * *
** * ** ** ** ** ** * * * * * ** * *
** * ** ** ** ** ** * * * * * ** * *
** * ** ** ** ** ** * * * * * ** * *
* * ** ** ** ** ** * * * * * ** * * *
* ** ** ** ** ** * * * * * ** * * **
* ** ** ** ** ** * * * * * ** * * **
* ** ** ** ** ** * * * * * ** * * **
* ** ** ** ** ** * * * * * ** * * **
* ** ** ** ** ** * * * * * ** * * **
** ** ** ** ** * * * * * ** * * ** *
** ** ** ** ** * * * * * ** * * ** *
** ** ** ** ** * * * * * ** * * ** *
* ** ** ** ** * * * * * ** * * ** * *
** ** ** ** * * * * * ** * * ** * **
** ** ** ** * * * * * ** * * ** * **
** ** ** ** * * * * * ** * * ** * **
** ** ** ** * * * * * ** * * ** * **
** ** ** ** * * * * * ** * * ** * **
** ** ** ** * * * * * ** * * ** * **
** ** ** ** * * * * * ** * * ** * **
* ** ** ** * * * * * ** * * ** * ** *
** ** ** * * * * * ** * * ** * ** **
** ** ** * * * * * ** * * ** * ** **
** ** ** * * * * * ** * * ** * ** **
* ** ** * * * * * ** * * ** * ** ** *
** ** * * * * * ** * * ** * ** ** **
** ** * * * * * ** * * ** * ** ** **
More interesting behaviour occurs with rule 45, 00101101
** * *** * *** ** ** ** * * ** *** ** * * ******* * * * ** **
* **** **** * * ** * ** * * * *** * ** ** **** * ** *** * **
* *** * * ***** * * * ******** **** * ** * **** * * ***
*** *** * ** *** *** *** * * *** *** *** ** * * ** *
* * * **** ** **** * * ******* * ** *** * ** * * ****** ** **
* * *** * ** * * ** ** * * * **** ** ** * * * ***** ** ** *
**** * * * *** * * ** ****** **** * ** * * ** * *** *** * ** **
** ** ***** * * ****** ** ** ** * * ***** * * *** * **** **
* ** * ** **** * ** *** * * * **** * * * * * * * ** * ** *
* **** ** * * *** * * ** ***** **** *** *** ***** * * * * **
* *** * ** *** *** ** * * * * * * ** ** * * * *******
*** *** *** ** ** * **** * * * *** *** * * * ** * **** *****
* * * ** ** * ** *** ******* ** **** * * * **** ** ******
** * *** * * * * * ** *** * * * **** *** * * *** *
* **** * * * *** *** * * ** ****** * * * * * * ** *** * ** ***
*** ** ***** * * *** * ** ********** *** * * * ** * * ** *
** * ** * ** * ** * *** *** * ** ******** ** * *** *
** * **** **** *** **** ** ** * * ** ******* * * * ** * * *
** **** * ** ** ** ** ** ** * * ** ** * * ******* *** * * ***
** *** * * * * * * ** ** ** ** *** **** * ****** ** * *****
* * ** * ****** * * ***** ** ** ** * * **** **** * * *** *
** * ** * **** * ** ** ** * * ** * * * **** * ** *** *** *
** *** * *** * * ** * ** ** ***** ****** ** * ** * * * * * **
* * * *** ** *** *** **** ** * * ** ** ** * * **** * * * *** *
** *** * *** * ** ** ** ** *** ** * *** * ** ****** ******** *
* ** **** ** *** * * * * * * ** ** * **** ** * * ** **
** * * * ** * * * * *** *** * ** * * ** **** *** ****** * **
* * * ** ***** * ******* * * *** * * * * * * ** ** ****
* ***** ** *** * ** * ** * *** ***** * * * * * *** * *
** * ** **** * ****** *** **** ** ** * * ******** * * * ** ** *
* ** * * ** * * ** ** ** ** ** ** * ** * **** * * ** **
** *** ** * * * * **** *** * * * * ** ** ** **** ** ***** * * *** **
* ** ** ********** ** ** * * ***** ** ** ** ** ** ** *** * * **
*** * ** * * * **** * ** ** ** * * ** ** * ** ** * * *
** * *** ******** *** * *** * ** * ** ** ***** * **** * * * *
* *** * ** **** *** *** **** ** * * * *** * * * * * *
* *** ** * ***** * * * * ** ** ** *** *** *** ** ******* * *
**** * * **** ** * * ** *** * * * * * * ** ** * * ** * *
* ***** ** * ****** ** * * * *** *** * * * ***** ****** * *
*** *** ** * **** ** ** ***** * * * * * *** * ** *
** ** *** * **** *** * * ** * ** * ** ***** * **** * *** * *
Another interesting example is rule 90, applied to random starting conditions it tends to create inverted triangular structure.
*** ***** ***** ** * ** ****** * * * * * **** * * * *** ** *
* **** **** ***** **** * ** * ** ** * ** ** * ** * ** ***
* * ** ** ** ** **** * * **** * * *** ** ****** * ***** ** * **
** **** ****** *** ** *** ** *** * * ** * *** ** *** * ***** **
*** * * * * * * ***** * ** * *** * * ** * * *** ** *** * ** ** ****
* ** * * * * ** * * ** ***** * * ***** * * *** *** *
* ***** * ** * * * * * **** * **** * * * * * * * ** * * * *
* * * ** * * * * * ** * * * ** ** ** * * * * ** ** *
** * * * ***** ** * * ** ** **** ** ** ** ** ** ***** ***
*** * * ** * * ** ***** * *** *** ** *** *** * ** ** **
* ** * * * **** * * **** * *** * **** * ** * ** ** * * ******* ****
* *** * *** * ** * * * ** *** * * ** ****** ** * * *
* ** * * ** *** ****** ** ** ** * *** ** * **** ** ******* * * * *
** ** * *** * * * * ** ****** * * ** * * *** ** * * * * *
******* * * * * * ** * ** * *** * ** * ****** * ** * *
*** ** * * ** **** * *** * ** * **** * ** * *** * *
* ** * *** * * * ** * *** *** *** **** * ** *** * *** *** ** * **
* *** * * ** **** *** * * * * * * *** ***** * *** **** * *** * **
* *** ** * * *** * **** * *** **** * *** * * * * * *****
* * * ** * * *** * *** * * ** * * ** * *** * ** * * ***
**** * * *** *** ** * *** **** * * * *** * ** ** *
* ** ** * *** * * * ** * ** ** ** ** * ** *** ** * ** ****
* ********* * ** * **** * *** ********** * *** * * **** **** * *
* *** * ** * ** * * ** * * *** * * * * * * ** *
* * ** * * ***** * ***** ** **** * ** *** * * ** ** **** *
* *** * * * * ** * ** * ** * * *** * ** * * * *** *** * * *
** ** ** * * * * * ** *** * ** ****** * ** * ** *** * * * ** *
* ** ** ** ***** * ******* ** * **** * **** ** * *******
** *** **** ** * *** ** *** * *** * ** *** * ** *
* *** * **** ** **** * *** ** ****** ** * *** *** ******* *** * **** *
* * * ******** * * * *** ** * ** * * * * * * * * *** ** *
* * * *** *** * * * * *** * *** * * * *** ***** *
* * * * ** ** * * * * *** *** * * * * * * ** * * *** *
* * * *** *** * * ** * * * * * * ** * * * *** * ** * *
** * ** *** **** *** ** ** ** ** **** * * * * * ** * ** *
*** ** * * * * * * ********** *** ** *** * * * * ** **** ***** **
* ***** ** * * * ** ****** * * * * * ***** * * * **
* ** **** * * * *** ** * * * *** *** * * **
* * * **** ** ** * * * * ** * *** * ** ** * ** ** ** ** * ****
* * *********** * * * * **** * *** ** ** * *** ** ** ** * **
* * *** * ** * ** ** * * ***** **** * ** * ** ** **** *** *
Rule 90 with a single "on" cell gives raise to the familiar Sierpinsky arrowhead, increasing the length of the string and the number of time steps creates the arrowhead at any arbitrary resolution.
*
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Source code
The following C source code gives a simple shell of an program for creating 1 dimensional boolean cellular automata at just text resolution. Higher resolution bitmap displays can be created with changes to DisplayState().
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "sys/types.h"
#include "time.h"
/*
Simple Implementation of a 1 dimensional CA with 3 inputs and ring topology
*/
#define NITERATIONS 60
#define LENGTH 78
/*
The rule specify mappings from 000 -> ?, 001 -> ?, .... 111 -> ?
Where the xyz -> ? refers to the state of the
x - left neightbour, y - oneself, z - right neighbour
? to the state of oneself at the next time step
*/
/*int rules[8] = {0,1,0,1,0,0,0,0}; */ /* Rule 10 */
/*int rules[8] = {1,0,1,1,0,1,0,0}; */ /* Rule 45 */
int rules[8] = {0,1,0,1,1,0,1,0}; /* Rule 90 */
void DisplayState(int *,int);
int main(int argc,char **argv)
{
int i,j,k;
long secs;
int state[LENGTH],newstate[LENGTH];
/* Initialise the state */
time(&secs);
srand(secs);
for (i=0;i<LENGTH;i++)
state[i] = rand() % 2;
DisplayState(state,LENGTH);
for (i=0;i<NITERATIONS;i++) {
/* Erase the old state, not really necessary */
for (j=0;j<LENGTH;j++)
newstate[j] = 0;
/* Create the next state */
for (j=0;j<LENGTH;j++) {
k = 4*state[(j-1+LENGTH)%LENGTH] + 2*state[j] + state[(j+1)%LENGTH];
newstate[j] = rules[k];
}
/* Update the current state */
for (j=0;j<LENGTH;j++)
state[j] = newstate[j];
/* Display the results */
DisplayState(state,LENGTH);
}
}
/*
Display the state of the CA at the current time step
*/
void DisplayState(int *s,int len)
{
int i;
for (i=0;i<len;i++) {
if (s[i] == 1)
putchar('*');
else
putchar(' ');
}
printf("\n");
}
|