Rule 110 cellular automaton
Encyclopedia
The Rule 110 cellular automaton (often simply Rule 110) is an elementary cellular automaton
with the following rule table:
In the table above, when the sequence of 1s and 0s corresponding to the new states is regarded as a binary number, the decimal equivalent is 110; hence the name of the rule.
published a proof of a 1985 conjecture by Stephen Wolfram
by proving that Rule 110 is Turing complete
, i.e., capable of universal computation. Cook presented his proof at the Santa Fe Institute conference CA98 before the publishing of Wolfram's book. This resulted in a legal affair based on a non-disclosure agreement with Wolfram Research. Wolfram Research blocked publication of Cook's proof for 2 years.
system.
, exhibits what Wolfram
calls "Class 4 behavior", which is neither completely stable nor completely chaotic. Localized structures appear and interact in various complicated-looking ways.
While working on the development of NKS
, Wolfram's research assistant Matthew Cook
proved Rule 110 capable of supporting universal computation. Rule 110 is a simple enough system to suggest that naturally occurring physical systems may also be capable of universality— meaning that many of their properties will be undecidable, and not amenable to closed-form mathematical solutions.
contained an exponential time overhead due to the encoding of the Turing machine's tape using a unary numeral system
. Neary and Woods (2006) modified the construction to use only a polynomial
overhead.
conference, held before the publication of NKS
. Wolfram Research claimed that this presentation violated Cook's nondisclosure agreement with his employer, and obtained a court order excluding Cook's paper from the published conference proceedings. The existence of Cook's proof nevertheless became known. Interest in his proof stemmed not so much from its result as from its methods, specifically from the technical details of its construction . The character of Cook's proof differs considerably from the discussion of Rule 110 in NKS. Cook has since written a paper setting out his complete proof.
Cook proved that Rule 110 was universal (or Turing complete) by showing it was possible to use the rule to emulate another computational model, the cyclic tag system
, which is known to be universal. He first isolated a number of spaceships
, self-perpetuating localized patterns, that could be constructed on an infinitely repeating pattern in a Rule 110 universe. He then devised a way for combinations of these structures to interact in a manner that could be exploited for computation.
Three localized patterns are of particular importance in the Rule 110 universal machine. They are shown in the image below, surrounded by the repeating background pattern. The leftmost structure shifts to the right two cells and repeats every three generations. It comprises the sequence 0001110111 surrounded by the background pattern given above, as well as two different evolutions of this sequence.
The center structure shifts left eight cells and repeats every thirty generations. It comprises the sequence 1001111 surrounded by the background pattern given above, as well as twenty-nine different evolutions of this sequence.
The rightmost structure remains stationary and repeats every six generations. It comprises the sequence 111 surrounded by the background pattern given above, as well as five different evolutions of this sequence.
Below is an image showing the first two structures passing through each other without interacting (left), and interacting to form the third structure (right).
There are numerous other spaceships in Rule 110, but they do not feature as prominently in the universality proof.
The initial spacing between these components is of utmost importance. In order for the cellular automaton to implement the cyclic tag system, the automaton's initial conditions must be carefully selected so that the various localized structures contained therein interact in a highly ordered way.
The data string in the cyclic tag system is represented by a series of stationary repeating structures of the type shown above. Varying amounts of horizontal space between these structures serve to differentiate 1 symbols from 0 symbols. These symbols represent the word on which the cyclic tag system is operating, and the first such symbol is destroyed upon consideration of every production rule. When this leading symbol is a 1, new symbols are added to the end of the string; when it is 0, no new symbols are added. The mechanism for achieving this is described below.
Entering from the right are a series of left-moving structures of the type shown above, separated by varying amounts of horizontal space. Large numbers of these structures are combined with different spacings to represent 0s and 1s in the cyclic tag system's production rules. Because the tag system's production rules are known at the time of creation of the program, and infinitely repeating, the patterns of 0s and 1s at the initial condition can be represented by an infinitely repeating string. Each production rule is separated from the next by another structure known as a rule separator (or block separator), which moves towards the left at the same rate as the encoding of the production rules.
When a left-moving rule separator encounters a stationary symbol in the cyclic tag system's data string, it causes the first symbol it encounters to be destroyed. However, its subsequent behavior varies depending on whether the symbol encoded by the string had been a 0 or a 1. If a 0, the rule separator changes into a new structure which blocks the incoming production rule. This new structure is destroyed when it encounters the next rule separator.
If, on the other hand, the symbol in the string was a 1, the rule separator changes into a new structure which admits the incoming production rule. Although the new structure is again destroyed when it encounters the next rule separator, it first allows a series of structures to pass through towards the left. These structures are then made to append themselves to the end of the cyclic tag system's data string. This final transformation is accomplished by means of a series of infinitely repeating, right-moving clock pulses, in the right-moving pattern shown above. The clock pulses transform incoming left-moving 1 symbols from a production rule into stationary 1 symbols of the data string, and incoming 0 symbols from a production rule into stationary 0 symbols of the data string.
The reconstructions was using a regular language to Rule 110 over an evolution space of 56,240 cells to 57,400 generations. Writing the sequence 1110111 on the tape of cyclic tag system and a leader component at the end with two solitons.
Elementary cellular automaton
In mathematics and computability theory, an elementary cellular automaton is a one-dimensional cellular automaton where there are two possible states and the rule to determine the state of a cell in the next generation depends only on the current state of the cell and its two immediate neighbors....
with the following rule table:
| current pattern | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| new state for center cell | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
In the table above, when the sequence of 1s and 0s corresponding to the new states is regarded as a binary number, the decimal equivalent is 110; hence the name of the rule.
History
Around 2000, Matthew CookMatthew Cook
Matthew Cook is a mathematician and computer scientist who proved Stephen Wolfram's conjecture that the Rule 110 cellular automaton is Turing-complete. Rule 110 is arguably the simplest Turing-complete system currently known....
published a proof of a 1985 conjecture by Stephen Wolfram
Stephen Wolfram
Stephen Wolfram is a British scientist and the chief designer of the Mathematica software application and the Wolfram Alpha computational knowledge engine.- Biography :...
by proving that Rule 110 is Turing complete
Turing completeness
In computability theory, a system of data-manipulation rules is said to be Turing complete or computationally universal if and only if it can be used to simulate any single-taped Turing machine and thus in principle any computer. A classic example is the lambda calculus...
, i.e., capable of universal computation. Cook presented his proof at the Santa Fe Institute conference CA98 before the publishing of Wolfram's book. This resulted in a legal affair based on a non-disclosure agreement with Wolfram Research. Wolfram Research blocked publication of Cook's proof for 2 years.
Interesting properties
Among the 88 possible unique elementary cellular automata, Rule 110 is the only one for which this has been proven, although proofs for several similar rules should follow as simple corollaries, for instance Rule 124, where the only directional (asymmetrical) transformation is reversed. Rule 110 is arguably the simplest known Turing completeTuring completeness
In computability theory, a system of data-manipulation rules is said to be Turing complete or computationally universal if and only if it can be used to simulate any single-taped Turing machine and thus in principle any computer. A classic example is the lambda calculus...
system.
Class 4 behavior
Rule 110, like the Game of LifeConway's Game of Life
The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....
, exhibits what Wolfram
Stephen Wolfram
Stephen Wolfram is a British scientist and the chief designer of the Mathematica software application and the Wolfram Alpha computational knowledge engine.- Biography :...
calls "Class 4 behavior", which is neither completely stable nor completely chaotic. Localized structures appear and interact in various complicated-looking ways.
While working on the development of NKS
A New Kind of Science
A New Kind of Science is a book by Stephen Wolfram, published in 2002. It contains an empirical and systematic study of computational systems such as cellular automata...
, Wolfram's research assistant Matthew Cook
Matthew Cook
Matthew Cook is a mathematician and computer scientist who proved Stephen Wolfram's conjecture that the Rule 110 cellular automaton is Turing-complete. Rule 110 is arguably the simplest Turing-complete system currently known....
proved Rule 110 capable of supporting universal computation. Rule 110 is a simple enough system to suggest that naturally occurring physical systems may also be capable of universality— meaning that many of their properties will be undecidable, and not amenable to closed-form mathematical solutions.
Turing machine simulation overhead
The original emulation of a Turing machineTuring machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
contained an exponential time overhead due to the encoding of the Turing machine's tape using a unary numeral system
Unary numeral system
The unary numeral system is the bijective base-1 numeral system. It is the simplest numeral system to represent natural numbers: in order to represent a number N, an arbitrarily chosen symbol representing 1 is repeated N times. For example, using the symbol | , the number 6 is represented as ||||||...
. Neary and Woods (2006) modified the construction to use only a polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
overhead.
The proof of universality
Matthew Cook presented his proof of the universality of Rule 110 at a Santa Fe InstituteSanta Fe Institute
The Santa Fe Institute is an independent, nonprofit theoretical research institute located in Santa Fe and dedicated to the multidisciplinary study of the fundamental principles of complex adaptive systems, including physical, computational, biological, and social systems.The Institute houses a...
conference, held before the publication of NKS
A New Kind of Science
A New Kind of Science is a book by Stephen Wolfram, published in 2002. It contains an empirical and systematic study of computational systems such as cellular automata...
. Wolfram Research claimed that this presentation violated Cook's nondisclosure agreement with his employer, and obtained a court order excluding Cook's paper from the published conference proceedings. The existence of Cook's proof nevertheless became known. Interest in his proof stemmed not so much from its result as from its methods, specifically from the technical details of its construction . The character of Cook's proof differs considerably from the discussion of Rule 110 in NKS. Cook has since written a paper setting out his complete proof.
Cook proved that Rule 110 was universal (or Turing complete) by showing it was possible to use the rule to emulate another computational model, the cyclic tag system
Tag system
A tag system is a deterministic computational model published by Emil Leon Post in 1943 as a simple form of Post canonical system. A tag system may also be viewed as an abstract machine, called a Post tag machine —briefly, a finite state machine whose only tape is a FIFO queue of unbounded length,...
, which is known to be universal. He first isolated a number of spaceships
Spaceship (CA)
In a cellular automaton, a finite pattern is called a spaceship if it reappears after a certain number of generations in the same orientation but in a different position...
, self-perpetuating localized patterns, that could be constructed on an infinitely repeating pattern in a Rule 110 universe. He then devised a way for combinations of these structures to interact in a manner that could be exploited for computation.
Spaceships in Rule 110
The function of the universal machine in Rule 110 requires an infinite number of localized patterns to be embedded within an infinitely repeating background pattern. The background pattern is fourteen cells wide and repeats itself exactly every seven iterations. The pattern is 00010011011111.Three localized patterns are of particular importance in the Rule 110 universal machine. They are shown in the image below, surrounded by the repeating background pattern. The leftmost structure shifts to the right two cells and repeats every three generations. It comprises the sequence 0001110111 surrounded by the background pattern given above, as well as two different evolutions of this sequence.
The center structure shifts left eight cells and repeats every thirty generations. It comprises the sequence 1001111 surrounded by the background pattern given above, as well as twenty-nine different evolutions of this sequence.
The rightmost structure remains stationary and repeats every six generations. It comprises the sequence 111 surrounded by the background pattern given above, as well as five different evolutions of this sequence.
Below is an image showing the first two structures passing through each other without interacting (left), and interacting to form the third structure (right).
There are numerous other spaceships in Rule 110, but they do not feature as prominently in the universality proof.
Constructing the cyclic tag system
The cyclic tag system machinery has three main components:- A data string which is stationary;
- An infinitely repeating series of finite production rules which start on the right and move leftward;
- An infinitely repeating series of clock pulses which start on the left and move rightward.
The initial spacing between these components is of utmost importance. In order for the cellular automaton to implement the cyclic tag system, the automaton's initial conditions must be carefully selected so that the various localized structures contained therein interact in a highly ordered way.
The data string in the cyclic tag system is represented by a series of stationary repeating structures of the type shown above. Varying amounts of horizontal space between these structures serve to differentiate 1 symbols from 0 symbols. These symbols represent the word on which the cyclic tag system is operating, and the first such symbol is destroyed upon consideration of every production rule. When this leading symbol is a 1, new symbols are added to the end of the string; when it is 0, no new symbols are added. The mechanism for achieving this is described below.
Entering from the right are a series of left-moving structures of the type shown above, separated by varying amounts of horizontal space. Large numbers of these structures are combined with different spacings to represent 0s and 1s in the cyclic tag system's production rules. Because the tag system's production rules are known at the time of creation of the program, and infinitely repeating, the patterns of 0s and 1s at the initial condition can be represented by an infinitely repeating string. Each production rule is separated from the next by another structure known as a rule separator (or block separator), which moves towards the left at the same rate as the encoding of the production rules.
When a left-moving rule separator encounters a stationary symbol in the cyclic tag system's data string, it causes the first symbol it encounters to be destroyed. However, its subsequent behavior varies depending on whether the symbol encoded by the string had been a 0 or a 1. If a 0, the rule separator changes into a new structure which blocks the incoming production rule. This new structure is destroyed when it encounters the next rule separator.
If, on the other hand, the symbol in the string was a 1, the rule separator changes into a new structure which admits the incoming production rule. Although the new structure is again destroyed when it encounters the next rule separator, it first allows a series of structures to pass through towards the left. These structures are then made to append themselves to the end of the cyclic tag system's data string. This final transformation is accomplished by means of a series of infinitely repeating, right-moving clock pulses, in the right-moving pattern shown above. The clock pulses transform incoming left-moving 1 symbols from a production rule into stationary 1 symbols of the data string, and incoming 0 symbols from a production rule into stationary 0 symbols of the data string.
Cyclic tag system working
The reconstructions was using a regular language to Rule 110 over an evolution space of 56,240 cells to 57,400 generations. Writing the sequence 1110111 on the tape of cyclic tag system and a leader component at the end with two solitons.
External links
- For a nontechnical discussion of Rule 110 and its universality, see: A New Kind of Science p.690
- Wolfram Science – Rule 110