CS4998: Blockchain Development Textbook
  • CS4998: Blockchain Development
  • Prerequisites
  • Introduction
    • Blockchain Theory
      • Bitcoin and the UTXO Model
      • Ethereum and the State-Based Model
    • Remix - A First Glance
    • Hello World!
      • Solidity File Structure
      • Primitive Values & Types
      • Contract Structure
      • Functions
      • Data Structures
      • Summary & Exercises
    • Hello World! Pt. 2
      • Control Flow
      • Interfaces and Inheritance
      • Constructors
      • Contract Interactions
      • Modifiers
      • Dynamic Arrays and Strings
        • Dynamic Arrays
        • Strings
      • Errors
      • Events
      • Units and Global Variables
      • Default Functions
  • Local Development
    • Node Providers
    • Interacting With On-Chain Contracts
    • Migrating to Foundry & VS Code
      • The Basics of Forge
      • Installing and Using Dependencies
      • Cast
      • Anvil
  • Understanding the EVM
    • The Ethereum Virtual Machine
      • A First Look at Computers
      • The Turing Machine
      • EVM Data Structures
      • Operation Codes (Opcodes)
      • Gas
      • Contract Compilation
      • Contract Runtime
    • Gas Optimizations
  • Yul & Advanced EVM Topics
    • Yul
    • Metamorphism
    • Bitwise Manipulations
  • Correctness
    • Security
    • Types of Testing
  • ERC Standards
    • Why ERCs?
    • ERC20
    • ERC721
    • ERC777
    • ERC1155
  • Frequently Used Smart Contracts
    • OpenZeppelin
    • Uniswap
    • Multisignature Contracts
    • AAVE/Compound
  • MEV & Advanced Blockchain Theory
    • Consensus Mechanisms vs Sybil Resistance Mechanisms
    • Maximal Extractable Value (MEV)
    • Looking Past The EVM
  • Etcetera
    • Developer Practices
    • Spring 2023 Past Resources
Powered by GitBook
On this page
  • Tape, Scan, Write, Move
  • The Architecture of the Turing Machine
  • Examples
  • Again, Why Learn About Turing Machines?
  • Resources
  1. Understanding the EVM
  2. The Ethereum Virtual Machine

The Turing Machine

What Unites All Modern Computers

PreviousA First Look at ComputersNextEVM Data Structures

Last updated 1 year ago

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:

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:

  • _ : 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.

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:

; 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

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

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:

; 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

QQQ : the set of states the Turing Machine can be in

Σ\SigmaΣ : the input alphabet

Γ\GammaΓ : the working alphabet

FFF : the set of final states

δ\deltaδ : the state transition function

QQQ

Σ\SigmaΣ

Γ\GammaΓ

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

FFF

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

δ\deltaδ

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

δ:(Q,Γ)→(Q,Γ,d)\delta: (Q, \Gamma) \to (Q, \Gamma, d)δ:(Q,Γ)→(Q,Γ,d)

where ddd 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.

0n1n0^n1^n0n1n

As a first example, we want to construct a Turing Machine that will accept any string xxx where x∈{0n1n}x \in \{0^n1^n\}x∈{0n1n} (i.e. any string that starts with nnn 0s followed by nnn 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:

Σ={0,1}\Sigma = \{0, 1\}Σ={0,1}

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

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

Furthermore, we know that there is at least one state in QQQ (let 0 be the starting state). We now begin by defining qqq; 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 0n1n0^n1^n0n1n 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 xxx) 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 0i1j0^i1^j0i1j where i<ji < ji<j and so we reject

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 0i1j0^i1^j0i1j where i>ji > ji>j and so we reject.

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

If you want to run the Turing Machine yourself, go to and copy the code below into the simulator:

011001100110

Σ={0,1}\Sigma = \{0, 1\}Σ={0,1}

Γ={0,1}\Gamma = \{0, 1\}Γ={0,1}

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

We now define δ\deltaδ:

Finally, to run the Turing Machine yourself, go to and copy the code below into the simulator:

Philosophical Perspective on Turing Machines:

Cornell CS4820 (Intro to Algorithms) Handout:

https://morphett.info/turing/turing.html
https://morphett.info/turing/turing.html
https://plato.stanford.edu/entries/turing-machine/
http://www.cs.cornell.edu/courses/cs4820/2018sp/handouts/turingm.pdf
Courtesy of
Courtesy of
Turing Machine
https://turingmachine.io/
https://turingmachine.io/