Turing completeness and gas

A system is called Turing-complete when it can express any computation that a Turing machine can perform, assuming it has enough time and memory.

That does not mean it can magically solve every problem. It means the system is expressive enough to implement any computable algorithm.

Where loops and recursion fit

Unbounded loops and recursion are common signs of Turing completeness because they allow a program to repeat work for as long as the computation requires.

repeat:    perform one step    if the result is complete:        stop    otherwise:        go back to repeat

The important word is unbounded. A loop that is guaranteed to run at most ten times does not provide the same computational power as a loop that can continue for an arbitrary number of steps.

Loops are not the formal definition of Turing completeness. A language may express repetition through recursion, jumps, function calls or another mechanism. What matters is the complete computational model rather than one syntax feature.

The halting problem

Once a language can express arbitrary computation, it can also express programs that never finish:

for {	// Continue forever.}

For many individual programs, termination is easy to prove. A loop over a fixed-size array clearly has a limit. The difficult result proved by Alan Turing is that no general algorithm can inspect every possible program and input and always decide correctly whether that execution will halt.

This is the halting problem.

It is more precise to say that termination is undecidable in general. Turing's result does not mean that the runtime of every useful program is unpredictable or impossible to prove.

Turing-incomplete systems

A Turing-incomplete language deliberately restricts what programs can express. It may remove unbounded loops, recursion or unrestricted jumps. It may also use a type system or execution model that guarantees every accepted program terminates.

This restriction can provide valuable properties:

Every valid program eventually stops.
The maximum amount of work may be easier to estimate.
Validation and security analysis become simpler.
A program cannot consume resources forever through an infinite loop.

Turing-incomplete does not automatically mean that the exact runtime of every program is obvious. A terminating computation may still be large or depend on its input. The useful guarantee is that the language has intentionally limited unbounded computation.

Bitcoin Script is a practical example. It is a stack-based language deliberately designed without loops or gotos, making it less expressive but easier to validate safely.

Accidental Turing completeness

Keeping a system Turing-incomplete can be harder than it first appears. Several individually limited features may combine to recreate unbounded computation.

For example, a language might have no while statement but allow recursive function calls. A template system might have no explicit recursion but let templates include each other dynamically. A rule engine might gain enough state and conditional jumps to simulate a general-purpose machine.

The property belongs to the whole execution model, not to a checklist of syntax features.

The EVM can express arbitrary computation

Ethereum smart contracts run as bytecode inside the Ethereum Virtual Machine. EVM bytecode has conditional jumps, memory, persistent storage and contract calls. These features allow it to express arbitrary computations, including programs that would loop forever without an external limit.

A simplified Solidity example looks like this:

function runForever() external pure {    uint256 value;     while (true) {        unchecked {            value++;        }    }}

Every Ethereum node executing a transaction must reach the same result. Allowing this function to consume CPU forever would stop block processing and create an easy denial-of-service attack.

Ethereum does not try to solve the halting problem. Instead, it gives every transaction a finite execution budget.

Gas is a computation meter

Every EVM operation has a gas cost. Arithmetic, memory expansion, storage access, logging and calls all consume gas according to protocol rules.

The basic model is:

gas remaining = transaction gas limit for each EVM operation:    gas remaining -= cost of operation     if gas remaining is insufficient:        stop with an out-of-gas error

The sender chooses a gas limit for the transaction. That limit is the maximum amount of gas the transaction is allowed to consume. A block also has a gas limit that bounds the total gas of the transactions included in it.

An execution can therefore end in three broad ways:

The contract reaches STOP, RETURN or another successful exit.
The contract explicitly reverts.
The execution runs out of gas and stops exceptionally.

An infinite loop eventually reaches the third case because its gas budget is finite.

What happens when execution runs out of gas

If a transaction runs out of gas while executing a smart contract, the EVM reverts the state changes made by that execution. The gas spent on the attempted work is not returned.

Consider a contract that updates two values:

function update() external {    firstValue = 10;    expensiveOperation();    secondValue = 20;}

If expensiveOperation runs out of gas, Ethereum does not keep firstValue = 10 while discarding only the remaining work. The execution fails atomically and its state changes are reverted.

The sender still pays for the computation that nodes performed before the failure. This makes deliberately wasteful execution expensive for the sender rather than an unlimited cost imposed on every node.

Turing-complete or quasi-Turing-complete?

The EVM is commonly described as Turing-complete because its instruction set can express arbitrary computation. It is also described more precisely as quasi-Turing-complete because every individual transaction is bounded by a finite amount of gas.

Both descriptions point to different levels of the system:

Language expressiveness: EVM bytecode can represent arbitrary algorithms.
One transaction: execution cannot continue forever because its gas is finite.
A contract over time: computation can continue across many transactions by storing intermediate state on-chain.

Gas does not make the EVM Turing-incomplete by removing expressive features. It places a resource boundary around each attempt to execute them.

Gas estimation is not a termination proof

Wallets and clients estimate gas by simulating a transaction against a particular blockchain state. This is useful, but it is not a general proof that a program always terminates or always consumes the same amount of gas.

Execution cost may depend on:

The current contract storage.
The transaction input.
The number of elements processed by a loop.
Calls to other contracts.
Which branches are taken.
State changes between estimation and inclusion.

This is why unbounded loops over caller-controlled or ever-growing data are dangerous even when they are logically expected to finish:

for (uint256 i = 0; i < users.length; i++) {    process(users[i]);}

As users grows, the function may eventually require more gas than a transaction can provide. A safer design processes a bounded page and saves progress for the next transaction.

function processBatch(uint256 start, uint256 count) external {    uint256 end = start + count;    if (end > users.length) end = users.length;     for (uint256 i = start; i < end; i++) {        process(users[i]);    }}

What I want to remember

Turing completeness describes computational expressiveness. It means a system can represent any computable algorithm given enough resources. Unbounded loops and recursion are common ways to obtain that power, but they are not the definition by themselves.

The halting problem says there is no universal algorithm that can determine whether every possible program and input will finish. It does not say that termination can never be proved for a specific program.

Ethereum handles this uncertainty with economics and resource accounting rather than static prediction. The EVM can express arbitrary computation, but every transaction receives finite gas. If execution exceeds that budget, it stops and its state changes are reverted.

The key distinction is simple: gas does not predict whether a program will halt; it guarantees that one execution cannot run forever.