What the machine is made of
A Turing machine is a deliberately bare-bones imagined device. Despite its simplicity, it is the standard model for what an algorithm can do. It has four parts.
- A tape: an endless strip divided into cells, each holding one symbol from a small fixed alphabet. One symbol is designated as blank, and all cells start blank except where the input is written.
- A head: a pointer that sits over one cell at a time. It can read the symbol in that cell, write a new symbol there, and then move one cell left or right.
- A state: the machine is always in one of a finite number of states. One is the start state, and one or more are halting states.
- A state table, also called a transition table: the machine’s program, a list of rules.
The state table is the heart. Each rule says, “if you are in this state and the head reads this symbol, then write this symbol, move in this direction, and switch to this next state.” The table has a finite number of entries, so the machine’s behavior is fully described by a small piece of text.
How a step works
Every step is the same mechanical routine:
- Read the symbol under the head.
- Look up the rule for the current state and that symbol.
- Write the symbol the rule specifies (possibly the same one).
- Move the head left or right by one cell.
- Change to the new state.
If the new state is a halting state, the machine stops, and whatever is on the tape is the result. If there is no rule for the current combination, many presentations treat that as halting too. If the machine never reaches a halting state, it runs forever, which is exactly the situation the halting problem is about.
A worked example: adding one in unary
In unary notation a number n is written as n copies of the symbol 1. So three is 111. Let’s build a machine that adds one to a unary number, turning 111 into 1111.
The idea: move right until you find a blank, write a 1 there, and stop.
States: Scan (start) and Done (halting). Symbols: 1 and blank (written as _).
The state table:
- In Scan, reading 1: write 1, move right, stay in Scan.
- In Scan, reading _: write 1, move right, go to Done.
Trace it on the tape 111, with the head on the first 1:
- Step 1: Scan reads 1, writes 1, moves right. The tape is unchanged and the head is on the second 1.
- Step 2: Scan reads 1, writes 1, moves right. The head is on the third 1.
- Step 3: Scan reads 1, writes 1, moves right. The head is on the blank after the three 1s.
- Step 4: Scan reads _, writes 1, moves right, enters Done. The tape now holds 1111.
The machine halts after four steps with the answer on the tape. The number of steps is n plus one for an input of n ones, which gives 3 plus 1 equals 4 here.
Small as it is, the example shows how everything works: the head carries no memory except through the state, and all information lives on the tape.
Why the tape is unlimited
The tape is assumed to extend as far as needed in at least one direction. A machine with a fixed amount of tape would be a finite automaton, limited the way any finite automaton is. The unbounded tape is what allows counting, copying and comparing numbers of any size. Real computers cannot have infinite tape, a mismatch that theory simply accepts as an idealization.
Variations and why they do not matter much
Many variants of the machine have been studied: multiple tapes, a tape unbounded in both directions, several heads, or a head that can stay in place. They are all equivalent in power to the basic version, because each can be simulated by the simple one, though sometimes with a slowdown. A particularly useful fact: a machine that can record its own program on the tape can act as a universal machine, reading the description of any other machine and imitating it. That idea is a direct ancestor of the stored-program computer.
Where Turing machines show up in practice
You rarely write real software this way, but the model is useful as a common yardstick.
- It is the reference point for the Church-Turing thesis, which claims the model captures everything we mean by “computable.”
- It is the usual target in proofs, such as the halting problem argument.
- It is the thing that other systems simulate when people prove they are Turing complete. Tape-based esoteric languages are close cousins of the model: a head, a row of cells and simple moves, as seen in the family of tape languages.
Reading a machine description
When you meet a Turing machine, look at four things: the alphabet, the set of states, the start and halt states, and the table. Then trace a short input by hand, tracking the tape, the head position and the current state at each step. Tracing by hand is the most reliable way to build intuition, and the same habit helps when following a grid program.