Turing Machines
Computability, decidability, and the foundations of computation
TM Definition (7-Tuple)
A Turing Machine is defined as M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject)
How TMs Work
A TM has an infinite tape divided into cells, a read/write head positioned over one cell, and a finite control in one of the states. At each step:
- Read the symbol under the head
- Consult the transition function δ(current_state, symbol)
- Write a new symbol to the tape
- Move the head Left or Right
- Transition to a new state
The TM halts when it enters q_accept or q_reject. If it never halts, it loops infinitely.
Church-Turing Thesis
The Church-Turing thesis states that every effectively computable function can be computed by a Turing Machine. “Effectively computable” means computable by some mechanical procedure. All known models of computation (λ-calculus, μ-recursive functions, Post systems, RAM machines, cellular automata) have been proven equivalent to TMs, providing strong evidence for the thesis.
Key Implication:
If a problem cannot be solved by a Turing Machine, it cannot be solved by any computer — ever.
Decidability vs. Undecidability
Decidable Problems
A TM halts with YES/NO on every input. Examples: DFA emptiness, CFG membership, primality testing.
Undecidable Problems
No TM exists that always halts with the correct answer. Examples: Halting Problem, Post's Correspondence Problem, Hilbert's Entscheidungsproblem.
Alan Turing proved the undecidability of the Halting Problem in 1936 using a diagonalization argument, establishing the fundamental limits of computation.
Examples
Add two unary numbers (e.g., 11+111 → 11111)
- Move right to find the + separator
- Replace + with 1
- Move to the end and erase the last 1
State Transition Diagram
A simple TM that recognizes { 0ⁿ1ⁿ | n ≥ 0 }
Limits of Computation
Turing Machines reveal that there are fundamental limits to what computers can do. Some problems are undecidable (no algorithm exists), and among decidable problems, some are intractable (require exponential time). Understanding these limits is crucial for knowing when to seek approximation algorithms or heuristic solutions.
Interview Questions
Q1: What is a Turing Machine and what are its key components?
A Turing Machine (TM) is a 7-tuple (Q, Σ, Γ, δ, q₀, q_accept, q_reject) consisting of a finite set of states Q, an input alphabet Σ, a tape alphabet Γ (including blank), a transition function δ: Q×Γ → Q×Γ×{L,R}, a start state q₀, an accept state q_accept, and a reject state q_reject. The TM has an infinite tape, a read/write head, and a finite control unit. At each step, it reads a symbol, writes a new symbol, moves left or right, and changes state.
Q2: Explain the Church-Turing thesis and its significance.
The Church-Turing thesis states that every effectively computable function can be computed by a Turing Machine. It is a thesis (not a theorem) because 'effectively computable' is an intuitive notion. The thesis is widely accepted because: (1) all reasonable models of computation (lambda calculus, μ-recursive functions, RAM machines) have been proven equivalent to TMs, and (2) no counterexample has been found. It establishes TMs as the standard model for studying computability.
Q3: What is the difference between decidability and undecidability?
A decision problem is decidable if there exists a Turing Machine that halts with YES or NO for every input instance. It is undecidable if no such TM exists. The classic example is the Halting Problem: given a TM M and input w, does M halt on w? Alan Turing proved this is undecidable by a diagonalization argument. Other undecidable problems include Post's Correspondence Problem, the Entscheidungsproblem, and determining whether a CFG is ambiguous.