# 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!

### 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:

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:

**Scan**: the scanner of the Turing Machine reads the current symbol that is printed on the cell the scanner is above**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)

**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:

_ : the blank symbol

We discuss each element in detail:

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

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.

#### _

The blank symbol.

### 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.

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

Once we come across the blank symbol, we accept.

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

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:

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:

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

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

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

### 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

Last updated