The Turing Machine

What Unites All Modern Computers

The next model of computation that we will examine is the Turing Machine. Conceived in the 1930s by British computer scientist Alan Turing, the Turing Machine defines what it means for a problem to be computable; to be more specific, many in the computer science field agree that a problem is computable if it can be run on a Turing Machine.

We will discuss the architecture of the Turing Machine along with some examples, but perhaps the biggest question on your mind is why study the Turing Machine? After all, we are studying a model of computation that is more than 85 years old, and it is difficult to see what relation smart contract development has to Turing Machines.

It turns out, however, that there is a connection between the Turing Machine and smart contract development on EVM-chains. That is, the Ethereum Virtual Machine is Turing Complete. The same computable problems that can be written for Turing machines can be translated to EVM code, and vice versa!

A Quick Note on Gas

Many might be quick to point out that the EVM is not Turing Complete due to the fact that any computation is limited by gas. While this is true, we are ignoring the limitations imposed by gas.

Tape, Scan, Write, Move

To start, we begin by answering what is perhaps the biggest question on your mind: what does a Turing Machine look like? Below is an image of a Turing Machine:

Turing Machine

From a physical perspective, there are two main components to a Turing Machine: the tape and the scanner. The tape acts as both the input to the machine and the memory that the machine can utilize throughout its execution. The scanner, meanwhile, is responsible for shifting the position of the tape while reading/writing to it.

Given its tape, each step of execution of the Turing Machine can be defined as follows:

1. Scan: the scanner of the Turing Machine reads the current symbol that is printed on the cell the scanner is above

2. Decide: given the state of the Turing Machine and the symbol it just read, the scanner then decides in a deterministic manner the action it will execute; said action consists of three parts:

   • The symbol to write onto the current tape cell

   • The state to transition to

   • The direction in which to shift the scanner (left or right)

3. Execute: with the Turing Machine knowing what to do now, the Turing Machine does the following:

   • Updates its state

   • Write to the tape

   • Move either left or right

Now that we understand the Turing Machine from a high level, we will examine its formal specification alongside some programs that make use of the Turing Machine.

The Architecture of the Turing Machine

Unlike the Cusco Model, which was defined in a programmatic manner, the Turing Machine is precise in its mathematical specification. A Turing Machine can be characterized by the following six elements:

• $Q$ : the set of states the Turing Machine can be in

• $\Sigma$ : the input alphabet

• $\Gamma$ : the working alphabet

• _ : the blank symbol

• $F$ : the set of final states

• $\delta$ : the state transition function

We discuss each element in detail:

$Q$

This is the set of states that the Turing Machine can be in through its execution lifecycle.

$\Sigma$

The letters that be written on the tape as input. It is important to note that the blank symbol _ cannot be a part of the input alphabet.

$\Gamma$

The set of all letters that the Turing Machine is able to use (i.e. read/write). Note that $\Sigma \subseteq \Gamma$.

_

The blank symbol.

$F$

The set of final states the Turing Machine can terminate with. An sample set of final states is $F = \{A, R\}$ where $A$ means accepted and $R$ means rejected.

$\delta$

Perhaps the most important component of the Turing Machine, $\delta$ can be mathematically defined as follows

$$\delta: (Q, \Gamma) \to (Q, \Gamma, d)$$

where $d$ is the direction the scanner is move in. In layman's terms, $\delta$ takes in the current tape cell alphabet and the current state and outputs the new state, tape cell alphabet, and direction to move in.

Examples

While the formal specification of a Turing Machine might appear simple, we will introduce several examples to show the state transition mechanism of a Turing Machine.

$0^n1^n$

As a first example, we want to construct a Turing Machine that will accept any string $x$ where $x \in \{0^n1^n\}$ (i.e. any string that starts with $n$ 0s followed by $n$ 1s) and rejects all other strings. Even for a simple task like this, creating a Turing Machine might appear intimidating. To start, let's begin by defining the "easier" components:

• $\Sigma = \{0, 1\}$

• $\Gamma = \{0, 1, x\}$ (here, $x$ acts as a letter to mark the cells that we have already read)

• $F = \{A, R\}$

Furthermore, we know that there is at least one state in $Q$ (let 0 be the starting state). We now begin by defining $q$; to help guide us, let's start by defining the desired logic of the Turing Machine from a high level:

• Start at the leftmost letter. If the leftmost letter is the blank symbol _, then we are dealing with the string $0^n1^n$ and so we can accept. Otherwise, move right until we find the first 1.

• Once we find the first 1, cross it out (i.e overwrite it with an $x$) and shift left until we find a 0

  • Ignoring all crossed out letters, if we come across the blank symbol _, this implies we have the string $0^i1^j$ where $i < j$ and so we reject

