Turing Machines: Bitcoin as a Computer

By Kurt Wuckert Jr.

Most people think of bitcoin as money and a ledger for payments. Underneath that, the scripting system is powerful enough to act like a general purpose computer. In other words, with the right structure, bitcoin can simulate a Turing machine, which is the standard model for “anything that can be computed.”

This chapter focuses on one specific technique that achieves this, using a Script feature often called OP_PUSH_TX. The goal is not to turn every transaction into a science project, but to show that bitcoin’s rules are expressive enough to implement full computation.

What Is a Turing Machine?

A Turing machine is an abstract model of a computer. It has:

  1. A finite set of states

    • One is the starting state.

    • Some are accepting states that mean “we are done and this input is valid.”

  2. A tape made of cells

    • The tape is unbounded in length.

    • Each cell holds a symbol from a fixed alphabet, like “(”, “)”, or a blank.

  3. A head

    • The head points at one cell on the tape at a time.

    • It reads the symbol under it, writes a new symbol if needed, and moves left or right.

  4. A transition function

    • A lookup table that says:“If you are in state X and you see symbol Y under the head, then write symbol Z, move left or right, and switch to state W.”

The machine keeps applying this rule over and over. Eventually it either halts in an accepting state, halts in a rejecting state, or runs forever. Despite the simplicity, this model is powerful enough to describe any effective computation.

A common example is a Turing machine that checks balanced parentheses, such as deciding whether “(())()()” is well formed. The states and rules tell the machine how to scan the string, track its internal state, and accept or reject.

The Church–Turing Thesis

The Church–Turing Thesis is a foundational idea in computer science. It says:

Anything that can be computed by any reasonable model of computation can also be computed by a Turing machine.

So, if some system can simulate a Turing machine, that system is called Turing complete. That is the bar we care about for bitcoin Script.

Bitcoin as the Turing Machine “Tape”

To map this idea onto bitcoin, we treat:

  • The global ledger as the Turing machine’s tape.

  • Transactions and their outputs as the tape cells.

  • The current state, head position, and tape contents as data stored in the locking script and transaction data.

  • Each new transaction as one step of the machine.

In this setup:

  • Every output that participates in the machine holds a snapshot of:

    • The current state.

    • Where the head is on the tape.

    • The current contents of the tape symbols.

  • The script attached to that output encodes the rules that define allowable “next steps.”

  • Spending that output with a valid input represents moving from one state to the next.

This is also what computer scientists call a finite state machine, extended across time using multiple transactions.

There are several constructions that show how to do this with Script. They all lean on a pattern known as OP_PUSH_TX, which uses the properties of digital signatures and transaction introspection to:

  • Inspect the current transaction.

  • Check the current state.

  • Enforce the correct next state.

An off-chain agent is still needed to craft the transactions, but Script enforces that only valid transitions are accepted on chain.

Simulating a Turing Machine on Bitcoin

To simulate a Turing machine generically on bitcoin, you take snapshots of its state and store those snapshots in smart contract outputs.

A snapshot needs to contain:

  • The current state (like “A”, “B” etc.).

  • The head position on the tape.

  • The tape contents (the symbols in each cell at that point in time).

These snapshots live in the outputs of bitcoin transactions. Each time you want to advance the machine by one step, you:

  1. Create a transaction that spends the current snapshot output.

  2. Run Script checks that:

    • Read the current state and head symbol.

    • Look up the correct transition rule.

    • Verify that the newly created output encodes the correct next snapshot.

  3. If all checks pass, the transaction is valid and the machine has advanced one step.

The machine keeps running as long as someone sends these “step” transactions. It naturally halts when it reaches an accepting state and no more valid transitions exist, or when no one continues to submit transactions.

Example: Checking Balanced Parentheses

As a concrete implementation, consider a Turing machine that checks whether a string like “(())()()” has balanced parentheses.

