Where you are in the story
Phase 5 asks what Turing machines cannot do. Every proof uses three Phase 4 facts: TMs can be encoded as strings, a universal TM can run any encoded machine, and the difference between deciding and recognizing.
Previous phase in pictures
Decider vs recognizer
decider
halts on every input
recognizer
accepts members; may loop on non-members
The chain
RE TM
REC decider
CSL LBA
CFL PDA
Regular DFA
Programs are data
TM M
⟨M⟩
a binary string
U(⟨M, w⟩)
runs M on w
Two half-answers make a whole
L is RE
and
L̅ is RE
⇒
L is recursive
Carry these forward
TM transition type?
δ : Q × Γ → Q × Γ × {L, R}. (4.1.1)
Is an NTM more powerful than a DTM?
No. (4.2)
What does an LBA accept?
Exactly the CSLs. (4.2)
Recursive vs RE?
Decider exists vs recognizer exists. (4.3.1)
Full chain?
Regular ⊂ DCFL ⊂ CFL ⊂ CSL ⊂ REC ⊂ RE. (4.3.2)
L and L̅ both RE ⇒ ?
L is recursive. (4.3.3)
Is RE closed under complement?
No. (4.3.3)
Are TMs countable?
Yes — each has a finite code. (4.4)
What does the universal TM do on ⟨M, w⟩?
Simulates M on w (loops if M loops). (4.4)
Church–Turing thesis?
Algorithm = TM (a thesis). (4.4)
Quick refresher
- MCQ
L is RE but not recursive. L̅ is:
- recursive
- RE
- not RE
- regular
- MSQ
Which are recursive?
- every CFL
- every CSL
- every RE language
- every regular language
- MCQ
The universal TM is:
- a decider for {⟨M,w⟩ : M accepts w}
- a recognizer for {⟨M,w⟩ : M accepts w}
- an LBA
- a PDA
What the next phase adds
count machines vs languages
5.1
diagonal language, halting problem
5.2
reductions
5.3
Rice’s theorem
5.4
the master table
5.5
Answer Vault
Reveal answers when you’re ready
- C — Complement theorem.
- A: Then L recursive.
- B: Then L recursive.
- D: No.
- ABD — REC ⊊ RE.
- C: Not all.
- B — It may loop.
- A: It loops when M loops.
- C: No.
- D: No.