Intuition The ONE core ideaA Turing Machine is normally a machine built to do one fixed job. The whole topic asks:
can we build one machine that reads a written description of any other machine and then
acts it out ? Yes — and that machine, the Universal Turing Machine , is why a single piece
of hardware can run any program: code is just data fed to an interpreter.
Before you can understand that sentence, you must be able to read every squiggle in it. This page
builds each symbol from absolute zero, in an order where nothing appears before it is earned. We
link the parent Universal Turing Machine and each
prerequisite as it enters.
We are not talking about metal and gears. In this subject a machine is a rule for changing a
row of symbols . Picture a long paper strip divided into boxes, and a tiny reading head sitting
over one box. That is the entire physical universe of the theory.
Look at Figure s01. The row of boxes is the tape; the yellow letters 1 0 1 1 are the input
sitting in the leftmost cells; the greyed boxes marked "blank" are empty cells we have not written
on yet (we will give this "blank" a proper symbol in §1); the red arrow is the head, pointing at
the one cell it is currently reading. Keep this picture in mind — every definition below is just a
label on some part of it.
The tape is an infinitely long strip of cells. Each cell holds one symbol (like 0, 1, or
an as-yet-unwritten "blank"). The picture (Figure s01): graph paper stretched forever.
Why we need it: it is the machine's memory and its worksheet at the same time — the only
place anything is stored.
Common mistake "The tape only stretches to the right."Why it feels right: in Figure s01 we only drew blanks running rightward, because the input
starts at the left edge.
The fix: the standard textbook Turing machine has a tape that is two-way infinite — it
runs forever in both directions, so the head can never "fall off a left end". Some books use
a one-way (left-bounded) tape instead, where cell 0 is the leftmost cell and moving L Multi-tape vs Single-tape TM .
The head is the little pointer that sits over exactly one cell. It can read what's there,
write a new symbol there, and step one cell left or right. In Figure s01 it is the red arrow.
Why we need it: a machine can only look at one thing at a time — that limit is what makes the
model simple enough to reason about.
The head reads symbols , so we need names for the allowed symbols. This is also where we finally
put a proper name on the "blank" cells you saw in Figure s01.
Look at Figure s02. The small blue bag holds the input letters 0 1; the big green bag holds
those plus two extra symbols: the blank ⊔ X
Σ Γ
Σ input alphabet : the symbols your input string is
allowed to be made of, e.g. { 0 , 1 } Γ tape alphabet : every symbol that can ever appear
on the tape — the green bag. It always contains one distinguished blank symbol ⊔ ⊔ never allowed in Σ Σ ⊆ Γ ⊔ ∈ Γ ∖ Σ
Why we need both: the machine often needs scratch symbols — extra symbols that were never
in the original input but are handy for bookkeeping — so those live in Γ Σ
Definition Scratch symbolX scratch symbol is any tape symbol in Γ ∖ Σ remember a spot on the tape . We call our example one X Why we need it: suppose a machine must remember "I already dealt with this cell". It cannot
use 0 or 1 (those are real data), so it overwrites the cell with X X w
Σ Γ Why it feels right: in tiny examples the only symbols are 0 and 1, so the bags look
equal.
The fix: Γ extra symbols — at minimum the blank ⊔ X Σ ⊆ Γ Σ Γ
w string is a finite row of symbols written left to right, e.g. 1011. The parent note
writes w input string — the actual data you hand the machine to work on. In Figure
s01 it is the yellow 1 0 1 1 sitting in the leftmost cells, with blanks stretching away after
it. Why we need it: every "run" of a machine starts by placing w
The machine also has an internal "mood" that decides how it reacts — this is a state .
Look at Figure s03. The four circles labelled q 0 q 1 q a cc q r e j δ
Q state is the machine's current internal mode, like a mood or a step-number in a recipe.
Q finite set of all states . We name individual states q 0 , q 1 , q 2 , … Q Why we need it: with only a head reading one symbol, the machine would have no memory of
what it's in the middle of doing — the state IS that short-term memory.
Three states get special jobs (all four appear as circles in Figure s03):
q 0 start state : where the dial begins.q a cc accept state : reaching it means "YES, halt and accept" (the green double
ring in Figure s03).q r e j reject state : reaching it means "NO, halt and reject" (the red double ring in
Figure s03).
0 i + 1 q i 0 i + 1 0 repeated i + 1 q 0 → 0, q 1 → 00, q 2 → 000. This is just unary counting :
tally marks. Why: to write a state down as a string we need a symbol-recipe, and tally
marks are the simplest one a machine can parse.
Now the engine: the rulebook that ties state + read-symbol to an action. In Figure s03 it is drawn
as the labelled red arrow between two state-circles; here we write that same arrow in symbols.
δ δ transition function : the complete table of
"if–then" rules. Each row looks like
δ ( q i , a ) = ( q j , b , D ) , D ∈ { L , R } . If the dial is in state q i and the head reads symbol a then write symbol b move the head direction D switch the dial
to state q j D L R ( q i , a ) ( q j , b , D )
δ q a cc q r e j δ only for the non-halting states, i.e. for q Q ∖ { q a cc , q r e j } q a cc q r e j stops immediately — there is no "next rule" to look up, because those are the
halting states . So the domain of δ ( Q ∖ { q a cc , q r e j }) × Γ , q a cc , q r e j left of a rule, only ever on the right (as a
destination). That is precisely why, in Figure s03, arrows end at q a cc q r e j leave them.
Why δ Everything a machine does — add,
palindrome-check, loop forever — is encoded entirely in this finite table. Two machines differ
only in their δ write δ and
hand it to another machine: it is finite.
M = ( Q , Σ , Γ , δ , q 0 , q a cc , q r e j ) Turing machine M Σ Γ Γ reserves a blank ⊔ ∈ Γ ∖ Σ δ q 0 , q a cc , q r e j M one specific such machine. See
Turing Machine for the full build.
M ( w ) M ( w ) M w M outcome of starting M w q 0 δ M ( w ) accept , reject , or loops forever
(never halts) . So M ( ⋅ )
Here is the leap that makes the whole topic possible.
⟨ M ⟩ ⟨ M ⟩ M M M tape
itself , as data.
Why we need it: a machine can only be fed strings. To let one machine read another, the
second machine must first be turned into a string . ⟨ ⋅ ⟩
⟨ M , w ⟩ ⟨ M , w ⟩ ( M , w ) program and its data glued into one string . Concretely: take ⟨ M ⟩ separator that cannot occur inside either piece (for the unary scheme in the parent, the
block 111 already marks the end of the machine), then append the string w ⟨ M , w ⟩ = ⟨ M ⟩ separator 111 w . ⟨ M ⟩ w ⟨ M , w ⟩ unambiguously split back into M ⟨ M , w ⟩
⟨ M ⟩ The fix: ⟨ M ⟩ ⟨ M , w ⟩ literally just a string , like
111010011.... The angle brackets are a reminder of what it means , not a new type of thing.
Because it is an ordinary string, it can be fed to a machine as data — that is the entire trick.
U U Universal Turing Machine — one fixed machine that reads ⟨ M ⟩ w M w U (⟨ M ⟩ , w ) = M ( w ) , U M w same answer as running
M w ⟨ M ⟩ w M ( w )
⟺ ⟺ if and only if ", sometimes shortened to "iff") is a
two-way promise between two statements . "P ⟺ Q both "if P Q and
"if Q P P Q same switch. Why we need it: we want to say U M same in
both directions, not just one.
↓ ↓ halts " — the machine stops (either accepts or rejects) rather
than running forever. The parent's statement
U on ⟨ M , w ⟩ ↓ ⟺ M on w ↓ U if and only if M ⟺ and loop-together). Why we need this
symbol: not every machine halts; we need shorthand to talk precisely about whether it does.
Machines that may never halt are the world of Recursively Enumerable Languages .
These foundations feed three big destinations you'll meet after this note:
The idea "fixed machine + variable program on tape" is exactly the Stored-Program Computer
and von Neumann Architecture .
Feeding U itself (⟨ U ⟩ Diagonalization and the
Halting Problem .
The claim that U not more powerful — just more flexible — is the Church-Turing Thesis .
The multi-tape design of U Multi-tape vs Single-tape TM equivalence.
How to read the map below. Read it top-to-bottom: each box is a foundation from this page, and
an arrow "X → Y X Y Tape and Head (§0);
it lets us talk about Alphabets (§1), which lets us talk about strings and w (§2). Separately,
the States box (§3) and the alphabets feed the Transition function δ (§4). Bundle those
and you get the Machine tuple M ; encode that tuple as a string and you get Encoding of M
(§5); feed that plus states into the Universal machine U (§6). The final box shows the two
topics this page unlocks.
Alphabets Sigma and Gamma
States set Q and q0 qacc qrej
Transition function delta
Encoding of M as a string
Universal Turing Machine U
Stored-Program and Halting Problem
Cover the right side and test yourself — you're ready for the parent note when every line is easy.
What is the tape? An infinite strip of cells, each holding one symbol — the machine's memory and worksheet.
Is the standard tape one-way or two-way infinite? Standard textbook TMs use a two-way-infinite tape; one-way (left-bounded) variants exist and compute the same things.
What does the head do? Sits over one cell; it can read, write, and step one cell left or right.
Difference between Σ Γ Σ Γ Σ ⊆ Γ
Where does the blank symbol ⊔ In Γ Σ ⊔ ∈ Γ ∖ Σ
What is a scratch symbol like X A tape symbol in Γ ∖ Σ
What is w The input string — the data placed on the tape at the start of a run.
What is a state, and what is Q A state is the machine's current internal mode; Q
What do q 0 q a cc q r e j Start state, accept (halt-yes) state, reject (halt-no) state.
On which states is δ On the halting states q a cc q r e j ( Q ∖ { q a cc , q r e j }) × Γ
Read δ ( q i , a ) = ( q j , b , D ) In state q i a b D q j
What is D ∈ { L , R } The move direction — left or right by one cell.
What does M ( w ) The function computed by M M w
What does ⟨ M ⟩ The finite-string description (the "program") of machine M
What does ⟨ M , w ⟩ The pair ( M , w ) ⟨ M ⟩ w
Why can any machine be encoded as a string? Because Q Γ δ
What does ⟺ If and only if — a two-way promise: both statements are true together and false together.
What does U (⟨ M ⟩ , w ) = M ( w ) Running U M w M w
What does ↓ The machine halts (stops), as opposed to looping forever.
