Cellular Automata and Reversible Computing

Cellular automata represent a concept which has been discovered under various names and used with different purposes in a multitude of fields. Among such fields one could include pure mathematics, where they are related to topological dynamics, or electrical engineering, where they are also called iterative arrays. Despite a wide applicability, cellular automata are a relatively new topic, since they do not appear to have been formally considered before the second half of the 20th century. After the ascension of electronic computers, many different systems, analogous to different extents to the cellular automata model, have been independently introduced.

"A cellular automata machine is a universe synthesizer. [..] Its color screen is a window through which one can watch the universe that is being <played> ." - Tommaso Toffoli, Norman Margolus

This website explores various fields of Cellular Automata theory and Reversible Computing. The emphasis, however, is put on the former, due to the many existing variations of Cellular Automata, each with interesting rules, developments and outcomes.

We have covered the famous 'Game of Life' in detail, talking about how it appeared, what its rules are and how they were conceived, while presenting its inhabitants and discussing its features. We have related the two concepts of our topic, showing ways in which one could create Cellular Automata with invertible behaviour, and we found applications closely related to the field of computer theory - Turing Machines and other patterns capable of processing data.

After browsing through the website, feel free to experiment with patterns in our Game of Life applet or to test your newly-acquired knowledge by doing the Quiz. For a more powerful tool, look in the references for a link to Golly, an advanced Life simulator.

What's the point?

This blunt question might very well be the first one that crosses the mind of someone just introduced to the field of Game of Life and other cellular automata. Are they, in the end, only a “game”? Is this a topic of real scientific interest or a niche for those who enjoy exploring a world of fascinating patterns and behaviours, but with nothing else to gain?

One man, mentioned before, certainly has a strong opinion on the subject. Stephen Wolfram, author of the monumental study “A new kind of science”, believes that cellular automata are proof of a fundamental principle of nature, which states that “very simple programs produce great complexity”. This might be an easy to understand, but hard to accept answer to many questions still open in science today, such as how the intricate phenomena we find in nature have come to exist, seemingly out of nothing.

The main purpose of this website is to show how these ideas apply in the field of computing. Although the “computers” described here are cumbersome and ineffective, some of the mechanisms involved in their construction and operation could very well be extremely relevant in the future.

For example, the Spartan Computer Constructor can be created by glider synthesis – the process of forming a pattern only using the collisions of salvos of gliders. Perhaps, in a similar manner, it will be possible to combine elements much smaller and much less complex than the ones used in industry today to create huge processing power, by harnessing their inherent tendency to form intricate patterns.

As the ubiquitous transistor based technology might be reaching its physical limitations, such ideas can be closer than we think.