Unit V: Turing Machines & Recursive Function Theory

Complete Exam Preparation – 100% Coverage with Examples & Proof Ideas

1. Turing Machine – Formal Definition (7-tuple)

M = (Q, Σ, Γ, δ, q₀, B, F)

Q → finite set of states
Σ → input alphabet (does not contain B)
Γ → tape alphabet (Σ ⊆ Γ, contains B = blank)
δ: Q × Γ → Q × Γ × {L, R} → transition function
q₀ → start state
B → blank symbol
F ⊆ Q → accepting (final) states

2. Instantaneous Description (ID)

Represented as: X₁X₂…Xᵢ₋₁ q Xᵢ Xᵢ₊₁…Xₙ
q is current state, head is on Xᵢ

3. Language Accepted by TM

Acceptance by Final State: Enter any state in F
Acceptance by Halting: Reach a state where δ is undefined

Both definitions are equivalent in power → recognize Recursively Enumerable (RE) languages

4. Techniques for TM Construction (Most Asked)

TM for { aⁿ bⁿ cⁿ | n ≥ 0 }
1. Match first a with first b → replace with X,Y
2. Go back, match remaining a with next b
3. Repeat until all matched
4. Then match remaining b with c
→ Requires multiple passes → only TM can do this!

TM for { ww | w ∈ {a,b}* } (copying)
1. Remember first symbol
2. Mark it, go to end
3. Write same symbol at end
4. Repeat until blank
→ Classic 10–12 marks question

5. Variants of Turing Machines (All Equally Powerful)

Variant	Power
Multi-tape TM	Same as single tape
Non-deterministic TM	Same as deterministic
TM with stay-put (no move)	Same
Two-way infinite tape	Same
Multi-dimensional tape	Same

6. Turing Machine as Computer of Functions

TM can compute any partial recursive function
Input: number n in unary → Output: f(n)

7. Universal Turing Machine (UTM)

There exists a TM U such that:
Given encoding ⟨M⟩ of any TM M and input w,
U simulates M on w and behaves exactly like M

UTM = Stored-program computer → Foundation of modern computers

8. Linear Bounded Automata (LBA)

TM with tape restricted to input length + end markers

L(LBA) = Context-Sensitive Languages (Type-1)

9. Church-Turing Thesis (Most Important Statement)

Church-Turing Thesis:
Any function that can be computed by an algorithm can be computed by a Turing Machine.

Not provable, but universally accepted

10. Recursive and Recursively Enumerable Languages

Type	Accepted By	Decidable?
Recursive (R)	TM that always halts	Yes (always Yes/No answer)
Recursively Enumerable (RE)	General TM	May loop on No

R ⊂ RE (proper subset)

11. The Halting Problem (Undecidability)

HALT = { ⟨M, w⟩ | TM M halts on input w } is undecidable

Proof by contradiction (diagonalization):
Assume H exists → construct H' that does opposite → paradox

12. Post’s Correspondence Problem (PCP)

PCP is undecidable → used to prove many problems undecidable

Instance: Two lists A = [a₁,…,aₙ], B = [b₁,…,bₙ]
Question: Is there sequence i₁…iₖ such that aᵢ₁…aᵢₖ = bᵢ₁…bᵢₖ ?

13. Introduction to Recursive Function Theory

Primitive Recursive Functions: zero, successor, projection, composition, primitive recursion
μ-recursive Functions: add unbounded minimization → total Turing computable
Ackermann function → grows faster than primitive recursive

14. Summary Table (Quick Revision)

Machine	Language Class	Decidable?
DFA	Regular	Yes
PDA	Context-Free	Membership yes, others mostly no
LBA	Context-Sensitive	—
TM (halting)	Recursive	Yes
TM (general)	Recursively Enumerable	May loop

Most Important Exam Questions – Unit V (15–20 Marks Guaranteed)

Design TM for {aⁿbⁿcⁿ}, {ww}, palindrome, addition, etc. (12–15 marks)
Prove Halting Problem is undecidable (full proof)
Explain Universal TM with diagram
Prove PCP is undecidable (outline)
Difference between Recursive and RE languages
Show that if L and L̅ both RE → L is recursive
Church-Turing Thesis and its significance
Prove equivalence of multi-tape and single-tape TM

Quick One-Liners for Last Minute

TM = Most powerful model
Halting Problem = First undecidable problem
UTM = Theoretical computer
Two stacks = TM power
Recursive = always halts
RE = may loop on rejection
Church-Turing = Algorithm = TM-computable