Turing Test with Bitcoin

How to create artificial life inside Bitcoin

Since 2015 there has been an ongoing debate on Bitcoin’s capabilities to do complex computation and whether or not Bitcoin is “Turing-complete.” Unfortunately there has been a pervasive lie spread about Bitcoin that it is not Turing-complete, and that it is not capable of complex computation like the Ethereum blockchain is. In this piece we will examine the history of the claim of Bitcoin’s Turing-completeness, and then we will create artificial life that lives inside of Bitcoin forever.

The history of Turing-completeness in Bitcoin

The Bitcoin world was first introduced to Dr. Craig S. Wright in 2015 when he was introduced on a panel as “a former academic” who does “research commercially that no one ever hears about.” Introducing himself as someone who mined Bitcoin “a long time ago,” it was a very mysterious entrance for a then-unknown in the space. Alongside himself was a star-studded panel consisting of Ed Moy, former Director of the United States Mint; Joseph Vaughn Perling, the founder of the New Liberty Dollar project; Trace Meyer, an early Bitcoin investor; and Nick Szabo, the creator of Bit gold.

The panel is a must-watch for anyone interested in peeking back through the history of Bitcoin’s evolution. Early on in the panel, Dr. Wright makes a surprising claim about Bitcoin that befuddles the panel experts. He makes a claim that Bitcoin and Bitcoin Script, the programming language that was built by Satoshi Nakamoto, is capable of complex computation and is Turing-complete.

Turing-completeness of a computational system is defined to mean that the system is capable of solving any computation problem. In more simplistic terms in computer science, a system is said to be Turing-complete if it can “loop.” Since it is not immediately obvious that Bitcoin Script is capable of looping, it was widely accepted that Bitcoin was not a Turing-complete system. To understand the boldness of Dr. Wright’s claim at the time, we have to peer back through the modern history of “blockchain” and “cryptocurrency.”

In 2013, Vitalik Buterin introduced Ethereum to the world with a white paper titled “Ethereum: A Next Generation Smart Contract & Decentralized Application Platform”. Buterin cites the need for Ethereum because the “scripting language as implemented in Bitcoin has several important limitations,” the first of which is a “lack of Turing-completeness.” Shortly thereafter in the paper Ethereum is introduced as “a blockchain with a built-in Turing-complete programming language, allowing anyone to write smart contracts and decentralized applications.”

By the time of the aforementioned panel in 2015, Bitcoin was seen as a blockchain with many limitations and Ethereum was seen as a blockchain that could be used for complex smart contracts. The idea that Bitcoin was limited has produced this even more nonsensical idea of “second-generation” and “third-generation” blockchains with the implication that Bitcoin, while a good starting point, was just the first step in creating a global blockchain that could handle all sorts of transactions.

As an immediate response to Dr. Wright’s claim on the panel, Nick Szabo, clearly confused by what Craig is saying, responds that what Wright is saying is “an esoteric thing” and if Bitcoin “is not Turing-complete, then it’s not a general purpose language like Ethereum regardless of that partial loop type of thing.” Watch the video below.

The panel moves on from this claim, and we don’t hear about Bitcoin’s ability to do complex computation for another couple of years. It just so happens that we hear it, again, from Dr. Wright himself.

By July of 2017, Bitcoin was approaching a large schism. Those who correctly saw Bitcoin’s artificial scaling limitations for what they were gathered in Arnhem at “The Future of Bitcoin” conference to discuss the path forward for Bitcoin. Dr. Wright was not scheduled to speak at this conference, but luckily for us, Jon Matonis, the former director of the Bitcoin Foundation, forfeited his speaking time and chose to introduce the man that he recognized as Satoshi Nakamoto to speak in his stead. In what was essentially his first public appearance since being doxed as the creator of Bitcoin, Wright gave a fiery speech about where he saw Bitcoin going in the decades ahead.

Twenty-six minutes into the speech, a slide pops up titled “Turing completeness”. He sighs and says, “I’ve had a lot of shit about this one. Guess what? You’re all wrong – it is [Turing-complete]”.

TuringCompleteness

Bitcoin is a decider

As he is discussing how Bitcoin’s scripting system forms the basis for a special class of Turing Machines called a “decider,” he flips to a slide that shows an interesting pattern that mathematicians would immediately recognize as the Wolfram 110 cellular automaton:

