Introduction

A complete definition of cellular automaton can be found on Wikipedia. These are simple computing devices, taking a lot of different shapes and guises, but with a common underlying principle:

  1. cells are arranged with a particular topology defining, for each single cell, its neibourghood as a set of other cells ;
  2. a single cell can have states ;
  3. cells change state in discrete steps (transitions) according to their current state and the state of their neighbours, following some fixed rules

One very well-known example of cellular automata is John Conway's Game of Life. What makes cellular automata fascinating is that, although extremely simple to define and to implement (hence this piece of software), they can exhibit extremely complex behavior with all sort reularities and even what appears to be true randomness.

They have been extensively studied, among others, by Stephen Wolfram who have made extensive use of them as evidence in its "demonstration" (quotes being justified by the lack of mathematical proof) of its Principle of Computational Equivalence and of the developments in its masterpiece book, A New Kind of Science (NKS for short).

Pictures of various kinds of cellular automata, among lots of computing systems, are ubiquitous in NKS and when I read it first, I was at once fascinated by the particular beauty of these images.

Implementation

This piece of a software is a straightforward (read dead simple) implementation of one-dimensional two-state automata for generation of two dimensional images. An automaton is a (finite) ring of cells (ie. each and every cell has two neighbours), each cell having two states. At each computation step, the states of all the cells are computed simultaneously using transition rules according to the state of a cell and its two neighbours. By arranging the ring of cells as a row in a rectangular 2D picture, and by considering that the height is formed by appending each generation of the automata one to another, one gets an image such as the following: Automaton with rule 110 and single black starting cell

This particular image is generated by the present package. It is a B&W rendition of the evolution of an automaton with a single black starting cell following rule 110, each cell being mapped to a single pixel. This particular rule is Turing complete which means that is has the computational power of a Turing machine (see Wikipedia again for an introduction): this may not be obvious but it can do whatever a general purpose language like Java can do.

An artefact of this particular implementation is that, being organized in a ring, cells at the far right and at the far left of the picture are neighbours, which generates cycles on the images when something passes from one side to the other.

As an alternative, one can generate 8bit and 24bit colored images from the same automata. Each bit is mapped to a single cell automaton cell.

Rule 110 automata as 8bit image Rule110 automata as 24bit image

I personnally prefer the simple, B&W images.

Numbering

Automata are numbered according to a simple scheme. There can be eight possible arrangements for the states of the three contiguous cells that affect the output state of a cell. Each rule must give the resulting state of each these 8 combinations, this state having 2 possible values. Hence there are `2^8=256` possible different rules, so each one can be numbered unambiguously.

The number of a rule is then the 8 bits binary number obtained by considering a black output state as 1 and a white as 0. The bit number of a particular pattern is obtained by, once again, using binary numbers formed from the three bits a pattern is made of.

For example, 110 corresponds to the binary number (MSB) 01101110. This gives the following eightrules (1 means black and 0 means white):

Pattern Output
111 0
110 1
101 1
100 0
011 1
010 1
001 1
000 1
© 2006-2007