Coinmonks
Published in

Coinmonks

Turing Machines on Bitcoin

Bitcoin Turing-Complete Proof

Introduction to Turing Machine

A Turing machine consists of the following components (simplified):

  • An tape with storage cells and a read/write-head that can move on the tape
  • A so-called transition function that tells the machine what to do and when.
A Turing Machine checking balanced parentheses

Church-Turing Thesis

The Church-Turing Thesis states that the Turing machine can compute anything that can be computed. It is the very definition of computation and the fundamental tool for reasoning about computers.

Simulate Turing Machines on Bitcoin

We show a generic way to simulate Turing machines on Bitcoin. We take snapshots of a running Turing machine: head position, current state, and tape. Snapshots are stored in a stateful Bitcoin smart contract. More specifically, they are in the outputs of Bitcoin transactions. Each step in running the Turing machine is triggered by a Bitcoin transaction. The Turing machines can keep running, unless it enters an accepted state.

Simulating Turing Machines (TM)

Implementation

To demonstrate the feasibility of simulating Turing machines on Bitcoin, we have implemented the aforementioned Turing machine to check balanced parentheses, as shown below.

A Turing Machine contract checking balanced parentheses
  • L9–12: define all symbols
  • L19-30: define the transition function as a table
  • L37: read the symbol from head
  • L40–43: use the current state and head symbol, we look up in the transition function table to find the new state (L46), write to the tape (L48), and move the head (L50).
  • L51–59: initially the tape contains only the input string, such as “(())()().” If any time the tape runs out, either on the left (L52) or right (L56), a blanked cell is added. This ensures the tape can be arbitrarily long and is unbounded (but not infinite²).

Deployment

We have deployed the Turing machine above to Bitcoin and run it on the input string “(())()().” The complete execution is shown below.

Turing Machine Accepting (())()()
Turing Machine at Step 0
Step 0: txid
Turing Machine at Step 3
Step 3 txid

Turing Complete Proof

It is straightforward to adapt the Turing machine contract above to implement any other Turing machines, by simply changing the states, the symbols and transition function. Thus, any Turing machine can be simulated on Bitcoin, conclusively proving Bitcoin is Turing-Complete by definition. QED.

Update: 12/2022

There is an independent paper proving a UTXO-based blockchain is Turing Complete using logic similar to ours: Self-reproducing Coins as Universal Turing Machine

Acknowledgements

Thanks goes to Pasquale Valentin for helping deploying the contract on Bitcoin.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
sCrypt

sCrypt (https://scrypt.io) is a company with a mission to provide integrated on-chain smart contracting solutions on Bitcoin Satoshi Vision