Glossary

    Glossary

    Turing Complete

    Turing complete describes a system that can compute anything computable, given enough time and resources. Ethereum's smart contract platform is Turing complete; Bitcoin's scripting language is deliberately not - and the difference decides what each chain can do.

    FoundationsLast reviewed 2026-10-01

    What it is

    A Turing-complete system is one that can run any calculation a computer can run, provided it has enough time and memory. The name comes from Alan Turing, who defined the model in 1936. In crypto the term marks the line between chains that can run arbitrary programs and chains that can only run simple ones: Ethereum's virtual machine is Turing complete, so developers can build lending markets, exchanges and games on it, while Bitcoin's script language is deliberately limited to basic spending conditions.

    The catch is that a system which can compute anything can also loop forever. A program with a bug can spin endlessly, consuming resources without ever finishing. This is why Ethereum meters computation with gas: every step of a program costs a fee, and when the fee runs out, the program stops. Programmable money needs a meter, because a runaway program on a shared ledger burns everyone's resources.

    Key takeaways

    • Turing complete means a system can compute anything computable, given enough resources.
    • Ethereum's virtual machine is Turing complete; Bitcoin's script is deliberately not.
    • A system that can compute anything can also loop forever - the halting problem.
    • Gas is the meter that stops runaway programs: each step costs a fee.
    • Bitcoin's limits are a feature: simple scripts mean a smaller attack surface.

    How it works

    Walk one program on Ethereum. A developer deploys a lending contract written in a language like Solidity, which compiles to instructions for the Ethereum Virtual Machine. When you deposit, the machine executes the contract's instructions step by step: read your balance, move the deposit, mint a receipt token, update the state. Each step costs gas, priced in gwei - the gas-ethereum entry covers the fee mechanics. If the program finishes, the state changes and the leftover gas is refunded; if it hits an infinite loop, the gas runs out and execution stops mid-flight.

    That meter is the entire point. The halting problem, proven by Turing, says you cannot look at a program and know in advance whether it finishes. Ethereum does not try to know; it makes finishing expensive and stopping automatic. A buggy program can only burn the gas its caller paid for, never the network's shared resources.

    Bitcoin took the other path. Its script language supports simple conditions - signatures, time locks, multi-signature thresholds - and deliberately omits loops. The smart-contract entry covers what Ethereum's generality buys; Bitcoin's restraint buys predictability and a smaller attack surface.

    Why it matters

    For an Australian reader, Turing completeness is why one chain hosts an economy and another hosts a ledger. Every DeFi protocol, NFT marketplace and on-chain exchange you see linked from this site runs on a Turing-complete platform, and the gas fees you pay interacting with them are part of the ATO's cost picture: gas on transactions is generally a cost base input, and each contract interaction can be a CGT event.

    A colleague named Brent (yes, that Brent) once asked why Ethereum fees 'cost money to fail' after a transaction reverted. The answer is the meter: the network executed steps before the failure, and steps cost gas, whoever's program fails. The highest-leverage thing most Australians can do is treat every contract interaction as billable computation - check the gas-ethereum entry before interacting, and read the smart-contract entry before signing anything a contract asks of you.

    Real-world examples

    A deposit into a lending market on Ethereum

    You deposit $2,000 AUD worth of ETH into a lending contract. The virtual machine executes the contract step by step: it reads your balance, moves the deposit, mints a receipt token and updates the state. The steps cost gas - say $4 AUD total, refunded minus $1 for the work actually done. The program finished, so the state changed and the receipt token sits in your wallet. Every one of those steps was billable computation on a shared machine.

    The transaction that failed and still cost gas

    You send a transaction to a contract that reverts - a failed check, a slipped deadline, a full queue. The machine executed steps before the failure: reading state, checking conditions, then stopping. The state did not change, but the gas for the steps already run is gone, say $2 AUD. That is the meter working as designed: failure is expensive for the caller, never free for the network. Brent's confusion above was this exact bill.

    What Bitcoin's script can and cannot do

    Bitcoin's script supports a 2-of-3 multi-signature spend, a time-locked inheritance clause or a simple signature check. It cannot run a lending market, a game or an exchange, because it has no loops and no general state. That restraint means every possible script is knowable in advance, fees are predictable, and the attack surface is small. The block entry covers the ledger those scripts write to.

    Common mistakes

    Mistake: Assuming a failed transaction on Ethereum is free.

    Why it bites you: The network executed steps before the failure, and steps cost gas. A reverted transaction still burns the gas its caller paid, which is why failed mints on busy days cost real AUD.

    Mistake: Treating Bitcoin's limited script language as a deficiency.

    Why it bites you: The limits are deliberate: simple scripts mean predictable fees and a smaller attack surface. Generality is a trade-off, not a grade.

    Mistake: Signing a contract interaction without understanding what the program does.

    Why it bites you: A Turing-complete program can do anything its code says, including moving approvals you did not intend. The [token-approval-scam entry](/glossary/token-approval-scam/) covers the unlimited-allowance trap.

    Mistake: Assuming 'programmable money' means the money programs itself.

    Why it bites you: Programs are written by developers and executed by the network, and bugs are the developer's, then your problem. The meter protects the network, not your intent.

    Ivy's take

    I spent an evening working through what actually happens between sending a contract transaction and seeing the result, and the halting problem is the bit nobody explains: Ethereum cannot know whether your program finishes, so it meters every step instead. That is the whole design in one sentence. Failures bill the caller, loops stop at zero gas, and the shared machine never burns for free.

    I ran the numbers through my own transaction history and the failed-transaction line items were small individually and annoying collectively, which is exactly how gas works. Bitcoin's restraint used to look like a limitation to me; after enough failed mints, it looks like discipline. Programmable money is real and useful, and every bit of it is billable. Treat each signature as hiring a program by the step.

    Related jargon, defined

    Ethereum Virtual Machine
    The shared computer that executes smart contract code on Ethereum.
    Gas
    Ethereum's meter for computation, where every program step costs a fee.
    Halting problem
    Turing's proof that you cannot know in advance whether a program finishes.
    Solidity
    The main programming language for writing Ethereum smart contracts.
    Script
    Bitcoin's deliberately limited spending-condition language, with no loops.
    CGT event
    An ATO-taxable disposal: selling, swapping or spending a crypto asset.

    Frequently asked questions

    What does Turing complete actually mean in crypto?+

    It means the chain can run any program a computer can run, given enough time and gas. Ethereum qualifies, which is why it hosts lending markets, exchanges and games; Bitcoin's script language is deliberately simpler.

    Why do failed Ethereum transactions cost gas?+

    Because the network executed steps of the program before it failed, and every step costs gas. The meter protects the shared network from runaway programs, which means failures bill the caller.

    Is Bitcoin Turing complete?+

    No, by design. Its script language handles simple spending conditions - signatures, time locks, multi-signature thresholds - and omits loops, which keeps fees predictable and the attack surface small.

    Does gas on contract interactions affect my Australian tax?+

    Generally yes, as a cost. Gas paid on transactions is treated as part of the cost base or a cost of disposal under the ATO's guidance, and each swap through a contract can be its own CGT event.

    Can a smart contract run forever?+

    Not on Ethereum. Gas meters every step, so a looping program stops when its caller's fee runs out. The halting problem is why the meter exists in the first place.

    Disclaimer: This information is general in nature and does not constitute financial or legal advice. Always consult a qualified professional for your specific situation.

    Keep learning

    Ivy Sinclair-Wren

    Ivy Sinclair-Wren

    Financial Chaos Analyst

    Connect on LinkedIn

    Ivy Sinclair-Wren is a Financial Chaos Analyst covering crypto markets, investing behaviour, and the Australian habit of checking prices during family dinners. Based in Melbourne, she reviews AUD Crypto Tracker's coin guides for accuracy, ATO alignment, and ruthless utility — no hype, no predictions, just what the data says.