Bitcoin is a decider2

Cellular automata, discovered by Stanislaw Ulam and John Von Nuemann, are an intriguing area of study most widely associated with the mathematician Stephen Wolfram who engaged in a systematic study of one-dimensional cellular automata. I encourage you to read about this fascinating area of study, but a simple way of thinking about cellular automata are that given an initial state and a simplistic ruleset, cellular automata can evolve to create complex systems. In the 1970s, cellular automata were popularized when Conway’s Game of Life, a two-dimensional cellular automata, attracted interest from the world outside of academia. We will return to Conway’s Game of Life, but it is important to note that Wolfram picked up the study of cellular automata in the 1980s and discovered complex behavior in these one-dimensional cellular automata, or elementary cellular automata.

Rule 110, discovered by Wolfram, is an elementary cellular automaton that shows interesting behavior that observers would be hard pressed to define as either stability or chaos. Rule 110 is known to be Turing-complete, implying that any calculation or computer program can be simulated using this automaton.

Dr. Wright refers to Rule 110 as “the simplest Turing-complete system” and makes a shocking revelation in his speech at Arnhem. “This was running in Bitcoin… We had PSO’s (Particle Search Optimizations) in Bitcoin running.” He laments the fact that at the time Bitcoin’s high fees had killed the research projects. “We had the first self-evolving code in Bitcoin that ran for two years,” he continues, before again referencing the high fees on the legacy BTC chain killing the project.

This should have been bigger news—this was proof that Turing-complete computation was possible inside of Bitcoin. Yet, for some reason, the so-called blockchain industry ignored the claim and in the cryptocurrency craze of 2017 it was repeated in mass media markets that Ethereum was a “programmable version” of Bitcoin.

In March of 2018, Clemens Ley is the first to publicly back Dr. Wright’s claim and gives a presentation titled “Why Bitcoin is Turing Complete” at the Satoshi’s Vision conference in Tokyo. Clemens, a student of Automata Theory, came up with an independent proof of the thesis and presented on the proof here. He begins the presentation by stating that “many things that people think are impossible in Bitcoin can actually be done.” He then spends the presentation giving a practical application of using the blockchain as the tape needed to do Turing-complete computation. His presentation, at the time of this writing only holding 3,479 views, is worth careful study by anyone skeptical of the claims that Bitcoin is capable of Turing-complete computation. It is again in 2017 that Dr. Wright’s claims are validated by another independent researcher Konstantinos Sgantzos who publishes the paperImplementing a Church-Turing-Deutsch Principle Machine on a Blockchain”.

While I’ve mused publicly on the irony that the creator of Bitcoin has been seen as a heretic while trying to educate the world on his creation, I accept that Dr. Wright is seen as controversial in the space that he gave birth to. Despite being personally thankful for the countless hours he has spent in public forums teaching myself and others about the nature of Bitcoin, there are few that have been willing to test his claims. While we can sit around and wait for more academics to validate Wright’s claims, there are also those who are willing to test them.

The Game of Life

I had the pleasure of meeting Xiaohui Liu in 2019 at a Bitcoin SV meetup in San Francisco. We exchanged pleasantries and spoke briefly on how we hoped Bitcoin would provide a solution to multiple problems inherent to Silicon Valley companies.

When I got home, Xiaohui had sent me a message with a link to his project sCrypt and said he had built a full functioning Bitcoin Script compiler in C++ as if it was no big deal. Xiaohui is one of my favorite innovators in the Bitcoin space, and he has continually used the familiar language of C++ to show other programmers what is possible inside of Bitcoin Script.

An easy way to validate Wright’s claim would be to use Bitcoin Script to replicate a Turing-complete system such as the aforementioned Rule 110 or Conway’s Game of Life. Xiahoui made this easy for us by releasing boilerplate code for Conway’s Game of Life in C++. The Game of Life is a cellular automaton that is played on a 2-dimensional grid.

The Game of Life is relatively simple and consists of four rules. The first three rules apply to cells that are populated (yellow), and the last rule applies to cells that are unpopulated (grey):

  1. Each populated cell with one or no neighbors dies, as if by solitude.

    Game of Life

  2. Each populated cell with four or more neighbors dies, as if by overpopulation.

    Game of Life

  3. Each populated cell with two or three neighbors survives.

    Game of Life

  4. Each unpopulated cell with three neighbors becomes populated.

    Game of Life

