Intuition The one core ideaA Turing machine is just a strip of paper cells with a pencil-eraser head that reads one cell, rewrites it, and shuffles one step left or right — following a tiny fixed rulebook. Everything else in the parent note is bookkeeping notation for describing that one picture precisely enough to reason about it.
Before you can read the parent note (topic note) , you need to see every symbol it throws at you. We build them one at a time, each on top of the last. Nothing is used before it is drawn.
Two words appear on every line of the parent note, so let us pin them down first.
Definition Set — a bag of allowed thingsA set is just a collection of items with no repeats and no order. We write it with curly braces: { 0 , 1 } 0 1 x x ∈ S x S x ∈ / S
Definition Alphabet and stringAn alphabet is a finite set of symbols — the characters you're allowed to write. A string is a finite row of those symbols placed side by side, like 0110. The set of all strings you can build from an alphabet Γ Γ ∗
Think of the alphabet as the keys on a tiny typewriter, and a string as one line typed with those keys. Γ ∗
The parent note needs these because a Turing machine's whole job is to read and rewrite strings built from an alphabet .
The tape is an infinitely long strip divided into equal boxes called cells . Each cell holds exactly one symbol at a time. The strip stretches forever to the right (and by convention starts at a left edge — cell 0
Why infinite? Because we want no memory limit . A finite automaton has a fixed brain; a real computer runs out of RAM. The tape's endlessness is what makes the model able to compute anything computable .
Intuition But the input is finite!You only ever write finitely many symbols. So how does the machine know where "your writing" ends and "empty space" begins? That is exactly what the blank symbol below is for.
⊔ ⊔ this cell is empty . Every cell you never wrote to holds ⊔
Common mistake "Blank means nothing is there."Why it feels right: empty looks like nothing. Fix: ⊔ real, readable symbol . The head can read it, and the rulebook can react to it — that is how a machine knows it walked off the end of the input.
Definition Input alphabetΣ Γ
Σ input alphabet : the symbols your input string is allowed to use. Blank is never in it: ⊔ ∈ / Σ Γ tape alphabet : every symbol that can ever appear on the tape . It always contains the blank and always contains all of Σ ⊔ ∈ Γ Σ ⊆ Γ
The symbol ⊆ Σ ⊆ Γ
Intuition WHY two alphabets and not one?The machine needs scratch symbols — markers like X # Γ Σ Σ
Definition State and the set of statesQ state is the machine's current mood — a label for "what I'm in the middle of doing" (e.g. "hunting for the next 0"). Q finitely many, which is why the control is called finite control .
The head is a pointer — imagine a finger resting on one cell. It can read that cell, overwrite it, and slide one cell left or right. It never jumps more than one cell per step.
Intuition Why only one cell and one step?Simplicity is the whole point. If this bare-bones machine can already compute everything, then fancier abilities (jumping, multiple tapes) add no extra power. We prove that later; for now, small moves keep the model easy to reason about.
Three named states matter specially:
Definition Start, accept, reject
q 0 start state , the mood the machine begins in.q accept yes , I accept this input", and I stop .q reject no , I reject", and I stop .
We require q accept = q reject
Definition Move direction{ L , R } L left ", R right ". Every step moves the head by exactly one of these.
Common mistake "The head can also stay put."Why it feels right: sometimes you'd like to write without moving. Fix: in this standard definition there is no "stay" option — every step moves L R L
Now the biggest symbol. Everything above was nouns; δ verb .
Definition Function and the arrow→ function is a machine-within-the-machine that takes an input and gives back exactly one output. We write f : A → B f A B × A × B A B
Definition Transition functionδ δ : Q × Γ → Q × Γ × { L , R } give δ returns a triple (new state, symbol to write, direction to move). One reading of δ
function and not just any rule?
A function gives exactly one output per input — no ambiguity. Because δ deterministic Turing machine: no choices, no dice. (Machines that do branch are Nondeterministic Turing Machines .)
Mnemonic Remember the seven as one sentence"Q uiet S tudents G et δ etention q₀ uickly, accept ing or reject ing." — states, Σ, Γ, δ, start, accept, reject.
This is the notation that trips people up most, so we earn it slowly.
Intuition Why bundle three things into one word?At any instant, the machine's entire future depends on only three facts: which mood (q on the tape , and where the finger sits . If we pack all three into a single written string, we can describe a whole computation as a list of these snapshots — like movie frames.
u q v insert the state letter q . So:
u left of the head,v from the head onward (head reads the first symbol of v ),the state q
Both u v Γ ∗ v
Worked example Reading a configuration1011 q 7 01111 101101111, the machine is in mood q 7 0 that comes right after 1011. If v q ⊔
⊢ C 1 ⊢ C 2 C 1 yields C 2 δ once to snapshot C 1 C 2
The parent note's yield rules (move-right, move-left, left-edge) are just this one idea spelled out for each direction. You now have every symbol needed to read them.
L language is just a set of strings — the strings we consider "good" / "in". L ( M ) = { w : M accepts w } M
Definition Recognizable vs decidable (in one breath)
Recognizable : some TM accepts every good string. On bad strings it may loop forever — never answering "no". See Recursively Enumerable Languages .Decidable : some TM always halts with a definite yes or no. See Recursive Languages . A machine that always halts is a decider .
The gap between them — looping forever instead of saying "no" — is exactly where the Halting Problem lives.
Two alphabets Sigma and Gamma
Transition function delta
Turing machine topic 4.6.13
Where does this all lead? These same foundations power the whole neighbourhood: Finite Automata and Pushdown Automata are weaker cousins, Multitape Turing Machines and Nondeterministic Turing Machines are equal-power variants, and the Church-Turing Thesis claims this simple picture captures all of computation.
Self-test: cover the right side and answer before revealing.
What does x ∈ S x S
What is a string over an alphabet Γ A finite row of symbols each taken from Γ
What does Γ ∗ The set of all strings (any length, including empty) over Γ
What is the blank symbol ⊔ It marks an empty cell, letting the machine detect the end of real input.
Why are there two alphabets Σ Γ Σ Γ
State the containment relation between them. Σ ⊆ Γ ⊔ ∈ Γ ⊔ ∈ / Σ
What is a "state" in plain words? The machine's current mood — what it's in the middle of doing.
Why must q accept = q reject Otherwise "yes" and "no" would be the same state and answers would be meaningless.
What are the only two head moves? L R
What does δ ( q , a ) = ( r , b , D ) In state q a r b D
Why is δ A function gives exactly one output per input, making the machine deterministic.
In u q v The first symbol of v ⊔ v
What does C 1 ⊢ C 2 C 2 δ C 1
What is a language? A set of strings.
Recognizable vs decidable — the one-word difference? A decider always halts ; a recognizer may loop forever on non-members.
