Recall warm-up
- If L and L̅ are RE, what is L?
Stuck? Peek at 4.3.3 Closure of REC and RE; L and L̅ both RE ⇒ L recursive
- REC closed: ∪ ∩ complement − concat * reversal h⁻¹; not h.
- RE closed: ∪ ∩ concat * reversal h h⁻¹; not complement, not difference.
- L, L̅ ∈ RE ⇒ L ∈ REC. L ∈ RE − REC ⇒ L̅ ∉ RE.
- What is the difference between a decider and a recognizer?
Stuck? Peek at 4.3.1 Recursive vs recursively enumerable; deciders and recognizers
- Recognizer: accepts L, may loop outside. RE = recognizable = semi-decidable = enumerable.
- Decider: halts always. Recursive = decidable.
- REC ⊆ RE. Enumerator ⇔ recognizer (dovetailing). Shortlex enumeration ⇔ recursive.
- What is ⟨X⟩?
Stuck? Peek at 0.3.4 Problems as languages
- Problem P ↔ language L_P = {⟨x⟩ : answer yes}. ⟨X⟩ = string encoding of X.
- Solving P = machine M with: M says yes on w ⇔ w ∈ L_P (membership).
- Always test ε against count conditions.
The Hook
Your laptop runs a web browser, a game, a compiler — one machine, any program. Turing saw this in 1936: a single universal TM can read the description of any TM M plus an input w, and do whatever M would do on w. This makes programs into data — and that is exactly what lets us ask machines questions about other machines, the gateway to Phase 5.
Predict First
A TM is a finite object: finitely many states, symbols and transitions. Can every TM be written as a finite binary string?
Core Concept
Prediction check
Yes. Number the states q₁, q₂, …, the tape symbols X₁, X₂, …, directions D₁ = L, D₂ = R; write each transition δ(qᵢ, Xⱼ) = (qₖ, Xₗ, Dₘ) as 0ⁱ1 0ʲ1 0ᵏ1 0ˡ1 0ᵐ and separate transitions with 11. The whole machine is one binary string ⟨M⟩.
TMs are countable
Every TM has a finite binary code, so TMs can be listed M₁, M₂, M₃, … in shortlex order of their codes (strings that are not valid codes can stand for a fixed trivial machine). There are only as many TMs as there are natural numbers. Phase 5 compares this with how many languages exist.
The universal Turing machine
Implementation: tape 1 holds ⟨M⟩, tape 2 simulates M’s tape, tape 3 holds M’s current state; each step looks up the matching transition in the code. (Multi-tape is fine — 4.2.)
So L(U) = { ⟨M, w⟩ : M accepts w } is RE. Whether it is recursive is the first question of Phase 5.
The Church–Turing thesis
It is a thesis, not a theorem: “effective procedure” is an informal idea. The evidence: every proposed model — λ-calculus, recursive functions, register machines, every programming language — computes exactly the same functions.
Consequence: “there is no algorithm for X” and “no TM decides X” mean the same thing.
Putting it together
- Every TM is a finite string; TMs can be listed M₁, M₂, …
- A universal TM runs any encoded TM on any input.
- Church–Turing: TM = algorithm, so “no TM” means “no algorithm”.
Visual
⟨M, w⟩ ──► [ U ] ──► accept if M accepts w
reject if M rejects w
loop if M loops on w
L(U) = { ⟨M,w⟩ : M accepts w } — RE (U recognizes it)Worked Examples
Is the set of all TMs finite, countably infinite, or larger?
Show the full solution
Countably infinite: each TM has a finite binary code.
Is the Church–Turing thesis a theorem?
Show the full solution
No — it relates a mathematical notion (TMs) to an informal one (algorithms); it cannot be proved, only supported by evidence.
Which are true? (i) A universal TM exists. (ii) The universal TM halts on every input. (iii) { ⟨M, w⟩ : M accepts w } is RE. (iv) The Church–Turing thesis implies a quantum computer can solve problems no TM can.
Show the full solution
(i) true. (ii) false — it loops when the simulated M loops. (iii) true. (iv) false — the thesis says the opposite about computability (speed is another matter). Answer: (i) and (iii).
GATE Traps
- The universal TM is a recognizer for { ⟨M, w⟩ : M accepts w }, not a decider.
- Church–Turing is a thesis (a hypothesis about the informal notion of algorithm).
- Programs are data: questions “about TMs” are questions about strings ⟨M⟩.
Memory Hook
The universal TM is the clerk who is handed another clerk’s rulebook and follows it to the letter — including getting stuck forever when that clerk would.
Connect the Dots
Phase 4 complete. We have the most powerful machine model and a machine that runs every other machine. Phase 5 asks the question Turing asked: are there problems no TM can decide? You will prove there are — starting from a counting argument and a diagonal trick.
Self-Test
- MCQ
The universal TM U on ⟨M, w⟩:
- always halts
- accepts iff M accepts w
- decides whether M halts
- rejects if M loops
- MSQ
Which are true?
- Every TM can be encoded as a binary string
- The set of TMs is countable
- Church–Turing thesis is a proven theorem
- { ⟨M,w⟩ : M accepts w } is RE
- MCQ
Church–Turing thesis states:
- TMs are faster than any computer
- every effectively computable function is TM-computable
- every language is decidable
- P = NP
Rule Card
- ⟨M⟩: binary code of transitions (0ⁱ1 0ʲ1 0ᵏ1 0ˡ1 0ᵐ, separated by 11). TMs are countable.
- Universal TM U: simulates M on w; L(U) = {⟨M,w⟩ : M accepts w} is RE.
- Church–Turing thesis: algorithm ⇔ TM (thesis, not theorem).
Concept Ledger
- encoding of a TM ⟨M⟩
- countably many TMs
- universal Turing machine U
- Church–Turing thesis
Answer Vault
Reveal answers when you’re ready
Warm-up answers
- Recursive.
- A decider halts on every input; a recognizer may loop on non-members.
- A string encoding of the object X.
Self-test answers
- B — It simulates M.
- A: It loops if M loops.
- C: That is impossible (Phase 5).
- D: It cannot detect looping.
- ABD — Encoding and UTM facts.
- C: It is a thesis.
- B — Definition.
- A: About speed — no.
- C: False.
- D: Unrelated.
Flashcards
- What does the universal TM do?
Reveal answer
Given ⟨M, w⟩ it simulates M on w. - Is the set of TMs countable?
Reveal answer
Yes — each has a finite binary code. - Is the Church–Turing thesis a theorem?
Reveal answer
No, a thesis.