Alan Turing is an English mathematician who invented the Turing machine, which is an abstract model that performs computations by reading from and writing to an infinite tape. Turing completeness refers to the ability of a system of instructions (such as a programming language) to simulate the operation of a Turing machine.
What Is a Turing Machine?
A Turing machine consists of the following:
- An infinite strip of tape split into cells, one beside the other. The tape acts like the memory in a typical computer or any other form of data storage. Each cell on the tape contains a symbol from a finite alphabet (representing instructions). The machine always has enough tape to handle any given computation, constituting infinite memory.
- A head that acts as a pointer to the cell of memory currently being inspected, positioned over a cell by the machine to read the symbol stored within. The machine can move the head left or right by only one cell at a time.
- A state register that stores the machine’s current state — one of a finite number of states used to govern the machine’s behavior. Among these is a special start state from which the register is initialized.
- A finite table of instructions (also known as the transition functions) that is checked by the machine during each step, and defines what the machine should do given any valid combination of states and symbols.
Example of a finite table (Source: Brilliant.org)
A Turing machine’s tape is initialized with a string of (typically blank) symbols, with the head positioned over one of its cells. When the head reads any given symbol, the machine consults the finite table for the following:
- The current status on the state register
- The symbol read by the head
- Which symbol to write to the cell
- Which direction to move the head
- What state to change the machine to
A Turing machine checking whether a string is a palindrome (Source: Anthony Morphett, http://morphett.info/)
What is a Turing Complete machine?
Every part of the machine (its state, symbols, and used tape) and its operations (writing and erasing symbols and moving the tape) are finite, discrete, and distinguishable. It is only the unlimited amount of tape (memory) that provides the machine with infinite storage space.
The Church-Turing thesis posits that any computable problem can be solved by a Turing machine. A “Turing-complete” machine or programming language is capable of executing any task accomplishable by a computer given enough time and memory, no matter its complexity. The majority of programming languages are considered Turing complete.
Advantages of a Turing Complete System
A major advantage of Turing-complete systems is their adaptability. To perform a previously undefined task, one would need to provide a non-Turing-complete system with a completely new set of code. Turing-complete systems, on the other hand, require only that you provide them with the corresponding set of instructions to execute on the existing codebase.
This approach works great for problems that have predefined steps and solutions (such as most arithmetic problems) but can lead to problems when it comes to undecidable problems. While a non-Turing-complete system would simply not be able to compute the problem, a Turing-complete system will still attempt to do so, which may result in unexpected or undesirable behavior.
Is Bitcoin and Ethereum Turing Complete?
The easiest way to explore how Turing completeness affects blockchain technologies is by comparing Ethereum (ETH), which is Turing complete, and Bitcoin (BTC), which is not. The Turing completeness of a blockchain is a matter of design rather than technical competence, and informs the functions and challenges of the project.
Why is Bitcoin Blockchain designed to be non-Turing Complete?
The Bitcoin blockchain was purposefully designed to be non–Turing complete to target its specific use-case (that of digital currency), where Turing completeness was considered unnecessary and potentially harmful. While Bitcoin’s scripting language is powerful enough to express some smart contract functionality, such as multi-signature wallets and the Lightning Network, it cannot implement loops or read/writes to arbitrary locations in memory.
Is a Non-Turing Complete Blockchain good?
A key advantage of non-Turing-complete blockchains such as Bitcoin is that processes are guaranteed to terminate at a runtime proportional to their length — a useful security feature for a digital currency. The simple nature of Bitcoin’s scripting language also ensures that developers can predict how their applications will react, given the finite number of possible situations. The drawback is that such blockchains simply cannot support the same level of applications that Ethereum can, significantly limiting their generality.
Why is Ethereum Blockchain Turing Complete?
The Ethereum blockchain, on the other hand, was designed from the ground up to serve as a platform for customized decentralized applications (DApps). While Bitcoin has no need for Turing completeness as it only needs to process transactions, Ethereum must interpret the underlying logic on which these transactions are based. As Ethereum has no way of knowing in advance what kind of transactions it might be asked to interpret, the blockchain must be designed in a way to potentially understand anything. In other words, it must be Turing complete.
How does Turing Compelteness helps Ethereum?
Turing completeness helps Ethereum implement sophisticated smart contracts that support looping and branching through the Solidity programming language, along with their deployment and execution through the Ethereum Virtual Machine (EVM). The Turing-complete nature of Ethereum smart contracts means that they are theoretically capable of executing any task a regular computer program could. This has opened up a wide range of possibilities, such as the creation of fungible tokens through the ERC-20 standard, decentralized finance (DeFi) applications, and automated market makers (AMMs).
Is a Turing Complete Blockchain bad?
A key disadvantage of Turing-complete blockchains such as Ethereum is that not only may certain transactions fail to terminate, but also it’s impossible to determine whether any given transaction will terminate. This is known as the halting problem and is the reason gas is required. Once the gas is used up, any transaction with an infinite loop will terminate. In this sense, the EVM is technically only quasi-Turing complete, as all execution processes are limited to the finite number of computational steps allowed by the amount of gas in a smart contract.
Another issue is that the programmability and flexibility offered by Turing completeness goes both ways. While Ethereum is in many ways more powerful than Bitcoin, the complexity of its smart contracts has also made it more vulnerable to malicious parties. The recursive call exploit that enabled the DAO hack and splintered the Ethereum network was only made possible by the Turing-complete nature of the smart contract. Other vulnerabilities such as reentrancy attacks are also not present in non-Turing-complete blockchains.
Turing Completeness vs. Rich Statefulness?
Rather than Turing completeness, founder Vitalik Buterin outlines a concept he calls “rich statefulness” as the key value proposition of Ethereum. “Rich statefulness” is the ability of a system to remember information at the blockchain level. As an illustration of this concept, if someone contributed funds to a “trustless insurance” contract, their total contribution, tickets, and claims would all be automatically stored and updated on the blockchain. This functionality is not possible on Bitcoin, which utilizes the UTXO (unspent transaction output) and is considered stateless.
According to Buterin, “once you have Ethereum’s philosophical model (viewing scripts as “doing stuff” rather than being “predicates”), then Turing-completeness actually becomes harder not to have than to have.” While the Turing-complete nature of Ethereum serves as its foundation, it is the rich statefulness that provides the network with flexibility and enables complexity beyond what is possible on the Bitcoin blockchain.
What Are the Security Risks of Turing Completeness?
The Ethereum project’s decision to design a Turing-complete language (Solidity) for its smart contracts has been the subject of much public scrutiny, especially after numerous high-profile security breaches. Solidity’s power enables both developers and malicious actors and can be seen as an extension of the project’s focus on cutting-edge functionality over stability.
Non-Turing-complete implementations remain an attractive option for blockchains such as Lamden (TAU), which are more stability-minded (or do not require such a wide range of functionality). Projects such as Algorand (ALGO) have embraced non-Turing-completeness as the way forward, arguing that Turing-complete smart contracts add an immense attack surface while being unnecessary for the majority of use cases.
An article written by Taylor Rolfe noted that the majority of the known attack vectors on Solidity could have been eliminated through non-Turning completeness. Contrary to Ethereum’s design philosophy, other projects argue that risk-averse technologies such as smart contracts should be designed to limit risk, even at the cost of potential performance.
Approximation of the “dead weight” attack surface inherited when using Turing-complete languages for smart contracts (Source: Kadenka)
Conclusion
The debate around Turing completeness is fundamentally one of security versus performance. A key reason for which projects such as Bitcoin are more programmatically secure than Ethereum is that their purposes are more limited. Such measures are difficult to implement in Ethereum given the project’s positioning as more of a platform rather than a specific service.
Turing-complete smart contract languages such as Solidity provide greater opportunities for applications, both useful and malicious. The cost of such power is a significant level of added risk, one that many developers and users may prefer to avoid.
Register to get $180 Welcome Bonus!
