This post originally appeared on Medium, and we republished with permission from Xiaohui Liu.
We have implemented Rule 110 on Bitcoin. Similar to two-dimensional cellular automata (CA) Conway’s Game of Life, Rule 110, a one-dimensional CA, is also Turing-complete. By deduction, we have shown Bitcoin is Turing Complete, once again.
Rule 110
The Rule 110 cellular automaton is a 1-dimensional elementary CA, where a linear pattern of 0s and 1s evolves according to a simple set of rules. Whether a point in the pattern will be 0 or 1 in the new generation depends on its current value and on those of its two neighbors. The Rule 110 has the following set of rules:
The name “Rule 110” is based on the fact that this rule can be summarized in the binary sequence 01101110, corresponding to the decimal value 110.
Turing-Complete
Despite its simplicity, Rule 110 is Turing-complete, as proven in Universality in Elementary Cellular Automata (Cook 2004). This implies that, in principle, it can simulate any calculation or computer program. Rule 110 is arguably the simplest known Turing-complete system.
Implementation
We have implemented Rule 110, in a similar approach to implementing Game of Life.
New to blockchain? Check out CoinGeek’s Blockchain for Beginners section, the ultimate resource guide to learn more about blockchain technology.
