What is Turing completeness and how does it relate to cryptocurrencies?

Turing-completeness refers to a characteristic of computing platforms where a computer that is deemed Turing-complete can execute all programs that a Turing Machine would be able to execute.

Turing machines are also known as “universal machines” because they are able to solve any problem that humans are able to solve by any known means. Programs that are not solvable by Turing machines are also known as non-computable.

In very basic terms a Turing machine is an infinite tape where data can be written, read or the tape can be moved back and forth based on the commands that were read from it. The following illustration, shows what a real world Turing machine would look like using motors and and magnetic heads:

This very simple concept is revolutionary compared to the computer models that came before it because a Turing machine is able to write or read to any position on this tape based on a single command. This precedes the concept of Random Access Memory (RAM), the main difference being that while the Turing machine tape can be accessed randomly, it must scroll the tape up and down, whereas the RAM machines can access any spot on memory directly, by just addressing the location. This latter and more sophisticated model was made possible by digital integrated circuits which could receive addresses on its electrical pins instead of tapes which must be scrolled to the correct position on demand.

In the cryptocurrency universe, Turing machines are important because it helps to define what a Second Generation Cryptocurrency is. Ethereum possesses a Turing-complete programming language called Solidity embedded into the Ethereum Virtual Machine (EVM). This means that Ethereum can be used to express and solve any known solvable computer problem. Any program that can be implemented in Java, C++, Scala, Haskell or any other Turing-complete language can be implemented in Solidity and run on the Ethereum platform as well. In theory you could implement something like Windows or Linux in Ethereum, were these programs to have graphical interfaces (which they won’t – this is just a theoretical example).

Bitcoin, in contrast, does not have a Turing-complete scripting language embedded in it, but instead uses a simpler model based on stacks. In Bitcoin, if the last value placed on a virtual “stack” of values is TRUE then the transaction happens, otherwise it fails (for example if the cryptographic signature on a transaction is fake or incorrect). Ethereum took the concept of the blockchain-stored scripting language a step further and turned the script interpreter into a Turing-complete platform that can execute any computer program known to man. This was a major leap forward and sparked a revolution in the cryptocurrency universe, turning Ethereum into the #1 contender for most valuable cryptocurrency, just behind Bitcoin.

Fun fact: Turing machines were developed for cryptography and their concept was born when attempting to break enemy cryptographic codes during World War II!

We hope this brief intro to Turing-completeness, as it relates to cryptocurrencies, has given you a clearer view of the importance of the Ethereum contribution to the world of cryptocurrencies.