The contract is written so that each call to a public function like transit() advances the machine by one step. The structure looks like this:

  • Lines 7–13: Define the set of states

    • Include the initial state.

    • Include one or more accepting states.

  • Lines 17–21: Define the alphabet of symbols

    • For example “(”, “)”, and a blank symbol for empty cells.

  • Lines 35–51: Define the transition function table

    • For each combination of state and symbol, specify:

      • The next state.

      • What symbol to write.

      • Which direction to move the head.

  • Line 66: Read the symbol under the head.

  • Lines 71–115:

    • Use the current state and head symbol as keys into the transition table.

    • Compute the new state.

    • Update the tape contents.

    • Move the head left or right.

    • If the head tries to move past the current tape boundary on the left or right, create a new blank cell so the tape can grow as needed.

In this design, the tape is unbounded in principle, because you can always add more blank cells at each step, although it is never truly infinite in practice. It grows as you use it.

Deployment on Bitcoin

The balanced parentheses Turing machine has been deployed to bitcoin and run with input “(())()()”.

The full execution looks like a sequence of transactions:

  • At step 0, the initial snapshot includes:

    • The starting state.

    • The head at the initial tape position.

    • The tape loaded with the input string and blanks as needed.

    This is encoded in the output of a transaction, referenced by a specific TXID.

  • At step 3, the machine has taken three transitions:

    • The state may have changed.

    • The head may have moved.

    • Some tape cells may have been updated.

    This updated snapshot is stored in the output of a later transaction, with a different TXID.

Each snapshot is just another output on chain, with Script enforcing that each new snapshot follows correctly from the previous one under the machine’s rules.

Why This Proves Bitcoin Is Turing Complete

The key point is that the balanced parentheses machine is only one specific Turing machine. The same pattern works for any Turing machine:

  • You can change:

    • The set of states.

    • The tape alphabet.

    • The transition function table.

  • You keep:

    • The structure that stores snapshots in outputs.

    • The scripting rules that check legal transitions.

    • The OP_PUSH_TX style technique for introspecting and validating the current transaction.

If you can do that for arbitrary Turing machines, then by the definition used in computability theory, bitcoin Script is Turing complete. It can simulate any Turing machine, as long as you are willing to represent each step as a transaction and store the evolving state on chain.

In formal terms:

A system of data manipulation rules is Turing complete if it can simulate any Turing machine.

By showing how to encode states, tape, head position, and transitions into bitcoin transactions and scripts, and by demonstrating a working example, this construction satisfies that definition.

ELI5(ish...)

Think of a Turing machine like a very patient person with:

  • A long strip of paper divided into squares (the tape).

  • A pen that they can move left and right over the strip (the head).

  • A rulebook that says:

    • “If I am in mood A and I see symbol ‘(’ under my pen, then I should write something, move left or right, and switch to mood B.”

They follow this rulebook step by step until they reach a rule that says “stop.”

Now imagine using bitcoin as that strip of paper:

  • Each transaction output is like a snapshot of the strip at a moment in time.

  • That snapshot includes:

    • What mood the person is in.

    • Where their pen is.

    • What symbols are written on the strip.

  • Each new transaction is one more step where:

    • The “rulebook” lives in the locking script.

    • The new transaction proves that you applied the rule correctly.

    • The output of that transaction contains the new snapshot.

So the ledger becomes a timeline of the machine thinking:

  • Step 0 transaction: starting state, pen at position 0, tape says “(())()()”.

  • Step 1 transaction: state updated, pen moved, maybe one symbol changed.

  • Step 2, 3, and so on.

  • Eventually a step lands in an “accept” state that means “yes, the parentheses are balanced.”

Because you can change the rulebook, the states, and the symbols, you can build this pattern for any Turing machine. That is why we say bitcoin Script is powerful enough to behave like a general computer. It is not that every wallet is doing this on your behalf. It is that the rules are expressive enough that, if you want, you can use transactions themselves as the “tape” and Script as the “brain” to compute anything that a classic computer can compute, one transaction at a time.

Acknowledgements: This was learned primarily from this article by sCrypt