[Riches] – A New Kind of Science: The NKS Forum.
A new Kind of science is a book dedicated to understand how science has evolved in such aspects in systematic computational systems such as cellular automata.The discovery that simple programs can produce complex behaviors caused a dramatic paradigm shift by claiming that the universe and everything is being computed by a simple program.
Wolfram explains how the cellular automata works A cellular automaton is a model of a system of “cell” objects with the following characteristics.
- The cells live on a grid.
- Each cell has a state. The number of state possibilities is typically finite.
- Each cell has a neighborhood. This can be defined in any number of ways, but it is typically a list of adjacent cells.
A cellular automata works like is a row of cells that change colour according to set rules. If a cell is white, for example, and its immediate neighbours are white, then the cell remains white. Alternatively, if a white cell’s neighbours are both black, then it turns black.
Most of Wolfram’s analyses deal with the simplest possible cellular automata, specifically those that involve just a one-dimensional line of cells, two possible colors (black and white), and rules based only on the two immediately adjacent cells.
But the most relevant application that Wolfram’s has developed is the Rule 110 that shows how that sequence evolves.
The author first starts by proving that a “tag system” that removes 2 symbols at each step is universal by compiling a 2-state turing machine program. After that, he proves that a glider system can indeed implement a tag system. It is a step by step process. Then, he studies the space time of CA-110 to find the gliders and asociate them to the glider system correctly.
Two unusual features of the proof of Turing completeness are that, firstly, it looks highly unlikely that such a very simple rule could do everything, and secondly, is that the proof requires an infinitely long repeating background on which to work.
Describing how simple computational mechanisms can exist in nature at different levels, and that these simple and deterministic mechanisms can produce all of the complexity that we see and experience.
He makes the point that computation is essentially simple and ubiquitous. Since the repetitive application of simple computational transformations can cause very complex phenomena, as we see with the application of Rule 110, this, according to Wolfram, is the true source of complexity in the world.