Skip to content

Turing Machines

Imagine you have a roll of paper tape that stretches infinitely in both directions. You also have a simple mechanical box that sits on this tape. This box can do only three things: read the symbol written on the paper, write a new symbol, and move one step to the left or right.

It sounds primitive, like a toy. Yet, this simple theoretical device—the Turing Machine—is powerful enough to simulate every computer that has ever existed or will ever exist. From the supercomputer running climate models to the smartphone in your pocket, they are all just optimized Turing Machines.

The Model

Alan Turing proposed this model in 1936, before electronic computers were even built. He wanted to define exactly what it means to "compute" something.

A Turing Machine consists of four essential parts:

  1. The Tape: An infinite strip of paper divided into cells. Each cell contains a symbol (like 0, 1, or A) or is blank. This is the machine's memory.
  2. The Head: A device that can read the symbol at the current cell, write a new symbol, and move the tape Left (L) or Right (R).
  3. The State Register: A variable that holds the current "state" of the machine (e.g., START, FIND_ZERO, HALT).
  4. The Finite Table of Action (The Program): A set of rules that tells the machine what to do.

The Rules of the Game

Every operation follows a strict pattern based on two inputs: 1. The Current State of the machine. 2. The Symbol currently being read by the head.

Based on these two inputs, the machine produces three outputs: 1. Write a symbol to the current cell. 2. Move the head (Left or Right). 3. Switch to a new state.

It looks like a function: (Current State, Current Symbol) → (Write Symbol, Move Direction, New State)

Visualizing with State Graphs

While you can write out rules in a table, computer scientists often use State Graphs (or State Transition Diagrams) to visualize them.

  • Nodes (Circles) represent States.
  • Arrows represent Transitions.
  • Labels on Arrows show the rule: Read / Write, Move

For example, a label 0 / 1, R on an arrow from State A to State B means: "If you are in State A and read a '0', write a '1', move Right, and go to State B."

Example: The "Bit Flipper"

Let's design a simple Turing Machine that reads a string of binary digits (e.g., 1101) and flips them (to 0010).

Setup: - Tape: ... # 1 1 0 1 # ... (where # is a blank space) - Head: Starts at the first 1. - States: FLIP (working), DONE (finished).

The Rules:

Current State Read Write Move New State Description
FLIP 1 0 Right FLIP See a 1? Make it 0, keep going.
FLIP 0 1 Right FLIP See a 0? Make it 1, keep going.
FLIP # # Left DONE Hit a blank? We're finished. Back up one step.

The Execution:

  1. Start (State: FLIP): Head reads 1. Rule says: Write 0, Move R, Stay in FLIP. Tape is now 0 1 0 1.
  2. Step 2 (State: FLIP): Head reads 1. Rule says: Write 0, Move R, Stay in FLIP. Tape is now 0 0 0 1.
  3. Step 3 (State: FLIP): Head reads 0. Rule says: Write 1, Move R, Stay in FLIP. Tape is now 0 0 1 1.
  4. Step 4 (State: FLIP): Head reads 1. Rule says: Write 0, Move R, Stay in FLIP. Tape is now 0 0 1 0.
  5. Step 5 (State: FLIP): Head reads # (Blank). Rule says: Write #, Move L, Go to DONE. Machine halts.

Why This Matters: Universality

The specific machine above is a "special-purpose" Turing Machine—it only flips bits. But Turing discovered something profound: you can build a Universal Turing Machine (UTM).

A UTM is a Turing Machine that can read the description of another Turing Machine (written on its tape) and simulate it.

This is the separation of Hardware and Software. - The UTM is the Hardware (the CPU). - The description on the tape is the Software (the App).

Before this, computing machines were built for single tasks (calculating tides, cracking codes). To change the task, you had to rebuild the machine. Turing proved that you only need one machine design; to change the task, you just change the tape.

Practice Problems

Practice Problem 1: Parity Checker

Design a Turing Machine (in descriptions) that reads a binary string and determines if it has an odd number of 1s.

  • Start at the beginning of the string.
  • If the number of 1s is odd, write 1 at the end.
  • If even, write 0.

Hint: You need two states to track the parity as you scan.

Solution

States: 1. EVEN (Start state, assumes we've seen 0 or even 1s so far) 2. ODD (We've seen an odd number of 1s so far) 3. HALT

Rules: - State EVEN: - Read 0: Stay EVEN, Move R (0 doesn't change parity). - Read 1: Switch to ODD, Move R. - Read #: Write 0 (count was even), Move L, -> HALT. - State ODD: - Read 0: Stay ODD, Move R. - Read 1: Switch to EVEN, Move R. - Read #: Write 1 (count was odd), Move L, -> HALT.

Practice Problem 2: The Infinite Loop

Can you design a rule that causes a Turing Machine to run forever?

Solution

Yes, it's very simple. Just create a state that moves without changing anything fundamental or reaching a halt state.

Rule: - State RUN: Read Any, Write Same, Move Right, Next State RUN.

The head will just travel to the right forever (assuming an infinite tape). This concept is crucial for the Halting Problem.

Key Takeaways

Concept Meaning
Tape Infinite memory storage.
Head The mechanism that reads and modifies memory.
State The current "context" or memory of what the machine is doing.
Transition The rule: (State, Symbol) -> (Action, New State).
Universal Turing Machine A machine that can simulate any other machine (Software).

The Turing Machine is the atom of computer science. It strips away all the complexity of RAM, caches, and transistors to reveal the pure mathematical heart of computation: Reading, Writing, and Changing State.