Turing-Complete Rule 110 on Bitcoin

Turing-Complete Rule 110 on Bitcoin

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

250 iterations of rule 110
250 iterations of 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:

Rule 110
Rule 110

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.

An animation of Rule 110
An animation of Rule 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.

Rule 110
Rule 110

New to Bitcoin? Check out CoinGeek’s Bitcoin for Beginners section, the ultimate resource guide to learn more about Bitcoin—as originally envisioned by Satoshi Nakamoto—and blockchain.

[id^="_form"]
[id^="_form"]
[id$="_submit"]
[id$="_submit"]
[^;]
[^;]
[?&]
[?&]
[^&#]
[^&#]
[(d+)]
[(d+)]
[elem.name]
[elem.name]
[+_a-z0-9-'&=]
[+_a-z0-9-'&=]
[+_a-z0-9-']
[+_a-z0-9-']
[a-z0-9-]
[a-z0-9-]
[a-z]
[a-z]
[el.name]
[el.name]
[id^="_form"]
[id^="_form"]
[id$="_submit"]
[id$="_submit"]
[^;]
[^;]
[?&]
[?&]
[^&#]
[^&#]
[(d+)]
[(d+)]
[elem.name]
[elem.name]
[+_a-z0-9-'&=]
[+_a-z0-9-'&=]
[+_a-z0-9-']
[+_a-z0-9-']
[a-z0-9-]
[a-z0-9-]
[a-z]
[a-z]
[el.name]
[el.name]