Making a Turing Machine in Bitcoin’s script

Introduction

While Bitcoin supports smart contracts through its script, the expressive power of the language is intentionally limited. Particularly it doesn’t have loops and therefore it is considered to be not Turing Complete. It is possible though to approximate a loop through repeated if statements in the following way:

while (condition) doSomething();

is equivalent to

if (condition) doSomething();
if (condition) doSomething();
...

So let’s attempt to write a Turing Machine! We will be using the following notation to define code blocks:

.codeBlockName {
    // statements go here
    // comments too
}

The components

We will start by writing all the components of a Turing Machine (TM).

The tape

A TM requires an infinitely long tape divided into cells where characters can be written and read from. We will store the cells as elements on the two stacks available to the script. We will divide the tape into two parts: the part to the left of the read/write head, stored in the alt-stack, and the part under and to the right of the read/write head, stored on the stack. We will also need to store the number of elements stored in the alt-stack (as the script offers no way to retrieve that) and the current state of the Finite State Machine (FSM) corresponding to the TM (more on that later).

Writing to the tape

.write(.val) {
    OP_NIP
    .val
    OP_SWAP
}

Moving the read/write head to the left

.moveLeft {
    OP_FROMALTSTACK
    OP_DUP OP_0 OP_NUMEQUAL OP_IF // if the alt-stack is empty
        OP_0 // add an empty element
    OP_ELSE
        OP_1SUB
        OP_FROMALTSTACK
    OP_ENDIF
    OP_SWAP
    OP_TOALTSTACK
    OP_SWAP
}

Moving the read/write head to the right

.moveRight {
    OP_SWAP
    OP_FROMALTSTACK OP_1ADD
    OP_TOALTSTACK OP_TOALTSTACK
    OP_DEPTH OP_1 OP_NUMEQUAL OP_IF // if there are no more elements
        OP_0 OP_SWAP // add an empty element (under the read/write head)
    OP_ENDIF
}

The FSM

The movement of the read/write head and writing to the tape is controlled by a FSM. Our TM needs to check whether the current state and symbol match one of the transitions and execute the matching one. Finally we need to check that the FSM reached one of its acceptance states.

Checking and executing a transition

.execute(.curState, .input, .nextState, .output, .movement) {
    OP_2DUP
    .curState OP_NUMEQUAL
    OP_SWAP
    .input OP_EQUAL
    OP_BOOLAND OP_IF // if the current state and symbol match the transition
        .write(.output) 
        .movement
        OP_DROP .nextState
    OP_ENDIF
}

Checking if the curent state is an acceptance state

.checkAccept(.state) {
    OP_OVER
    .state OP_NUMEQUAL
    OP_BOOLOR
}

OP_FALSE
.checkAccept(.state1)
.checkAccept(.state2)
...
.checkAccept(.stateN)
OP_VERIFY

Joining the components together

Now that we have all the components of the FSM there are two more steps. We will need to first initialize the alt-stack size and the initial state, and finally ensure that the stack contains only one element (OP_TRUE) at the end of the execution. For that we will need to repeatedly apply .clean:

.clean { OP_DEPTH OP_0NOTEQUAL OP_IF OP_DROP OP_ENDIF }

Therefore, the final script will be:

// init variables
OP_0 OP_TOALTSTACK .initState

// execute the TM transitions
.execute(.curState1, .input1, .nextState1, .output1, .movement1)
.execute(.curState2, .input2, .nextState2, .output2, .movement2)
...
.execute(.curStateN, .inputN, .nextStateN, .outputN, .movementN)

.execute(.curState1, .input1, .nextState1, .output1, .movement1)
.execute(.curState2, .input2, .nextState2, .output2, .movement2)
...
.execute(.curStateN, .inputN, .nextStateN, .outputN, .movementN)

...

// check that we finished at an acceptance state
OP_FALSE
.checkAccept(.state1)
.checkAccept(.state2)
...
.checkAccept(.stateN)
OP_VERIFY

// clean the stack
.clean
.clean
...
.clean

// the script finishes as valid
OP_TRUE

Limitations

While we would normally need to include enough .execute blocks for the TM to halt for all inputs it may be difficult to calculate that. In order for the script to halt even in the presence of an infinite number of .execute blocks nested if statements would have to be used instead.

Also, while the script would be able to simulate any TM it will fail to reject unknown inputs. Again, nested if statements combined with checking whether some transition has been matched would solve that.

The real world

Unfortunately, the above script would be impractical to use in the real world because of the limitations imposed by Bitcoin’s virtual machine. Particularly there is a limit of 201 non-push operations per script which greatly limits the number of transitions that can be executed.

We can reduce the number of operations needed per transition by assuming that we will never run out of tape elements stored in the stacks, which allows us to greatly simplify the movement of the read/write head:

.moveLeft { OP_FROMALTSTACK OP_SWAP }

.moveRight { OP_SWAP OP_TOALTSTACK }

Demonstration

I wrote a TM compiler which targets Bitcoin’s script.

Due to the limit on the number of operations per script only the simplest TMs can be executed on the Bitcoin blockchain. A transaction which spends from an output accepting even length strings of ones (up to the length of 3) is 22553e36c09bbb5e470826b70f53152d3bbc22666991d92cb423ab128e03aaf8.

Conclussion

So we have shown that we can write a TM in Bitcoin’s script. Does that mean we could (in principle) execute any program? No! Turing Completeness only implies that any computation can be performed. What a program can do depends on how it can interact with the real world. Bitcoin scripts can receive very few inputs from outside. Ultimately though it doesn’t matter much because “smart contracts” which need to interact with the real world extensively need to rely on human consensus anyway making them redundant.