You can play with the Game of Life using this applet. The Game of Life is intriguing to academics and casual observers alike, because an initial configuration with this simple ruleset can create complex patterns and “lifeforms.” “Blocks,” “beehives,” “canoes,” and more are forms of still life that are found in the Game of Life. We even see dynamic “lifeforms” emerge such as a “glider gun.” It is a whacky world inside this cellular automaton, and the more you look into it the more weird it gets.

By creating an initial configuration on the blockchain we can observe how it evolves. Since Conway’s Game of Life is Turing-complete, if we can replicate it on the Bitcoin blockchain, then we can have demonstrable proof that Bitcoin is for all intents and purposes Turing-complete. If you’re wondering why this hasn’t already been done in Bitcoin’s history, a quick look at the code in Bitcoin Script would make it apparent why. The script is quite large, and would not be possible on the BTC chain. Because Bitcoin SV is the only blockchain that implements Satoshi’s original design, this is only possible on Bitcoin SV.

We have decided to put this to the test. Can we get Conway’s Game of Life to live on the blockchain?

Yes we can! Here we have published the initial configuration of Conway’s Game of Life on a 4×4 board. We start with 3 populated cells:

3 populated cells - game of life transaction

An observer of the script in the transaction linked above would see that we have a game board that looks something like this:

00000000
00000100
00010100
00000000

You can look at the scripthash of the script to see the second iteration on the game. Per the Game of Life rules, we will end up with a form of “still life” called a block in this transaction:

Game of life transaction

Or

00000000
00010100
00010100
00000000

Iterating on the game 5 more times keeps this form of stable still life seen in the Game of Life. We have created immortal life on the blockchain! The only thing stopping us from creating more complex systems is the economic forces involved. That Satoshi Nakamoto was one smart guy adding economics into this system! Our game lives so long as it can be funded.

We can see that it is possible to have a Turing-complete system running inside of Bitcoin, proving that Bitcoin itself is Turing-complete. With a little more work, we can create an interactive living game board that players can interact with and fund to keep life alive.

Why does any of this matter? Well, for one, it completely silences anyone who seeks to downplay Bitcoin’s ability to do complex computation. In BTC, they have deliberately removed Bitcoin’s computing capabilities by removing necessary opcodes, restricting the size of transactions and scripts, and capping the blocksize. Because BTC proponents falsely claim their blockchain as Bitcoin, it is widely seen as true that Bitcoin can’t do complex computation. Unsurprisingly to many in the Bitcoin SV ecosystem, this also vindicates Dr. Craig Wright.

Dr. Wright, the undeniable creator of Bitcoin, has repeatedly made incredulous claims about Bitcoin’s nature that have proven to be true. Whether it is the small-world nature of the bitcoin network topology, the economic incentives that secure the network, or the Turing-completeness of the system itself, Dr. Wright has repeatedly shown to be an expert of his own technology.

While Ethereum is unable to scale in any meaningful way, Bitcoin SV is rapidly scaling on the path to Terabyte sized blocks and beyond. Bitcoin is capable of everything Ethereum is capable of, but it has the massive scalability that Satoshi Nakamoto envisioned for the system baked into it.

The vindication of Craig Wright on the Turing-completeness of Bitcoin comes as no surprise to us at Britevue. In building the future of online reviews on top of Bitcoin, we are building complex systems that require Bitcoin to be able to do smart contracting and tokenization—things previously thought impossible in Bitcoin.

In order for artificial intelligence (AI) to work right within the law and thrive in the face of growing challenges, it needs to integrate an enterprise blockchain system that ensures data input quality and ownership—allowing it to keep data safe while also guaranteeing the immutability of data. Check out CoinGeek’s coverage on this emerging tech to learn more why Enterprise blockchain will be the backbone of AI.

I’d like to give a big thanks to Xiaohui Liu for his help is deploying the Game of Life contract, and also a big thanks to Dylan Murray for bringing life to Bitcoin.

YouTube video

New to blockchain? Check out CoinGeek’s Blockchain for Beginners section, the ultimate resource guide to learn more about blockchain technology.