Turing complete describes a programming language or machine that can carry out any calculation a general-purpose computer can, given enough time and memory. In practice that means it supports conditional branching ("if this, then that") and unbounded loops or recursion. Almost every everyday programming language is Turing complete.
The term comes from the British mathematician Alan Turing, whose 1936 paper "On Computable Numbers" described an abstract "Turing machine" that defines what is computable. In crypto, the phrase is used to separate smart-contract platforms such as the Ethereum blockchain, whose virtual machine can run arbitrary programs, from systems such as the Bitcoin blockchain, whose scripting language is deliberately limited.
Turing complete in plain terms
Compare a pocket calculator with a laptop. The calculator can do a fixed set of jobs: add, subtract, maybe square roots. The laptop can run any program anyone writes, from a spreadsheet to a game. The laptop is "Turing complete"; the basic calculator is not.
The flexibility has a price. A program that can do anything can also get stuck forever, for example in a loop that never ends, and there is no general way to tell in advance whether it will. On a shared blockchain, where thousands of computers run the same code, a program that never stops would freeze the network. So blockchains that allow full programs need a way to cut them off.
Bitcoin Script and Ethereum compared
Bitcoin transactions are locked and unlocked with Script, a small stack-based language. Script has no loops and a limited set of operations, so every script finishes in a predictable number of steps. That makes Bitcoin easier to analyse and harder to attack through its programs, but it limits what can be built directly on the base layer. Upgrades proposed through the BIP process have added capabilities while keeping Script non-Turing-complete.
The Ethereum white paper, first published in 2013, argued for a blockchain with a built-in Turing-complete language, so that developers could write any smart contract without the protocol needing a new feature for each use. Contracts written in languages such as Solidity are compiled to bytecode and run on the Ethereum Virtual Machine (EVM), the engine behind ether-based applications and many Ethereum-compatible blockchains.
Gas and the halting problem
Turing proved that no program can decide, for every possible program, whether it will eventually stop. This is the halting problem. A blockchain therefore cannot screen out endless loops before running them.
Ethereum solves this economically. Every operation costs a set amount of gas, and each transaction states a maximum it will spend. The sender pays a gas fee based on gas used and the gas price. If a program runs out of gas it stops, its changes are reversed, and the fee is still paid. Each block also has a gas limit. Because of these limits, Ethereum's Yellow Paper calls the EVM "quasi-Turing-complete": it can express any computation, but every actual run is bounded.
The cost of a run is calculated as:
Here "gas used" is the number of gas units the computation consumed and "gas price" is what the sender pays per unit, quoted in gwei (one billionth of an ether). If a transaction uses 50,000 units of gas at a price of 20 gwei per unit, the fee is 1,000,000 gwei, or 0.001 ether. A loop that would never end simply burns through its gas allowance and stops.
Other platforms use similar meters. Solana programs have compute budgets, and Cardano (ADA) charges for execution units in its Plutus scripts.
Benefits and risks
- Expressiveness. Full programmability made possible DeFi, NFTs, DAOs and the composability between them.
- A larger attack surface. More complex code means more room for bugs. In June 2016 an attacker exploited a reentrancy flaw in The DAO, a large investment contract, and drained about 3.6 million ether. Ethereum reversed the theft through a hard fork, and those who rejected it kept the original chain as Ethereum Classic (ETC).
- Harder verification. Programs that can do anything are hard to check fully, which is why audits and formal verification are common before large contracts go live.
- Cost for nodes. Every node must run every contract, which raises hardware demands and is one reason for scaling work such as rollups and sharding.
What Turing completeness does not imply
Turing completeness does not make a platform faster, more secure or more decentralised. It also does not mean a contract can reach outside the chain; data from the outside world still needs a blockchain oracle. And a non-Turing-complete system is not useless: Bitcoin supports multi-signature wallets, timelocks and the hashed timelock contracts behind the Lightning Network without general-purpose programs.