Turing completeness is a term in computer science that describes the ability of a system to compute any possible calculation or program, and can be used to describe modern programming languages (Python, C++, etc.).
Turing complete describes a programmable system that can solve any computational problem. The concept comes from the Turing machine, a theoretical model of computation devised by English mathematician and cryptographer Alan Turing. Conversely, a non-Turing-complete system is limited to performing particular tasks based on pre-defined instructions.
A common analogy is that a pocket calculator is non-Turing complete because it’s only programmed to perform a limited set of mathematical calculations. However, with a home computer, it’s possible to write a program that will carry out the same task autonomously.
Bitcoin and Ethereum provide the best-known contrast for Turing completeness. Bitcoin, and its Script programming language, was designed as a non-Turing complete system with limited functionality. The Bitcoin software was programmed solely to process bitcoin transactions and cannot support complex, multi-step smart contract logic.
However, Ethereum allows developers to write code using the Turing complete Solidity programming language, and execute it using the Ethereum Virtual Machine, which is also Turing complete. Theoretically, it’s possible to write any program for any use case and run it on Ethereum.
As such, Turing completeness has important implications for what can be achieved using blockchain technology.
History of Turing complete systems
Before the age of modern computing, researchers were interested in the theoretical possibilities of what computers could achieve. In 1936, Alan Turing published a paper in which he described a hypothetical machine that’s capable of reading a simple set of arbitrary instructions based on code. The machine would have an infinite length of tape divided into boxes, where each box can be read in turn by the machine.
In each box is a coded instruction that the machine can interpret. For simplicity, the instruction can be a one or a zero. Each time the machine reads an instruction from a box, it carries out the order by overwriting the instruction with a new symbol, either one or zero, in the same box. The machine then updates its state to reflect the change, so each state captures a particular point in the execution of the code.
Visual representation of the Turing machine. Rocky Acosta, CC BY 3.0 , via Wikimedia Commons
The Turing machine model was effectively a blueprint for programmable computers before modern computing was invented. In Turing’s day, scientists needed to construct a new machine each time they needed to solve a different task. Today, even though Turing complete machines and systems are commonplace, computer scientists still use the term to describe the maximum extent of what can be achieved with computer systems, programs, and languages.
It’s important to note that as a conceptual model, the Turing machine model doesn’t account for time, processing power, or any other factor except the machine's theoretical ability to process any set of programmed instructions.
Ethereum – the first Turing complete blockchain
Ethereum was the first Turing complete blockchain that could be used for programming smart contracts and decentralized applications (dapps).
Ethereum was designed to be Turing complete in two ways.
Ethereum’s smart contracts are written using the Solidity programming language, a general-purpose Turing complete language developed specifically for Ethereum.
The Ethereum Virtual Machine (EVM), which executes the smart contracts according to the program, is a Turing complete machine.
The EVM can process any configuration of smart contracts, even if their function or utility hasn’t been conceived of yet. Therefore, the launch of Ethereum as the first Turing complete blockchain marked a significant turning point in increasing the capabilities of blockchain technology. Rather than being limited to a finite series of use cases, Ethereum allows a potentially limitless range of uses.
Practical limitations to Ethereum’s Turing completeness
Ethereum can only be said to be Turing complete on the most theoretical level because of the practical mechanics of the blockchain. Every transaction on Ethereum costs gas to execute, and therefore if a smart contract were to run into an infinite loop – which is theoretically possible on a Turing machine – it would eventually run out of gas.
This limit to Ethereum’s Turing completeness is by design, as having multiple smart contracts running on infinite loops isn’t desirable for a public blockchain network with finite processing capacity. For this reason, every transaction on Ethereum requires a gas limit which specifies the maximum amount of computing power that can be allocated to the transaction. If the transaction isn’t completed once the limit is reached, it is rejected.
However, it is important to note that very few Ethereum smart contracts utilize recursive loops and other capabilities which require Turing completeness.
Drawbacks of Turing completeness in blockchain
The infinitely programmable nature of Turing complete systems is their biggest strength, and yet it can also be a significant weakness, particularly in public blockchains where code is visible to all. This means that the code may be vulnerable to disruptions (such as bugs in the smart contracts), or unintended uses, that impede the intended functioning of the protocol. Being able to program any kind of computation allows for a vast possibility of outcomes, and it’s not possible to anticipate all of them.
If an unanticipated issue occurs in a centralized system, the company that owns the code can issues a patch immediately. However, in a blockchain-based system, it can cause considerable disruption if someone manages to find a way to trigger an outcome that wasn’t anticipated by the developer. Due to the decentralized nature of the blockchain, updates to the software can take longer because every change needs to be voted on by the community.
One of the most famous examples of this is The DAO, a smart contract set up on Ethereum in 2016 as a kind of decentralized VC fund. In a move that’s commonly referred to as a hack, a malicious actor managed to drain over $150 million of investor funds from an Ethereum smart contract, resulting in a controversial decision to roll back the Ethereum blockchain to recover the funds from the attacker. This incident resulted in the Ethereum Classic fork.
Despite the name, this incident wasn’t a hack in the true sense of the word. The attacker exploited a then-little-known vulnerability in the way the underlying code was written to execute a move now known as a reentrancy attack, calling upon an untrusted contract to drain funds.
Since The DAO incident, developers have updated programming best practices to fix this vulnerability. However, with a Turing complete system where innovators are constantly writing new code, new vulnerabilities might continue to appear.
Turing complete essentials
Turing completeness describes the ability of a system to mathematically compute any possible calculation or program. It derives from the hypothetical Turing machine, developed by English mathematician Alan Turing in the 1930s.
Ethereum was the first Turing complete blockchain to launch, which marked the moment when potentially limitless smart contract capability became available to everyone.
Although Turing complete systems open vast possibilities, programs can also result in unanticipated outcomes that may be exploited by malicious actors.