What is Turing Complete in the blockchain world?

Turing Complete is a term used to describe a machine that can solve any computational problem — as long as it is given enough time, has enough memory, and is fed the necessary instructions. The term, which is often used to describe modern programming languages today, is derived from the Turing Machine, a system devised by Alan Turing in the 1930s.

In this AAG Academy guide, we’ll look at the Turing Machine and explain Turing Completeness in more detail. We’ll also look at the impact of Turing Completeness on cryptocurrency, how it is associated with Bitcoin and Ethereum, and the problems it brings.

What is a Turing Machine?

If you were born into the digital age, it may be difficult to imagine a time before computers — a time when every problem had to be solved by a human, without the help of a processor of any kind. But in Cambridge, England, during the 1930s, mathematics student Alan Turing was developing a machine that would become one of the earliest computers.

In a paper published in 1936, Turing described a machine that could read and write binary code (1s and 0s) on a reel of memory tape divided up into small squares or ‘cells.’ The machine would be tasked with a computational problem written in this code, reading each cell one by one, then it would devise a solution — assuming it had enough tape to do so.

Although Turing never actually built his machine, his design for it ensured it could answer any computational problem. This is why the term Turing Complete was later coined to describe a device or programming language that can replicate a Turing Machine by running any program or solving any problem. A device or language that cannot do this is deemed Turing Incomplete.

For instance, an Excel spreadsheet is Turing Complete because of its ability to process a vast range of calculations — and because of its programming language for macros and extensions. However, HTML, a language used across the web, is Turing Incomplete because it does not have the ability to solve problems and read or write information in the same way.

Turing Completeness on the blockchain

Although modern programming languages are used to build blockchain technology, not all can be considered Turing Complete. For instance, some blockchains are designed with only basic functionality, such as the ability to process transactions and little else. In this scenario, it makes sense to use a Turing Incomplete system because simplicity and predictability are key.

However, other blockchains are built to do much more, such as run decentralized applications (DApps) and smart contracts. For these, Turing Complete systems are required because complex computation is necessary. These blockchains must be able to process a wide range of different applications that are designed to do many different things.

Problems with Turing Completeness on the blockchain

Turing Complete systems have many obvious advantages, and without them, we simply wouldn’t have the computers and software we’ve become accustomed to today. However, in certain situations, Turing Completeness can pose problems. That’s certainly true within the blockchain industry, where decentralization is widespread and security is paramount.

The combination of an open and transparent ecosystem, in which all code is visible to anyone, and Turing Completeness provides an opportunity for attackers to take advantage. It is simply not possible to anticipate the near-infinite number of outcomes and possibilities that can be produced when a system is capable of processing anything that may be thrown at it.

This means that attackers can develop applications with potentially malicious outcomes that a blockchain was not protected against by design. They can also exploit bugs and vulnerabilities in the blockchain’s code that were inadvertently left in by its developers. While a Turing Incomplete system may not be able to process certain attacks, a Turing Complete system can.

It’s important to note that major attacks on blockchains are rare, and developers are constantly working toward safer, more robust systems. However, they do still happen, and with a Turing Complete system, there will always be unintended vulnerabilities — and an opportunity for attackers to devise new ways of exploiting the system that couldn’t have been predicted.

The impact of Turing Completeness on cryptocurrency

As we touched on above, Turing Completeness has both positive and negative implications for cryptocurrency. It has paved the way for an ever-growing ecosystem of decentralized applications that can do a wide range of things, and allowed cryptocurrencies to be used for more than just making payments. This has helped make many cryptos become hugely valuable.

On the other hand, Turing Completeness also contributes to the volatile and unsteady nature of cryptocurrency. It certainly isn’t the only attributing factor, but it is a factor nonetheless. It makes certain cryptocurrencies (those built on Turing Complete systems) inherently riskier. It’s worth noting, however, that not even Turing Incomplete systems are immune to attack.

Turing Completeness in Bitcoin and Ethereum

In addition to being the two most valuable cryptocurrencies on the planet, Bitcoin and Ethereum also provide the most recognizable contrast of Turing Completeness. Bitcoin, which was built solely to serve as a form of payment, is Turing Incomplete. Its Script programming language is relatively simple, with limited functionality that is focused on transaction processing.

However, Ethereum, which was designed to be an open platform for DApps and smart contracts, uses the Turing Complete Solidity programming language. It is capable of executing complex code using the Ethereum Virtual Machine (EVM), which is also Turing Complete, which means that almost anything is possible.

References

• Turing complete
• What is turing complete
• Turing complete explained