A cellular automaton is a computational system with two components: an ordered array of cells, such as on a Go board, and a set of rules that determines the state of each cell at any time, depending on its relation to other cells in its immediate locality.

A cell in such a system is generally represented by a square in the grid. The simplest state of such a cell is that it is either occupied (e.g. black) or unoccupied (e.g. white), on or off. An example of a simple rule is that a cell can be switched on if it is adjacent to a cell that it is already switched on. From such simple systems highly complex patterns can arise.

In his memoir, Adventures of a Mathematician (1991), Stanisław Ulam recalled how, in his student days in the late 1920s, his friend Stanisław Mazur proposed the first examples of infinite mathematical games and suggested the possibility of self-replicating automata. They didn’t record their abstract ideas, but some of their thoughts, he wrote, “were actually precursors of theories like that of [John] von Neumann on abstract automata.”

Actual realization of cellular automata started with von Neumann, a mathematician and computer scientist, in the late 1940s. His aim was to produce computer systems that were capable of replicating themselves, analogous to the way that biological cells do. He presented his ideas in a lecture given at the Hixon Symposium in Pasadena on 20 September 1948, later published under the title “The general and logical theory of automata”. He pointed out that “[the role of automata] in mathematics presents an interesting counterpart to certain functional aspects of organization in nature [although] natural organisms are, as a rule, much more complicated and subtle, and therefore much less well understood in detail, than are artificial automata.”

He discussed in detail the functioning of neurons and how neuronal activity could be modelled by a computerized automaton, nevertheless noting a major limitation, namely that the estimated number of neurons in the central nervous system was about 10¹⁰, all artificial automata at that time having no more than 10⁸ parts. “We have absolutely no past experience with systems of this degree of complexity.”

Von Neumann did not himself use the term “cellular automaton”. The earliest recorded instance of the phrase dates from 1965 in a paper in the Journal of Theoretical Biology by Walter R Stahl, “Algorithmically unsolvable problems for a cell automaton”, in which he discussed the biology of mammalian cells, particularly cancer cells, although we now recognize that his assertion that “the mammalian genome probably contains 100,000 to 1,000,000 genes encoded in billions of nucleotides” was a large overestimate. “It is impossible to prove,” he wrote, “ that the simplified axiomatic cell model is an adequate representation of any real cell, but it allows the introduction of certain concepts of automata theory into molecular biology in a new and provocative manner.”

In 1970 the mathematician John Conway described a cellular automaton that he called “The Game of Life”, a two dimensional system that starts with a few counters placed on an infinite grid and generates a large range of sequences of different shapes via three simple rules, relating to births, survivals, and deaths. This is probably still the best-known cellular automaton, and it has been shown to be a universal computer, comparable to a Turing machine. Martin Gardner described it in his Mathematical Games column in Scientific American in October 1970, as did Conway, with his colleagues Berlekamp and Guy, in the second volume of Winning Ways for Your Mathematical Plays (Academic Press, 1982), their classical work on combinatorial game theory, now in its second edition in four volumes.

Since then, with increased computing power, cellular automata have become important parts of artificial intelligence systems, with applications that include modelling the development of biological organisms, simulation of neuronal activity, studying homoeostatic mechanisms, cognition, cell proliferation, and tumour genetics, and many others. 

I have included an example of a cellular automaton in this week’s Interesting integer section below: the Ulam–Warburton cellular automaton, first published in 1962 and named after Stanisław Ulam and a Scottish engineer, Mike Warburton. Next week I shall demonstrate some other simple cellular automata.

Jeffrey Aronson is a clinical pharmacologist, working in the Centre for Evidence Based Medicine in Oxford’s Nuffield Department of Primary Care Health Sciences. He is also president emeritus of the British Pharmacological Society.

Competing interests: none declared.