Components of a Turing Machine
You'll learn: The five fundamental parts that make up every Turing Machine and enable universal computation.
Now that you know what a Turing Machine is, let's look inside. Every Turing Machine consists of exactly five essential components that work together to perform computations.
The Five Components
1. Infinite Tape
The tape is an unbounded sequence of cells extending infinitely in both directions. Each cell holds one symbol. Think of it as unlimited scratch paper—you'll never run out of space to write.
2. Tape Alphabet
The tape alphabet (Γ) is the finite set of symbols that can appear on the tape. This always includes a special blank symbol (often written as ␣ or ⊔) to mark empty cells, plus any symbols your computation needs (like 0, 1, or letters).
3. Read/Write Head
The head sits over exactly one tape cell at any moment. It can:
- Read the symbol in the current cell
- Write a new symbol to replace it
- Move one cell left or right
Imagine a person with a pencil hovering over one square of graph paper—they can see what's there, erase and rewrite it, then shift left or right.
4. State Register
The state register stores the machine's current state from a finite set of states (Q). States include a designated start state and one or more accepting (or halting) states. The state represents "where you are" in the computation's logic.
5. Transition Function
The transition function (δ) is the "program"—the rules that determine what happens next. Given the current state and the symbol being read, it specifies:
- Which state to enter next
- What symbol to write
- Which direction to move (L or R)
Key Takeaway: A Turing Machine = infinite tape + tape alphabet + read/write head + state register + transition function—these five components define the most powerful computational model in theoretical computer science.