04
Turing Machines and Computability
Chapter 4 • Advanced
70 min
Turing Machines and Computability
Turing Machines are the most powerful computational model.
Turing Machine (TM)
TM is a 7-tuple: M = (Q, Σ, Γ, δ, q₀, B, F)
- Q: States
- Σ: Input alphabet
- Γ: Tape alphabet (Σ ⊆ Γ)
- δ: Transition function (Q × Γ → Q × Γ × {L, R})
- q₀: Start state
- B: Blank symbol
- F: Accepting states
Components:
- Infinite tape
- Read/write head
- State control
Transition: (q, a) → (q', b, D)
- In state q, read a
- Write b, move direction D, go to state q'
TM Variants
Multi-Tape TM
Multiple tapes:
- More convenient
- Same power as single-tape TM
Non-deterministic TM
Multiple transitions:
- Same power as deterministic TM
Universal TM
Simulates any TM:
- Takes TM description and input
- Executes TM on input
Decidability
Decidable (Recursive):
- Language L is decidable if TM M decides L
- M halts on all inputs
- Accepts if w ∈ L, rejects if w ∉ L
Semi-decidable (Recursively Enumerable):
- Language L is semi-decidable if TM M recognizes L
- M halts and accepts if w ∈ L
- May loop if w ∉ L
Undecidability
Undecidable Problem: No algorithm exists.
Examples:
- Halting Problem: Cannot decide if TM halts on input
- Post Correspondence Problem (PCP): Undecidable
- Rice's Theorem: All non-trivial properties of RE languages are undecidable
Halting Problem
Halting Problem: Given TM M and input w, does M halt on w?
Proof by Contradiction:
- Assume H decides halting problem
- Construct D that contradicts H
- Contradiction → H cannot exist
Result: Halting problem is undecidable.
Reduction
Reduction: Problem A reduces to problem B if:
- Solution to B solves A
- If B is decidable, then A is decidable
- If A is undecidable, then B is undecidable
Use: Prove undecidability by reduction.
GATE CS Important Points
- TM Construction: Build TM for language
- Decidability: Understand decidable vs undecidable
- Halting Problem: Know proof
- Reduction: Use reduction to prove undecidability
- Rice's Theorem: Understand implications
Practice Tips
- Construct TM: Practice for various languages
- Decidability: Identify decidable problems
- Reduction: Practice reduction proofs
- Halting Problem: Understand proof
- Previous Year Questions: Solve GATE TM questions