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

  1. TM Construction: Build TM for language
  2. Decidability: Understand decidable vs undecidable
  3. Halting Problem: Know proof
  4. Reduction: Use reduction to prove undecidability
  5. Rice's Theorem: Understand implications

Practice Tips

  1. Construct TM: Practice for various languages
  2. Decidability: Identify decidable problems
  3. Reduction: Practice reduction proofs
  4. Halting Problem: Understand proof
  5. Previous Year Questions: Solve GATE TM questions