A New Kind of Science (NKS) written by Stephen Wolfram after 10 years of isolated research makes the claim that much of contemporary science may be rephrased by considering the properties of certain types of computer program. In simple terms, the thesis of NKS rests on the observation that very simple computer programs of certain types can give rise to complex and interesting behaviour. This raises the tantalising possibility that complex behaviours and structures observed in the real world may be a consequence of very simple rules. In this context the Universe is seen as a computational device that processes these rules iteratively and hence generates the richness we, as observers, experience. The book's title is a reference to the search for these underlying rules and it is in the spirit of this search that the following article has been written.

The 'certain types' of computer program mentioned above are known as Cellular Automata and were originated by John Von Neumann in the nineteen-fifties (Poundstone). The definition of a cellular automaton at reads as follows.

(CA, plural "- automata") A regular spatial lattice of "cells", each of which can have any one of a finite number of states. The state of all cells in the lattice are updated simultaneously and the state of the entire lattice advances in discrete time steps. The state of each cell in the lattice is updated according to a local rule which may depend on the state of the cell and its neighbors at the previous time step. Each cell in a cellular automaton could be considered to be a finite state machine which takes its neighbours' states as input and outputs its own state.

The best known example is J.H. Conway's game of Life.

Conway's game of Life, devised in 1970, is played on an infinite two dimensional grid with a specific rule that leads to particularly interesting behaviour and properties. Wolfram considers the simpler one dimensional case with a generic rule set. Some of the rules in this set lead to interesting behaviours and others do not.

Essentially, a one dimensional cellular automaton consists of a state vector with each element containing either a one or a zero. At each time step a new value is computed, based on a specific rule, for each element in the vector. The rule requires as input the values of an element and it's immediate neighbours in the previous time period and outputs the value of the element in the next period. An exhaustive list of configurations of the relevant elements in this previous time period is {1,1,1}, {1,1,0}, {1,0,1}, {1,0,0}, {0,1,1}, {0,1,0}, {0,0,1}, {0,0,0} and we will label these 1 to 8 respectively.

For example, a particular rule requires that those elements with previous configurations {1,1,1} or {1,0,1} should assume the value one and all other elements should assume the value zero. This is represented in binary as 10100000 or in decimal as rule 160. Given there are eight configurations then 2⁸ rules exist numbered 0 to 255.

Given a starting vector and a rule it is a straightforward matter to compute the evolution of the system over a number of time periods. A MATLAB script to do such computations and produce graphical output of the results is here. The following is output from this script for rules 22 and 30 respectively and iterated for 32 time periods. In both cases the initial state vector consists of a single one placed in the centre of a string of zeros.

The process of deducing a rule based on two consecutive states given a complete pattern is also easy. Places are identified where each element of the rule has been applied and these are used to build up a complete description of the rule. If a complete pattern is not available then a rule consistent with the partial pattern may be deduced by solving a set of Boolean equations. The ability to represent logical conditions as linear inequalities presents the opportunity to model this process as an IP.

Given state vectors for two consecutive time periods the IP must identify a rule that is consistent with the transition between these states for every element. To this end, the following subscripts, coefficients and decision variables are defined.

Subscripts

i = 1..2 - two time periods
j = 1..c - number of elements in each time period
k = 1..8 - number of possible configurations of relevant elements

Coefficients

x_i,j - state of element j in time period i
n_j - decimal value of previous configuration for element j

Variables

v_k - binary representation of rule value

For each element we need to identify the configuration of ones and zeros in the relevant elements of the previous time period (i.e. period 1). This configuration value will be expressed in decimal form so that, for example, {1,0,1} will be expressed as the decimal number 5. In general

n_j = 4x_1,j-1 + 2x_1,j + x_1,j+1

For a given previous configuration value the state of this element in period 2 must be consistent with the rule generated by the IP solution. In other words, the value of the element computed by the rule must be consistent with the value observed. This may be written down more formally as

n_j = 8 - k → ν_k = x_2,j

This may be achieved using tools summarised in Chlond and Toase and involves a two step procedure. Firstly, a dummy variable is set to one if the condition holds, or more formally

n_j = 8 - k → δ_j,k = 1

This may be enforced using the linear constraints

n_j - k α_j,k ≤ 7 - k
n_j + (9 - k)β_j,k ≥ 9 - k
δ_j,k = α_j,k + β_j,k - 1

Secondly, if the dummy variable has the value one then enforce the condition

δ_j,k = 1 - → ν_k = x_2,j

which may be modeled as

ν ≥ δ_j,kx_2,j + δ_j,k - 1
ν ≤ δ_j,kx_2,j - δ_j,k + 1

Mosel code to implement the model is here.

The input data for the Mosel model was generated using rule 30 and indeed the solution to the IP is 30. In many cases the solution generated will not be unique. This is merely a reflection of the fact that more than one rule may effectively account for the transition between the two time periods. This is analagous to situations where several scientific theories account equally well for observed data. In such cases experiments need to be devised and performed and further data collected to tie break between the competing theories.

References

Chlond, M.J. and C.M. Toase (2003), "IP Modeling and the Logical Puzzles of Raymond Smullyan", INFORMS Transactions on Education, Vol. 3, No 3,

Poundstone, W. (1985),The Recursive Universe,OUP, ISBN 0-19-285173-X

Wolfram, S. (2002), A New Kind of Science, Wolfram Media Inc., ISBN 1-57955-008-8

To reference this paper, please use:  Chlond, M.J. (2004), "A New Kind of IP," INFORMS Transactions on Education, Vol. 4, No 2,  http://ite.pubs.informs.org/Vol4No2/Chlond/