Intuition The big picture (WHY do we even need this?)Finite automata can't even check { a n b n } \{a^n b^n\} { a n b n } stack . We want a model that captures everything a real computer can compute — no memory limits, no clever tricks left out. A Turing machine is the simplest such model: an infinite tape of cells, a head that reads/writes one cell, and a tiny finite control that decides what to do next. It feels almost stupidly simple — and that's the point. The Church–Turing thesis says this simple thing is as powerful as anything .
Definition Turing machine (7-tuple)A (deterministic) Turing machine is M = ( Q , Σ , Γ , δ , q 0 , q accept , q reject ) M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}}) M = ( Q , Σ , Γ , δ , q 0 , q accept , q reject )
Q Q Q states Σ \Sigma Σ not containing the blank symbol ⊔ \sqcup ⊔ Γ \Gamma Γ ⊔ ∈ Γ \sqcup \in \Gamma ⊔ ∈ Γ Σ ⊆ Γ \Sigma \subseteq \Gamma Σ ⊆ Γ δ : Q × Γ → Q × Γ × { L , R } \delta : Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\} δ : Q × Γ → Q × Γ × { L , R } transition function q 0 ∈ Q q_0 \in Q q 0 ∈ Q q accept , q reject ∈ Q q_{\text{accept}}, q_{\text{reject}} \in Q q accept , q reject ∈ Q halting states , with q accept ≠ q reject q_{\text{accept}} \neq q_{\text{reject}} q accept = q reject
WHAT each piece does:
δ ( q , a ) = ( r , b , D ) \delta(q, a) = (r, b, D) δ ( q , a ) = ( r , b , D ) q q q a a a r r r overwrite the cell with b b b one cell in direction D D D L L L R R R
Intuition WHY a 7-tuple and not less?
We split Σ \Sigma Σ Γ \Gamma Γ extra working symbols (markers like X X X # \# #
We need ⊔ \sqcup ⊔
Two halting states (accept/reject) let the machine stop immediately the moment it decides, unlike DFAs which read the whole string.
Intuition WHY configurations?At any moment the entire future of the machine is determined by three things: the current state , the tape contents , and the head position . Bundle these into one object and you can talk about computation as a sequence of snapshots — like frames of a movie.
A configuration is written u q v u\,q\,v u q v
q ∈ Q q \in Q q ∈ Q u ∈ Γ ∗ u \in \Gamma^* u ∈ Γ ∗ left of the head,v ∈ Γ ∗ v \in \Gamma^* v ∈ Γ ∗ starting at the head (so the head points at the first symbol of v v v ).
Everything beyond v v v 1011 q 7 01111 1011\,q_7\,01111 1011 q 7 01111 101101111, state q 7 q_7 q 7 0 after 1011.
Definition Special configurations
Start configuration on input w w w q 0 w \;q_0\,w q 0 w q 0 q_0 q 0 Accepting configuration : state is q accept q_{\text{accept}} q accept Rejecting configuration : state is q reject q_{\text{reject}} q reject Halting configurations : the accepting and rejecting ones (no further moves).
Intuition WHAT does "yields" mean? (HOW computation steps)One configuration C 1 C_1 C 1 yields C 2 C_2 C 2 C 1 ⊢ C 2 C_1 \vdash C_2 C 1 ⊢ C 2 C 2 C_2 C 2 δ \delta δ tape edges and when overwriting under the head.
Suppose δ ( q , b ) = ( r , c , D ) \delta(q, b) = (r, c, D) δ ( q , b ) = ( r , c , D ) b b b a a a u u u v v v
M M M w w w C 0 ⊢ C 1 ⊢ C 2 ⊢ ⋯ C_0 \vdash C_1 \vdash C_2 \vdash \cdots C 0 ⊢ C 1 ⊢ C 2 ⊢ ⋯ C 0 = q 0 w C_0 = q_0 w C 0 = q 0 w C i + 1 C_{i+1} C i + 1 C i C_i C i until it reaches a halting configuration (or runs forever).
M M M accepts w w w C i C_i C i M M M rejects w w w C i C_i C i Otherwise M M M loops (never halts).
Definition Recognizable vs decidable
L ( M ) = { w : M accepts w } L(M) = \{ w : M \text{ accepts } w \} L ( M ) = { w : M accepts w } recognized by M M M A language is Turing-recognizable (a.k.a. recursively enumerable ) if some TM recognizes it. (On non-members, M M M
A language is Turing-decidable (recursive ) if some TM recognizes it and halts on every input (never loops). A TM that always halts is a decider .
Intuition The crucial asymmetry"Recognize" only promises a yes eventually for members. "Decide" promises a definite yes or no for every input. Looping forever is the gap between them — and that gap is the heart of undecidability (e.g. the Halting Problem).
Worked example Example A — TM forA = { 0 2 n : n ≥ 0 } A = \{0^{2^n} : n \ge 0\} A = { 0 2 n : n ≥ 0 } Idea: repeatedly cross off every other 0. Each pass halves the count. You accept iff every pass leaves an even count until a single 0 remains.
Sketch of δ \delta δ
Sweep right, cross out every other 0 (replace with X X X
Why this step? Halving the number of 0s; a power of two stays a power of two after halving.
If in one pass you saw exactly one 0 → accept . Why? 2 0 = 1 2^0 = 1 2 0 = 1
If you ever see an odd count > 1 >1 > 1 reject . Why? an odd number > 1 >1 > 1
Otherwise rewind head to the left end and repeat.
Trace on input 0000 (4 = 2 2 2^2 2 2
q 0 0000 q_0\,0000 q 0 0000 0X0X, count of 0s = 2 (even, > 1 >1 > 1 Pass 2: 0X0X → cross to 0XXX, count = 1 → accept . ✓
Worked example Example B — tracing yields step by stepTiny machine: δ ( q 0 , 0 ) = ( q 0 , 0 , R ) \delta(q_0, 0) = (q_0, 0, R) δ ( q 0 , 0 ) = ( q 0 , 0 , R ) δ ( q 0 , ⊔ ) = ( q accept , ⊔ , R ) \delta(q_0, \sqcup) = (q_{\text{accept}}, \sqcup, R) δ ( q 0 , ⊔ ) = ( q accept , ⊔ , R )
Input 00:
q 0 00 ⊢ 0 q 0 0 ⊢ 00 q 0 ⊢ 00 q accept q_0 00 \;\vdash\; 0\,q_0\,0 \;\vdash\; 00\,q_0 \;\vdash\; 00\,q_{\text{accept}} q 0 00 ⊢ 0 q 0 0 ⊢ 00 q 0 ⊢ 00 q accept
Step 1 Why? read 0, δ = ( q 0 , 0 , R ) \delta=(q_0,0,R) δ = ( q 0 , 0 , R ) 0 back, move right → 0 joins left part.Step 2 Why? same rule, head over second 0.Step 3 Why? head reads blank (empty right part), δ ( q 0 , ⊔ ) \delta(q_0,\sqcup) δ ( q 0 , ⊔ )
Worked example Example C — counting configuration sizeTape content 1#0, state q 3 q_3 q 3 #. Configuration = 1 q 3 # 0 = 1\,q_3\,\#0 = 1 q 3 #0 δ ( q 3 , # ) = ( q 5 , Y , L ) \delta(q_3,\#)=(q_5, Y, L) δ ( q 3 , # ) = ( q 5 , Y , L ) 1 q 3 # 0 ⊢ q 5 1 Y 0 1\,q_3\,\#0 \;\vdash\; q_5\,1\,Y\,0 1 q 3 #0 ⊢ q 5 1 Y 0
Why? wrote Y over #, stepped left onto 1, so 1 is new head symbol, Y0 follows. Now head is at the left edge — a future L L L
Common mistake "The head writesthen moves, so it can't write and move in one step."
Why it feels right: real CPUs do many micro-ops. Fix: one TM step does both — overwrite the current cell and move exactly one cell. It is a single atomic transition defined by one application of δ \delta δ
Common mistake "Recognizable = decidable."Why it feels right: if a TM can say "yes", surely it can say "no". Fix: for a recognizer , non-members may cause an infinite loop — it never says "no". Deciders are the strictly stronger class that always halt.
Common mistake "Moving left off the edge crashes the machine."Why it feels right: arrays throw out-of-bounds errors. Fix: by convention the head simply stays at cell 0 ; the computation continues normally.
Common mistake "Input alphabet and tape alphabet are the same."Why it feels right: the input lives on the tape. Fix: Σ ⊊ Γ \Sigma \subsetneq \Gamma Σ ⊊ Γ ⊔ \sqcup ⊔ ⊔ \sqcup ⊔ never in Σ \Sigma Σ
δ \delta δ Why it feels right: functions usually are total. Fix: δ \delta δ ( Q ∖ { q accept , q reject } ) × Γ (Q \setminus \{q_{\text{accept}}, q_{\text{reject}}\}) \times \Gamma ( Q ∖ { q accept , q reject }) × Γ no transitions out of halting states (they stop).
Recall Feynman: explain to a 12-year-oldImagine an endless strip of paper divided into boxes, and a little robot sitting on one box. The robot has a tiny notebook with a few "moods" (states). It looks at the letter in its box, then its rulebook says: "erase it, write this new letter, and shuffle one box left or right, and switch to that mood." It keeps doing this. Two special moods mean STOP-YES and STOP-NO . If it never reaches a STOP mood, it just keeps shuffling forever. That's a Turing machine — and amazingly, this dumb robot can compute anything any computer can.
Mnemonic Remember the 7-tuple as"Q-SAT-D-q₀-AR"
Q states, S igma (input), A lphabet-tape Γ, T ransition δ — then q₀ start, A ccept, R eject. Say it: "Cue-SAT-Delta, q-zero, Accept-Reject."
Recall Active recall checkpointCover the note. Can you (1) write the 7-tuple, (2) state the three yield rules, (3) define recognizable vs decidable, (4) trace q_0 00 for Example B?
What are the 7 components of a Turing machine? ( Q , Σ , Γ , δ , q 0 , q accept , q reject ) (Q,\Sigma,\Gamma,\delta,q_0,q_{\text{accept}},q_{\text{reject}}) ( Q , Σ , Γ , δ , q 0 , q accept , q reject ) — states, input alphabet, tape alphabet, transition function, start state, accept and reject states.
What is the type signature of the transition function δ \delta δ δ : Q × Γ → Q × Γ × { L , R } \delta: Q\times\Gamma \to Q\times\Gamma\times\{L,R\} δ : Q × Γ → Q × Γ × { L , R } .
Why must Σ ⊆ Γ \Sigma \subseteq \Gamma Σ ⊆ Γ ⊔ ∉ Σ \sqcup \notin \Sigma ⊔ ∈ / Σ Input lives on the tape (so
Σ ⊆ Γ \Sigma\subseteq\Gamma Σ ⊆ Γ ), but the blank marks "no input here" so it must never appear in the input itself.
What is a configuration u q v u\,q\,v u q v A snapshot: state
q q q , tape content
u u u left of the head, content
v v v starting at the head (head on first symbol of
v v v ), blanks beyond.
Yield rule for moving right: u a q b v ⊢ u a q b v \vdash u a q b v ⊢ δ ( q , b ) = ( r , c , R ) \delta(q,b)=(r,c,R) δ ( q , b ) = ( r , c , R ) u a c r v u a c r v u a cr v — write
c c c , head steps right so
c c c joins the left part.
Yield rule for moving left: u a q b v ⊢ u a q b v \vdash u a q b v ⊢ δ ( q , b ) = ( r , c , L ) \delta(q,b)=(r,c,L) δ ( q , b ) = ( r , c , L ) u r a c v u r a c v u r a c v — write
c c c , head steps left onto
a a a .
What happens when the head tries to move left off cell 0? It stays at cell 0 (left-edge convention); computation continues.
Difference between Turing-recognizable and Turing-decidable? Recognizable: some TM accepts members (may loop on non-members). Decidable: a TM that always halts gives yes/no for every input.
What is a decider? A TM that halts on every input (never loops).
What are the three outcomes of a TM running on input w w w Accept, reject, or loop forever (never halt).
Why are there exactly two halting states? So the machine can decide "yes" or "no" and stop immediately, without reading the whole input.
On which domain is δ \delta δ ( Q ∖ { q accept , q reject } ) × Γ (Q\setminus\{q_{\text{accept}},q_{\text{reject}}\})\times\Gamma ( Q ∖ { q accept , q reject }) × Γ — halting states have no outgoing transitions.
Finite Automata — TMs add a writable, infinite, two-way tape (FAs are read-only, one-way).Pushdown Automata — PDAs have a stack; TMs generalize to full random-ish access via head movement.Church-Turing Thesis — claims TMs capture all effective computation.Halting Problem — the canonical undecidable language; lives in the recognizable-but-not-decidable gap.Recursively Enumerable Languages / Recursive Languages — the language classes defined here.Nondeterministic Turing Machines — same power, possibly faster; defined via a yield relation not function.Multitape Turing Machines — equivalent in power, used for cleaner constructions.
reads writes moves L or R
extra work symbols and blank fill tape
Need model for all computation
Transition function delta
Sigma vs Gamma with blank
State plus tape plus head
Intuition Hinglish mein samjhoDekho, Turing machine basically ek bahut hi simple "robot" hai jo ek infinite tape (kagaz ki endless patti, boxes mein divided) par baitha hai. Uske paas ek head hota hai jo ek box ko padh sakta hai aur usme likh bhi sakta hai. Robot ke paas thode se states (moods) hain, aur ek rulebook jise hum δ \delta δ ( Q , Σ , Γ , δ , q 0 , q a c c e p t , q r e j e c t ) (Q,\Sigma,\Gamma,\delta,q_0,q_{accept},q_{reject}) ( Q , Σ , Γ , δ , q 0 , q a cce pt , q r e j ec t )
Ab "configuration" ka matlab hai ek snapshot — yaani us moment pe machine ki poori state: kaunsa state, tape pe kya likha hai, aur head kahan hai. Hum isse u q v u\,q\,v u q v u u u v v v δ \delta δ C 1 ⊢ C 2 C_1 \vdash C_2 C 1 ⊢ C 2
Sabse zaroori cheez yaad rakho: machine ke 3 anjaam ho sakte hain — accept, reject, ya loop (hamesha chalti rahe). Yahin se "recognizable" aur "decidable" ka farak aata hai. Agar TM members ko accept kar leti hai par non-members pe shaayad loop kar jaaye, toh language recognizable hai. Agar TM har input pe rukti hai (halt karti hai) aur saaf yes/no deti hai, toh wo decidable hai aur use decider bolte hain. Yeh loop wala gap hi aage chalke Halting Problem jaisi undecidable cheezon ki jadd hai — isiliye yeh chhota sa model itna important hai.