• After we find a 0, we cross it out and move right until we find the next 1

  • In the case that we come across the blank symbol _ (i.e. we have crossed out all the 1s), we move left one last time to make sure that we don't have any 0s remaining; if so, this implies we have the string $0^i1^j$ where $i > j$ and so we reject.

• Once we come across the blank symbol, we accept.

Now that we understand what our Turing Machine needs to do from a high level, we can implement $\delta$:

Input: Current State	Input: Current Symbol	Output: New State	Output: New Letter	Output: Direction
0	0	0	0	r
0	1	1	x	l
0	_	A	_	r
1	1	1	1	l
1	0	2	x	r
1	x	1	x	l
1	_	R	_	l
2	0	R	0	l
2	x	2	x	r
2	1	1	x	l
2	_	3	_	l
3	x	3	x	l
3	1	R	1	l
3	0	R	0	l
3	_	A	_	l

Below is a graph visualization of our Turing Machine that we just built:

Courtesy of https://turingmachine.io/

If you want to run the Turing Machine yourself, go to https://morphett.info/turing/turing.html and copy the code below into the simulator:

; This program checks if the input string is of the format 0^n1^n
; Input: a string of 0s and 1s

; Machine starts in state 0.

; State

; State 0: read the leftmost symbol
0 0 0 r 0
0 1 x l 1
0 _ _ r halt-accept

; State 1: we found a 1, getting next 0
1 1 1 l 1
1 0 x r 2
1 x x l 1
1 _ _ l halt-reject

; State 2: repeating back to 1
2 x x r 2
2 1 x l 1
2 _ _ l 3

; State 3: final check
3 x x l 3
3 1 1 l halt-reject
3 0 0 l halt-reject
3 _ _ l halt-accept

$0110$

In this next example, we will construct a Turing Machine that will accept any string that has the substring 0110 and rejects otherwise. Like last time, we begin by defining the more basic components:

• $\Sigma = \{0, 1\}$

• $\Gamma = \{0, 1\}$

• $F = \{A, R\}$

Next, we define the logic of our Turing Machine from a high level:

• Assuming that we start at the leftmost letter of the input string, we check if it is a 0. If not, we move right until we find the first 0.

  • If the string is empty, we reject.

• Once we find the first 0, we then check the next letter

  • If the next letter is a 0, we keep moving right until we find the first 1

• Assuming the next letter was a 1, we then check if the next letter is a 1

  • If the next letter is a 0, we revert to finding the next 1.

• Again assuming the next letter was a 1, we then check if the next letter is a 0

  • If the next letter is a 1, we start over

  • If the next letter is a 0, we accept

We now define $\delta$:

Input: Current State	Input: Current Symbol	Output: New State	Output: New Letter	Output: Direction
0	0	1	0	r
0	1	0	1	r
0	_	R	_	r
1	0	1	0	r
1	1	2	1	r
1	_	R	_	r
2	0	3	0	r
2	1	1	1	r
2	_	R	_	r
3	0	0	0	r
3	1	A	1	r
3	_	R	_	r

The graph visualization of the Turing Machine we just built is as follows:

Courtesy of https://turingmachine.io/

Finally, to run the Turing Machine yourself, go to https://morphett.info/turing/turing.html and copy the code below into the simulator:

; This program checks if the input string has the substring 0110
; Input: a string of 0s and 1s

; Machine starts in state 0.

; State

; State 0: read the leftmost symbol
0 0 0 r 1
0 1 1 r 0
0 _ _ r halt-reject

; State 1: check for possible 1
1 0 0 r 1
1 1 1 r 2
1 _ _ r halt-reject

; State 2: check for possible 1
2 1 1 r 3
2 0 0 r 1
2 _ _ r halt-reject

; State 3: check for possible 0
3 1 1 r 0
3 0 0 r halt-accept
3 _ _ r halt-reject

Again, Why Learn About Turing Machines?

As the two examples above might have shown, creating Turing Machines is an art in itself. However, some of you may still be wondering why this is helpful to learn when learning about smart contract development.

A smart contract, just like a Turing Machine, consists of both states and a deterministic state transition function. The state of a smart contract is comprised of the following (non-exhaustive) attributes:

• Account Nonce

• State Variables

• Account Balance

while the state transition function of a smart contract is comprised of its bytecode. When developing smart contracts, it is important to view the smart contract from a theoretical point-of-view and to consider all possible inputs/outputs and most importantly, what states the smart contract can be in; for to ignore this, one is putting their smart contract at risk of being exploited as a result of a smart contract being in an unintended state.

Resources

• Philosophical Perspective on Turing Machines: https://plato.stanford.edu/entries/turing-machine/

• Cornell CS4820 (Intro to Algorithms) Handout: http://www.cs.cornell.edu/courses/cs4820/2018sp/handouts/turingm.pdf