Bitcoin script is Turing Complete: sCrypt’s ‘Game of Life’ is Proof

Contracts platform sCrypt has published code to a Bitcoin Script version of Conway’s Game of Life, as a demonstration that the language is Turing Complete, and capable of maintaining a state. It challenges the controversial view from Bitcoin detractors and followers of “smart contract” blockchain platforms that Bitcoin Script is not capable of running complex computations.

Conway’s Game of Life (or just “Life”) is a famous cellular automaton that demonstrates Turing completeness. Designed in 1970 by British mathematician John Horton Conway, it is “played” by the user inputting an initial state, then watching how the set of cells evolves (or dies). The “player” has no further input once the initial state is set.

sCrypt described how the system works in a blog post, and published its Bitcoin Script code to run it. It proves Bitcoin Script’s ability to maintain a state across transaction blocks, without needing to run the entire computation on-chain.

Game of life was one of the first implementations of a Turing Complete CA, by John Horton Conway (1970). It is considered a Universal Constructor, meaning it can simulate any other Turing Machine.

This now runs on BitCoin (BSV). https://t.co/EIBA6ZK2ws

— Konstantinos Sgantzos (@CostaSga) December 10, 2020

Why is ‘Turing Completeness’ important?

sCrypt has previously published research material and code proving that Bitcoin Script is “Turing Complete,” and thus performing any computational task required to build contracts.

One issue is whether a system like Bitcoin, which works by broadcasting and processing transactions in blocks that happen every 10 minutes, can maintain a “state”—which would be necessary for data from a task taking longer than 10 minutes to perform.

Both sCrypt and Dr. Craig S. Wright have long argued that state can be preserved across multiple Bitcoin blocks, by feeding the outputs from one set of transactions into other, later ones. The newer transactions would need to validate the older outputs, or the functions would not run.

“sCrypt have a new toy, but, it proves my claim that Bitcoin is Turing Complete to be right,” Dr. Wright said.

For those looking to hear a longer discussion on Bitcoin and Turing Completeness, there is an entire episode of “Theory of Bitcoin” devoted to it.

Ayre Group and CoinGeek founder Calvin Ayre, who has frequently argued Bitcoin’s case on this particular topic, welcomed sCrypt’s new proof and said it proves Dr. Wright has a far deeper understanding of Bitcoin than anyone else—an understanding that could only come from Bitcoin’s inventor himself.

Craig proven right once more…his invention of Bitcoin was Turing complete as originally designed. https://t.co/LJQjn4wLu0

— Calvin Ayre (@CalvinAyre) December 10, 2020

“We need to be shouting this from the rooftops as this is a ‘marker’ that fell from the sky … irrefutable mathematic proof that Craig was right as only someone who had invented Bitcoin could be.”

What does Ayre mean when he says “Craig was right”? We need to look back into the history of Bitcoin, blockchain, and some of its best-known identities.

Wright vs. Szabo, 2015

The Turing-completeness argument has been running for over five years now. It was highlighted in a now-famous exchange between Dr. Craig S. Wright and cryptographer Nick Szabo in November 2015—one of Dr. Wright’s earliest public appearances as a Bitcoin speaker, shortly before his December 2015 “outing” as Bitcoin creator Satoshi Nakamoto.

Szabo appeared bemused and dismissive of Wright’s suggestion at the time, which looked at the way loops could be performed on a blockchain-based platform. Dr. Wright said control loops in Forth (the language upon which Bitcoin Script is based) could handle a looping function separate to the Forth code.

Szabo argued that if the loop couldn’t be performed in the original code then it wasn’t Turing complete. Wright countered that the only way of writing such a code would be on the “machine” itself—suggesting that attempting to do so, as Ethereum has, would render the system dysfunctional and unscalable.

“This would be a good topic for you to write a paper on, because that’s uncertainly an unconventional view that you have,” Szabo replied.

Dr. Wright did indeed publish such papers later (here and here), although the argument still rages in both computer science and general debates today.

Esoteric concept but important to understand

Dr. Craig Wright explains why the Bitcoin SV script is in fact Turing Complete (September, 2018) (https://t.co/y6b5YePCJx) pic.twitter.com/3lQgZY2WrD

— Ramon Quesada 🌷🇻🇪 (@RamonQuesadaT) December 11, 2020

Szabo was correct that the topic is esoteric, at least in that it concerns computer science concepts that outsiders might struggle to understand. However it has become a one-liner argument that dismisses Bitcoin in favor of blockchains like Ethereum, which were designed specifically (at least in theory) to perform any kind of computation on-chain.

The problem is that Ethereum has long struggled to scale to the levels it would require to perform those tasks. Attempted solutions to those problems have seen Ethereum stumble with propositions like drastic protocol and economic incentive shifts, such as moving from proof-of-work to proof-of-stake mining.

Bitcoin, on the other hand, can process any contract at any scale, and has protocol designed to be “set in stone,” unchanging to prevent disruption to the processors’ incentives that secure the network, and ensure that any transaction broadcast today (and in the past 10 years) will still be valid far into the future.

All these points are important to enterprise, governments, and developers looking to run large-scale and complex applications. The Turing completeness debate may be esoteric, but at the same time it can’t and shouldn’t be used as an argument against Bitcoin. So understanding it, at least on a basic level, is important for decision-makers.

Where altcoins and “competitor” blockchains have been unable to match BSV technically, they often substitute with simplistic arguments that dismiss BSV’s technology, or “play the man, not the ball” in the form of character assassinations on Dr. Wright.

Such arguments are easy to make on short-form, short-attention-span fora like Twitter and other social media. The real debate goes on in research papers, which most don’t read or don’t have the training to understand.

By publishing code to the Game of Life in Bitcoin Script, sCrypt has demonstrated a simple yet technically sound rebuttal to the “Is Bitcoin Turing Complete?” question, and proved a point Dr. Wright was making years before anyone else even considered it.

No doubt the social media-style arguments against Bitcoin BSV and its developers will continue, but it’s important to be able to prove they’re wrong, wherever they may appear. And it looks like Nick Szabo and others owe Dr. Wright an apology and should publicly acknowledge he was actually correct. We won’t hold our breath waiting.