Unit IV - Turing Machines
The Most Powerful Computational Model - Turing Machines, Church's Thesis, and Computability
1. Introduction to Turing Machines
A Turing Machine (TM) is the most powerful computational model in theoretical computer science. Proposed by Alan Turing in 1936, it defines the limits of what can be computed.
Why Turing Machines?
Previous models have limitations:
- Finite Automata: Only finite memory (current state)
- Pushdown Automata: Stack (LIFO) - can't access middle
- Turing Machine: Infinite tape - read/write anywhere!
Key Features of Turing Machine:
- Infinite Tape: Unbounded memory (extends infinitely in one or both directions)
- Read/Write Head: Can read and write symbols on tape
- Movement: Can move left (L), right (R), or stay (S)
- States: Finite control like FA/PDA
- Halting: May halt (accept/reject) or run forever
Historical Significance:
- 1936: Alan Turing proposed TM to solve Entscheidungsproblem (decision problem)
- Defined notion of "algorithm" and "computable function"
- Showed some problems are undecidable (no algorithm exists)
- Foundation of computer science and computability theory
Church-Turing Thesis:
Any function that can be computed by an algorithm can be computed by a Turing Machine.
This defines the boundary between computable and non-computable.
2. Turing Machine Model and Representation
Formal Definition:
A Turing Machine is a 7-tuple M = (Q, Σ, Γ, δ, q₀, B, F) where:
- Q: Finite set of states
- Σ: Input alphabet (symbols on input tape)
- Γ: Tape alphabet (Σ ⊂ Γ, includes blank symbol B)
- δ: Q × Γ → Q × Γ × {L, R}: Transition function
- Given state q and tape symbol X
- Go to state p, write Y, move direction D
- q₀ ∈ Q: Start state
- B ∈ Γ: Blank symbol (not in Σ)
- F ⊆ Q: Final (accepting) states
Components of Turing Machine:
- Tape:
- Infinite in both directions (or one direction)
- Divided into cells, each holding one symbol from Γ
- Initially contains input string, rest is blank (B)
- Read/Write Head:
- Points to one cell at a time
- Can read and write symbol
- Can move left or right
- Finite Control:
- Maintains current state
- Controls behavior based on transition function
Representation Methods:
1. Transition Table:
Example: TM for L = {0ⁿ1ⁿ | n ≥ 1}
| Current State | Read Symbol | Next State | Write Symbol | Move |
|---|---|---|---|---|
| q₀ | 0 | q₁ | X | R |
| q₁ | 0 | q₁ | 0 | R |
| q₁ | Y | q₁ | Y | R |
| q₁ | 1 | q₂ | Y | L |
| q₂ | Y | q₂ | Y | L |
| q₂ | 0 | q₂ | 0 | L |
| q₂ | X | q₀ | X | R |
| q₀ | Y | q₃ | Y | R |
| q₃ | Y | q₃ | Y | R |
| q₃ | B | q₄ | B | R |
Strategy: Mark 0 with X, find matching 1 and mark with Y, repeat. Accept if all matched.
2. Transition Diagram:
Graphical representation where:
- States are circles
- Transitions are arrows labeled: read/write, direction
- Start state has incoming arrow
- Final states are double circles
3. Instantaneous Description (ID):
Notation: α₁qα₂ represents:
- q: Current state
- α₁: Tape content to the left of head
- α₂: Tape content from head to the right (head on first symbol)
Example: X0011q₁Y means state q₁, head on Y, tape has X0011Y...
Move Notation:
⊢ denotes one move: α₁qα₂ ⊢ β₁pβ₂
⊢* denotes zero or more moves
Determinism:
Standard TM is deterministic: δ is a function (one choice per configuration)
Nondeterministic TM (NTM) allows multiple choices, but TM = NTM in power!
3. Languages Acceptability of Turing Machines
A language is Turing-recognizable (or recursively enumerable) if some TM accepts it. A language is Turing-decidable (or recursive) if some TM accepts it AND halts on all inputs.
Three Outcomes for TM on Input w:
- Accept: TM enters accepting state and halts
- Reject: TM enters rejecting state and halts (or halts in non-accepting state)
- Loop: TM runs forever (never halts)
Language Classes:
Recursive Language (Decidable):
- L is recursive if ∃ TM M that:
- Accepts every w ∈ L (halts in accept state)
- Rejects every w ∉ L (halts in reject state)
- M halts on ALL inputs
Recursively Enumerable Language (Recognizable):
- L is RE if ∃ TM M that:
- Accepts every w ∈ L (halts in accept state)
- For w ∉ L, M either rejects OR loops forever
- M may not halt on inputs not in L
Relationship between Language Classes:
Regular ⊂ Context-Free ⊂ Recursive ⊂ RE ⊂ All Languages
DFA PDA that TM that TM that (includes
always always may not undecidable)
halts halts halt
Examples:
| Language | Class | Reason |
|---|---|---|
| L = {0ⁿ1ⁿ | n ≥ 0} | Recursive (Decidable) | TM can check and always halt |
| L = {⟨M⟩ | M is TM that accepts ε} | RE but not Recursive | Can accept if yes, but may loop if no |
| Halting Problem | RE but not Recursive | Undecidable - no TM decides it |
| L = {⟨M⟩ | M never halts on any input} | Not RE | Complement of RE language |
Properties:
- Every Recursive language is RE (but not vice versa)
- Recursive languages are closed under: union, intersection, complement, concatenation, star
- RE languages are closed under: union, intersection, concatenation, star
- RE languages are NOT closed under complement!
Key Theorem:
A language L is recursive if and only if both L and L̄ (complement) are RE.
Proof idea: Run two TMs in parallel - one for L, one for L̄. Exactly one will accept.
4. Church's Hypothesis (Church-Turing Thesis)
The Church-Turing Thesis is a fundamental hypothesis about the nature of computation. It connects informal notion of "algorithm" with formal model of "Turing Machine".
Statement:
"Every function that would naturally be regarded as computable can be computed by a Turing Machine."
Or equivalently:
"The class of functions computable by a Turing Machine is exactly the class of functions that can be computed by any reasonable model of computation."
Historical Context:
- 1930s: Multiple mathematicians proposed models of computation:
- Alan Turing (1936): Turing Machines
- Alonzo Church (1936): Lambda Calculus
- Emil Post: Post Systems
- Kurt Gödel: Recursive Functions
- All models turned out to be equivalent in power!
- This led to the Church-Turing Thesis
Why is it a "Thesis" not a "Theorem"?
- Cannot be proved mathematically
- "Algorithm" is an informal, intuitive concept
- Cannot formally prove informal concept = formal model
- Strong Evidence:
- Every proposed computational model is equivalent to TM
- No one has found stronger model (that's practical)
- 70+ years of computer science supports it
- Universally Accepted: Foundation of computability theory
Equivalent Models of Computation:
| Model | Proposed By | Equivalent to TM? |
|---|---|---|
| Turing Machine | Alan Turing | ✓ (by definition) |
| Lambda Calculus | Alonzo Church | ✓ Yes |
| Recursive Functions | Gödel, Kleene | ✓ Yes |
| RAM (Random Access Machine) | Modern computers | ✓ Yes |
| Multi-tape TM | Extension of TM | ✓ Yes |
| Nondeterministic TM | Extension of TM | ✓ Yes |
| C/Java/Python programs | Modern languages | ✓ Yes |
Implications of Church-Turing Thesis:
- Turing Machine = Most Powerful:
- TM can compute anything that's computable
- No more powerful practical model exists
- Undecidability is Fundamental:
- Problems TM can't solve are inherently unsolvable
- No algorithm exists (not just "we haven't found it yet")
- Algorithm Definition:
- Can use "algorithm" and "Turing Machine" interchangeably
- Provides rigorous foundation for computability
Quantum Computing and Church-Turing:
Question: Do quantum computers violate Church-Turing thesis?
Answer: No! Quantum computers can solve same problems as TM.
- May be faster (polynomial vs exponential)
- But don't increase the SET of computable problems
- Extended thesis: "Quantum TM" = standard TM in power
Practical Use:
When proving something is "uncomputable", we show:
- No Turing Machine can solve it
- By Church-Turing thesis → No algorithm exists
- Therefore: Fundamentally impossible to compute
Example: Halting Problem is undecidable → No program can detect infinite loops in ALL cases
5. Composite and Iterated Turing Machines
Complex Turing Machines can be built from simpler ones using composition and iteration. This allows modular design and easier proofs.
A. Composite Turing Machines
Build complex TMs by combining simpler TMs in sequence or parallel.
1. Sequential Composition (M₁ • M₂):
Definition: Run M₁ first, then M₂ on resulting tape.
- If M₁ accepts, M₂ starts on M₁'s output tape
- If M₁ rejects, whole machine rejects
- Final result is M₂'s decision
Example: Recognize L = {0ⁿ1ⁿ2ⁿ | n ≥ 0}
- M₁: Convert 0ⁿ1ⁿ to 1ⁿ (check and remove matching 0's and 1's)
- M₂: Check if remaining tape is 1ⁿ2ⁿ
- Combined: M₁ • M₂ recognizes L
2. Parallel Composition (M₁ ∧ M₂):
AND: Accept if both M₁ AND M₂ accept
- Copy input tape
- Run M₁ on first copy, M₂ on second copy
- Accept only if both accept
OR (M₁ ∨ M₂): Accept if M₁ OR M₂ accepts
- Run both in parallel (dovetailing for decidability)
- Accept if either accepts
NOT (¬M): Accept if M rejects (only for decidable L)
- Run M on input
- Swap accept/reject states
- ⚠️ Only works if M always halts!
B. Iterated Turing Machines
Repeat a Turing Machine operation multiple times (like a loop in programming).
Examples of Iteration:
- Bounded Iteration:
- Repeat M exactly n times
- Example: Shift tape right n times
- Conditional Iteration (While Loop):
- Repeat M while condition holds
- Example: While tape has symbol X, do M
- For-Each Iteration:
- Apply M to each symbol on tape
- Example: Replace each 'a' with 'b'
Building Blocks for Complex TMs:
| Component | Function | Use |
|---|---|---|
| Copy | Duplicate input | Run multiple TMs on same input |
| Shift | Move tape contents left/right | Make space for writing |
| Compare | Check if two strings equal | Verify patterns |
| Erase | Clear portion of tape | Cleanup intermediate results |
| Find | Locate symbol on tape | Navigate tape |
Multi-Tape Turing Machines:
TM with k tapes (each with own read/write head)
- More efficient: Can do in O(n) what single-tape does in O(n²)
- Same power: Can simulate k-tape TM with 1-tape TM
- Easier to design: More intuitive for complex tasks
Theorem:
Every k-tape Turing Machine can be simulated by a single-tape Turing Machine.
Proof: Use multiple tracks on single tape to simulate k tapes.
6. Turing Machine as Enumerators
An enumerator is a Turing Machine that generates (outputs) all strings in a language, one by one. It's a different way to define language recognition.
Definition:
An enumerator is a TM with:- Normal TM components
Behavior:
- Starts with blank tape
- Performs computation
- Periodically prints strings to output
- May run forever, printing infinitely many strings
Language Enumerated by E:
L(E) = {w | E eventually prints w}
The set of all strings that E outputs (possibly with repetitions, in any order)
Example 1: Enumerator for L = {0ⁿ1ⁿ | n ≥ 0}
Algorithm:
for n = 0, 1, 2, 3, ... :
print 0ⁿ1ⁿ
Output: ε, 01, 0011, 000111, 00001111, ...
Example 2: Enumerator for {ww | w ∈ {0,1}*}
Algorithm:
for each string w in {0,1}* in lexicographic order:
print ww
Output: εε (empty), 00, 11, 0000, 0101, 1010, 1111, ...
Equivalence Theorem:
A language is Recursively Enumerable if and only if some enumerator enumerates it.
Proof (both directions):
1. Enumerator → TM (Recognizer):
Given enumerator E for L, build TM M that recognizes L:
- On input w, run E
- Every time E prints a string s:
- Compare s with w
- If s = w, accept
- If w ∈ L, E will eventually print it → M accepts
- If w ∉ L, M runs forever (doesn't halt)
2. TM (Recognizer) → Enumerator:
Given TM M that recognizes L, build enumerator E for L:
- Let s₁, s₂, s₃, ... be enumeration of all strings in Σ*
- For i = 1, 2, 3, ...:
- For j = 1 to i:
- Run M on sⱼ for i steps
- If M accepts sⱼ within i steps, print sⱼ
- This ensures every accepted string is eventually printed
- Uses dovetailing to avoid getting stuck on one input
Properties of Enumerators:
| Type | Property | Language Class |
|---|---|---|
| General Enumerator | May print strings in any order, with repetitions | RE |
| Lexicographic Enumerator | Prints strings in lexicographic order, no repetitions | Recursive |
Key Insight:
Recursively Enumerable literally means "can be enumerated by a TM"!
The name "RE" comes from this enumerator characterization.
Applications:
- Search Problems: Enumerate all solutions
- Theorem Provers: Enumerate all valid proofs
- Generating Functions: Output all values
- Language Generation: Generate all valid programs
7. Properties of Recursive and Recursively Enumerable Languages
Detailed Comparison:
| Property | Recursive (Decidable) | Recursively Enumerable |
|---|---|---|
| Definition | TM always halts (accept/reject) | TM halts on accept, may loop on reject |
| Alternative name | Decidable, Computable | Recognizable, Semi-decidable |
| Halting | Always halts | May not halt |
| Accept decision | Yes | Yes |
| Reject decision | Yes (halts in reject) | No (may loop forever) |
| Complement | Recursive | May not be RE |
| Union | Recursive | RE |
| Intersection | Recursive | RE |
Closure Properties:
Recursive Languages are Closed Under:
- ✓ Union: If L₁, L₂ recursive → L₁ ∪ L₂ recursive
- ✓ Intersection: L₁ ∩ L₂ recursive
- ✓ Complement: L̄ recursive
- ✓ Concatenation: L₁ · L₂ recursive
- ✓ Kleene Star: L* recursive
- ✓ Difference: L₁ - L₂ recursive
Proof technique: Combine TMs that always halt
RE Languages are Closed Under:
- ✓ Union: If L₁, L₂ RE → L₁ ∪ L₂ RE
- ✓ Intersection: L₁ ∩ L₂ RE
- ✗ Complement: L̄ may NOT be RE
- ✓ Concatenation: L₁ · L₂ RE
- ✓ Kleene Star: L* RE
- ✗ Difference: L₁ - L₂ may NOT be RE
Key Theorems:
Theorem 1: Complement Characterization
L is recursive if and only if both L and L̄ are RE.
Proof (→): If L recursive, TM M decides L. Complement TM M' decides L̄ by swapping accept/reject.
Proof (←): If L and L̄ both RE, run both TMs in parallel (dovetailing). For any input, exactly one will accept.
Example: Halting Problem
HALT = {⟨M, w⟩ | M halts on w}
- HALT is RE (can recognize by simulating M on w)
- HALT is NOT Recursive (undecidable)
- Therefore: HALT̄ is NOT RE (by complement theorem)
Hierarchy of Languages:
All Languages
▲
|
RE Languages (Recognizable)
▲
|
Recursive Languages (Decidable)
▲
|
Context-Free Languages
▲
|
Regular Languages
Famous Undecidable Problems (RE but not Recursive):
- Halting Problem: Does TM M halt on input w?
- Acceptance Problem: Does TM M accept input w?
- Emptiness: Is L(M) = ∅?
- Equivalence: Do M₁ and M₂ accept same language?
- Totality: Does M accept all strings?
Famous Non-RE Problems:
- HALT̄: Complement of halting problem
- Non-Acceptance: M does NOT accept w
- Non-Halting: M does NOT halt on w
8. Universal Turing Machine (UTM)
A Universal Turing Machine (UTM) is a TM that can simulate ANY other TM. It's the theoretical basis for modern programmable computers!
Concept:
UTM U takes two inputs:
- ⟨M⟩: Encoding (description) of a Turing Machine M
- w: Input string for M
U(⟨M⟩, w) simulates M on w:
- If M accepts w, U accepts
- If M rejects w, U rejects
- If M loops on w, U loops
Why Universal TM is Important:
- Stored-Program Concept:
- Programs are DATA (can be stored, manipulated)
- Same machine can run different programs
- Foundation of modern computers (von Neumann architecture)
- Interpreters/Compilers:
- Python interpreter is a UTM for Python programs
- Java JVM simulates Java bytecode
- Self-Reference:
- TM can take TM as input
- Enables proofs of undecidability (halting problem)
Encoding Turing Machines:
To input TM into UTM, need to encode M as a string ⟨M⟩
Encoding Scheme:
- Assign numbers to states: q₀ = 1, q₁ = 2, q₂ = 3, ...
- Assign numbers to tape symbols: 0 = 1, 1 = 2, B = 3, ...
- Encode directions: L = 1, R = 2
- Encode each transition δ(qᵢ, aⱼ) = (qₖ, aₗ, D):
- As string: 0^i 1 0^j 1 0^k 1 0^l 1 0^D
- Concatenate all transitions with separator 11
- Result: ⟨M⟩ is a binary string describing M
Example: δ(q₁, 0) = (q₂, 1, R)
Encoded as: 01100101100
How UTM Works:
- Input: UTM receives ⟨M⟩w on tape
- Setup: UTM uses multiple tapes (or tracks):
- Tape 1: Stores ⟨M⟩ (TM description)
- Tape 2: Simulates M's tape (content)
- Tape 3: Stores M's current state
- Tape 4: Stores M's head position
- Simulation Loop:
- Look up current state and tape symbol in ⟨M⟩
- Find matching transition
- Update simulated tape, state, head position
- Repeat until M halts (or loop forever)
Theorem:
There exists a Universal Turing Machine U such that for any TM M and input w:
U(⟨M⟩, w) = M(w)
U simulates M perfectly - same accept/reject/loop behavior.
Applications of UTM:
| Application | Description | Real-World Example |
|---|---|---|
| Interpreters | Execute programs in high-level language | Python, JavaScript engines |
| Compilers | Transform code, verify syntax | GCC, LLVM |
| Virtual Machines | Simulate entire computer systems | JVM, Docker, VirtualBox |
| Emulators | Run old software on new hardware | Game console emulators |
| Debuggers | Step-by-step program execution | GDB, Visual Studio debugger |
UTM and Undecidability:
UTM enables self-reference, leading to undecidable problems:
Halting Problem Proof (Outline):
- Assume HALT is decidable by TM H
- Build TM D using H and UTM:
D(⟨M⟩): if H(⟨M⟩, ⟨M⟩) accepts: // M halts on ⟨M⟩ loop forever else: halt - What does D(⟨D⟩) do?
- If D halts on ⟨D⟩ → D loops (contradiction!)
- If D loops on ⟨D⟩ → D halts (contradiction!)
- Contradiction → H cannot exist → HALT undecidable
Significance:
UTM shows that:
- General-purpose computers are possible (don't need new hardware for each program)
- Programs are data (can be input to other programs)
- Fundamental limits exist (some problems proven unsolvable)
- Self-reference is powerful (enables metacomputation and diagonalization)
⚡ Quick Revision (Unit IV Cheat Sheet)
TM Fundamentals
- TM: (Q, Σ, Γ, δ, q₀, B, F), δ: Q×Γ → Q×Γ×{L,R}.
- ID Notation: α₁ q α₂ (head at first symbol of α₂).
- Acceptance: By reaching accept state; may also consider halting semantics.
Language Classes
Regular ⊂ CFL ⊂ Recursive (Decidable) ⊂ RE (Recognizable) ⊂ All.
- Recursive: TM halts on all inputs (accept/reject).
- RE: TM halts on yes-instances; may loop on no-instances.
- Key: L is Recursive ⇔ L and L̄ are both RE.
Equivalences
- DTM ≡ NTM (same power).
- Multi-tape TM ≡ Single-tape TM (efficiency differs).
- Universal TM simulates any TM on ⟨M⟩, w.
Undecidability
- Halting Problem is undecidable (diagonalization via self-reference).
- Many problems reduce from HALT to prove undecidability.