What is ‘Turing-Completeness’ and What Does It Have to Do With Cryptocurrencies?

Bitcoin and other cryptocurrency enthusiasts have set chatrooms abuzz with the concept of Turing- completeness since the advent of Ethereum. Named after legendary logician and codebreaker Alan Turing, here’s a short primer on his gift to the world of cryptocurrencies.

Turing-completeness

A Turing-complete machine is, put simply, a machine that can simulate any other machine. An example might help here. If you take two machines, one which is Turing-complete and one which isn’t, and need them to perform novel tasks that they have no previous experience of, you will need to go about it in two different ways.

For the Turing-incomplete machine you will need to upload and install a new set of code which provides the machine with the ability to perform the necessary task. For the Turing-complete machine you will simply need to provide the machine instructions (for example, “achieve objective x, while not breaking rule a, b or c”) and the machine will then relay that to its previously existing code base, and arrange itself appropriately to perform the necessary task.

So Turing-completeness sounds simpler, but it comes with its own problems. Turing-completeness is great for working out decidable problems – that is, problems that can be solved by person with no particular ingenuity provided they have been given a precise set of instructions. Arithmetical sums or long division are an example of such problems.

But, as Turing and other logicians of his time found, when it comes to undecidable problems the waters get a bit murkier. A Turing-incomplete machine won’t be able to complete the problem. A Turing-complete machine, however, will at least give it a crack, though without knowable steps one can’t tell what manner of mischief the machine might get up to in order to try and solve the problem set for it. It would be a little like an inexperienced baby-sitter asking a toddler to do a painting without realising the need to supervise it to make sure it paints on the piece of paper, and not on the walls! To this extent, Turing-complete machines confront similar philosophical problems to AI, that is, we’re unclear as to what is in this Pandora’s box without peeking into it.

Bitcoin vs Ethereum

This is all a big deal in the bitcoin and Ethereum world. Ethereum is Turing-complete, and was originally marketed as such. Bitcoin is not. The difference is not in the operational deficiencies of the two, but in their purpose–bitcoin just doesn’t need to be Turing-complete.

Ethereum has the ability to take on contracts, understand them, and codify them so that actions are completed upon the contract’s conclusion . Attached to Ethereum is ether, the cryptocurrency it uses to deal with the contracts. To this extent, bitcoin and Ethereum get conflated, but whereas Ethereum is a code-base which can be used as a trusted third party and therefore needs a currency to underpin agreements, bitcoin is ‘just’ a currency.

Bitcoin has no need for Turing-completeness because it’s only ever being asked to process transactions. Ethereum, on the other hand, is being asked to understand the underlying agreements on which transactions must be processed. And it has no way, ahead of time, to know what agreements it might be asked to understand, therefore it must be coded in such a way as to be able to potentially understand anything – it must, in other words, be Turing-complete.

Rich Statefulness

Turing-completeness is only half the story. Developers have become very excited about it, so much so that Vitalik Buterin, co-founder of Ethereum, tweeted earlier this year displaying his fatigue with the topic:

Rich statefulness refers to the flexibility of the processing units on which these systems are built. Bitcoin, for example, is the equivalent of only ever having £20 notes in your wallet. You can get something different to £20 notes, but you’d have to get it made officially, which would be no small feat. Ethereum, on the other hand, has developed a systems whereby you can always have exactly the right change, thereby making any and all contracts possible, no matter their size. It is Turing-completeness which allows the rich statefulness, but it is the rich statefulness which, Buterin says, is necessary for Ethereum’s flexibility.