Turing Machines

What is a Turing Machine?

Turing Machine (TM) is the most powerful computational model in theory of computation.

Simple Analogy

Think of a Turing Machine like a person with unlimited paper:

  • Finite Automaton: Person with no memory (only current state)
  • Pushdown Automaton: Person with one stack of sticky notes
  • Turing Machine: Person with infinite paper tape (can read/write anywhere!)

Historical Context

Invented by: Alan Turing (1936)

Purpose: Answer fundamental question:

“What does it mean to compute?”

Result: Model of general-purpose computation that can simulate any algorithm

Why Turing Machines?

More powerful than:

  • Finite Automata (FA)
  • Pushdown Automata (PDA)
  • Context-Free Grammars (CFG)

Can recognize:

  • All regular languages ✓
  • All context-free languages ✓
  • Many non-context-free languages ✓
  • But NOT all languages! (some undecidable)

Can compute:

  • Addition, multiplication, sorting
  • Prime number checking
  • Program execution
  • Anything a modern computer can compute!

Church-Turing Thesis

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

Informal: TM = “algorithm”

Not a theorem: Cannot be proven (philosophical statement)

Universally accepted: No counterexample found in 90+ years!

Implications:

  • TM captures notion of “computation”
  • Problems undecidable for TM are undecidable for any computer
  • Limits of TM = limits of computation

TM vs Previous Models

Comparison Table

FeatureFAPDATM
MemoryStates onlyStackInfinite tape
AccessCurrent stateStack topAny tape cell
MovementForward onlyInput forwardBoth directions
WriteNoStack onlyYes, on tape
PowerRegularContext-freeRecursively enumerable
Example language{aⁿbⁿ}: No{aⁿbⁿ}: Yes{aⁿbⁿcⁿ}: Yes

Key Differences

FA → PDA: Added stack memory

PDA → TM:

  • Stack → Infinite tape
  • Forward only → Bidirectional
  • Read-only input → Read/write tape
  • One-way → Can revisit cells

Components of Turing Machine

Physical Description

                   Read/Write Head
                         ↓
     ┌───┬───┬───┬───┬───┬───┬───┬───┐
     │ B │ a │ b │ c │ d │ B │ B │ B │ ... → Infinite
     └───┴───┴───┴───┴───┴───┴───┴───┘
          ←───────────→
        Can move left or right

     Finite Control
     (Current State: q₁)

Components

  1. Tape: Infinite in both directions, divided into cells
  2. Tape alphabet: Symbols that can appear on tape (Γ)
  3. Head: Reads and writes symbols, moves left or right
  4. States: Finite set of states (Q)
  5. Transitions: Rules for state changes, writing, and movement

The Tape

Characteristics:

  • Infinite: Extends forever in both directions
  • Cells: Each holds one symbol from tape alphabet Γ
  • Blank symbol (B or ␣): Represents empty cells
  • Initially: Input on tape, rest blank

Example:

Input: "abc"

Initial tape:
... B B B a b c B B B ...
        ↑
     Start here

Tape Alphabet vs Input Alphabet

Input alphabet (Σ): Symbols in input string

  • Example: Σ = {a, b, c}

Tape alphabet (Γ): All symbols on tape

  • Example: Γ = {a, b, c, B, X, Y}
  • Must contain: Σ ∪ {B}
  • Can contain: Additional work symbols (X, Y, Z, etc.)

Relationship: Σ ⊂ Γ

Transitions

Form: δ(current_state, current_symbol) = (new_state, write_symbol, direction)

Example:

δ(q₀, a) = (q₁, X, R)

Meaning:

  • In state q₀, reading ‘a’
  • Write ‘X’ (replacing ‘a’)
  • Move Right
  • Go to state q₁

Direction:

  • R: Move right
  • L: Move left
  • (S): Stay (some definitions allow this)

States

Types of states:

  1. Start state (q₀): Where computation begins
  2. Accept state (qaccept): If reached, accept input
  3. Reject state (qreject): If reached, reject input
  4. Halting states: {qaccept, qreject}
  5. Non-halting states: All others

Halting:

  • TM halts when reaching qaccept or qreject
  • TM may run forever (never halt!)

How Turing Machine Works

Configuration

Configuration = (state, tape_contents, head_position)

Example: q₁abc (state q₁, head at ‘a’, tape has “abc”)

Notation:

  • uqv means: tape = …uv…, state = q, head at first symbol of v
  • q₀abc: Start state, head at ‘a’
  • aXq₁bc: State q₁, head at ‘b’, tape has “aXbc”

Computation Step

If: δ(q, a) = (p, b, R)

Then: uqav ⊢ ubpv

  • Replace ‘a’ with ‘b’
  • Move right
  • Change state q → p

If: δ(q, a) = (p, b, L)

Then: cuqav ⊢ cpubv

  • Replace ‘a’ with ‘b’
  • Move left
  • Change state q → p

Acceptance

Accept: Reach qaccept (halts and accepts)

Reject:

  • Reach qreject (halts and rejects), OR
  • No valid transition (crashes and rejects)

Loop: Run forever (never halt)

Three Possible Outcomes

For input w and TM M:

  1. Accept: M(w) halts in qaccept
  2. Reject: M(w) halts in qreject or crashes
  3. Loop: M(w) never halts

Example outcomes:

M₁("abc") → Accept
M₂("xyz") → Reject
M₃("loop") → Runs forever ⟳

Languages and TMs

Language Recognized by TM

L(M) = {w | M accepts w}

“All strings that M accepts”

Note: Does NOT include:

  • Strings M rejects
  • Strings M loops on

Recursively Enumerable Languages

Definition: L is recursively enumerable (RE) if some TM M recognizes L

L = L(M) for some TM M

Also called:

  • Turing-recognizable
  • Partially decidable
  • Computably enumerable (c.e.)

Recursive Languages (Decidable)

Definition: L is recursive (decidable) if some TM M decides L

M decides L means:

  • M halts on ALL inputs
  • M accepts if w ∈ L
  • M rejects if w ∉ L

Key: No looping! Always halts.

Hierarchy

Regular Languages
       ⊂
Context-Free Languages
       ⊂
Recursive (Decidable) Languages
       ⊂
Recursively Enumerable Languages
       ⊂
All Languages

Deterministic vs Non-deterministic TM

Deterministic TM (DTM)

Transition function: δ: Q × Γ → Q × Γ × {L, R}

At most one transition per (state, symbol)

Standard model: When we say “TM”, we mean DTM

Non-deterministic TM (NTM)

Transition relation: δ: Q × Γ → P(Q × Γ × {L, R})

Can have multiple transitions per (state, symbol)

Accepts if ANY path leads to acceptance

Important Theorem

Theorem: Every NTM can be simulated by a DTM

DTM and NTM have same power!

Difference from FA/PDA:

  • NFA = DFA in power
  • NPDA ≠ DPDA in power
  • NTM = DTM in power ✓

Example Languages

TM Can Recognize

✓ {aⁿbⁿcⁿ | n ≥ 0} (not context-free!) ✓ {ww | w ∈ {a,b}*} (not context-free!) ✓ {aⁿ² | n ≥ 0} (not context-free!) ✓ {aᵖ | p is prime} ✓ {⟨G,w⟩ | CFG G generates w}

TM Cannot Recognize (Undecidable)

✗ Halting problem: {⟨M,w⟩ | TM M halts on w} ✗ {⟨M⟩ | L(M) = ∅} ✗ {⟨M₁,M₂⟩ | L(M₁) = L(M₂)}

Variants of Turing Machines

Many equivalent variants:

  1. Multi-tape TM: Multiple tapes and heads
  2. Multi-head TM: Multiple heads on one tape
  3. Two-way infinite tape: Standard model
  4. One-way infinite tape: Only extends right
  5. Multi-dimensional tape: 2D grid, 3D grid, etc.
  6. Non-deterministic TM: Multiple possible transitions

All equivalent: Can simulate each other!

Church-Turing thesis: All reasonable models have same power

Universal Turing Machine

Universal TM (UTM): A TM that can simulate any other TM

Input: ⟨M, w⟩ (description of TM M and input w)

Output: Same as M(w)

Importance:

  • Proves existence of programmable computers
  • M = “program”, w = “data”
  • UTM = “computer” that runs programs!

Encoding Turing Machines

Can represent TM as string: ⟨M⟩

Encoding includes:

  • States (Q)
  • Alphabets (Σ, Γ)
  • Transitions (δ)
  • Start/accept/reject states

Example encoding: Binary string representing TM

Consequence: Can have TM that takes TM as input!

Why TMs are Important

Theoretical Importance

  1. Model of computation: Defines what’s computable
  2. Decidability: Shows some problems unsolvable
  3. Complexity: Basis for P, NP, etc.
  4. Universal computation: UTM ≈ programmable computer

Practical Importance

  1. Limits of computation: What computers can/cannot do
  2. Algorithm design: Understanding computability
  3. Compiler theory: Language recognition
  4. Verification: Proving program properties

Philosophical Importance

  1. Nature of mind: Can human thought be computed?
  2. Artificial Intelligence: What can AI achieve?
  3. Mathematics: Are all true statements provable?

Limitations of Turing Machines

Halting Problem

Cannot decide: Does TM M halt on input w?

Proved by: Alan Turing (1936)

Consequence: Some problems fundamentally unsolvable!

Other Undecidable Problems

  • Is L(M) empty?
  • Is L(M) = Σ*?
  • Do M₁ and M₂ accept same language?
  • Is grammar G ambiguous?

Practical Limitations

Complexity: Even decidable problems may take too long

  • Exponential time
  • Beyond practical computation

Historical Impact

1936: Turing introduces TM

1940s: First electronic computers (ENIAC)

1950s: Turing test for AI

Modern: Theoretical foundation for:

  • Computer science
  • Programming languages
  • Complexity theory
  • Cryptography

Important Exam Points

  1. ✓ Definition: Infinite tape, read/write head, states, transitions
  2. ✓ More powerful: Can recognize {aⁿbⁿcⁿ}, {ww}, non-CFLs
  3. ✓ Three outcomes: Accept, reject, or loop forever
  4. ✓ Decidable: TM halts on all inputs
  5. ✓ Recognizable: TM accepts all strings in language (may loop on others)
  6. ✓ Church-Turing thesis: TM = “algorithm”
  7. ✓ Universal TM: Can simulate any TM
  8. ✓ Halting problem: Undecidable!
  9. ✓ DTM = NTM: Same power (unlike PDA)
  10. ✓ Tape alphabet Γ ⊃ input alphabet Σ

Common Mistakes to Avoid

✗ Mistake 1: Thinking TM can solve everything
✓ Correct: Halting problem undecidable

✗ Mistake 2: Finite tape
✓ Correct: Tape is infinite

✗ Mistake 3: Can’t write on tape
✓ Correct: Can read AND write

✗ Mistake 4: Head moves only right
✓ Correct: Moves left or right

✗ Mistake 5: Always halts
✓ Correct: May loop forever

✗ Mistake 6: DTM ≠ NTM in power
✓ Correct: DTM = NTM (can simulate each other)

Practice Questions

Q1: What can TM do that PDA cannot?

Answer: Move bidirectionally, write on tape, recognize {aⁿbⁿcⁿ}.

Q2: What is Church-Turing thesis?

Answer: TM can compute anything computable by any algorithm.

Q3: Can TM always decide if it will halt?

Answer: No! Halting problem undecidable.

Q4: Difference between decidable and recognizable?

Answer: Decidable always halts; recognizable may loop on reject.

Q5: Is {aⁿbⁿcⁿ} recognizable by TM?

Answer: Yes! TM can count three values.

Q6: What is Universal Turing Machine?

Answer: TM that simulates any other TM (like programmable computer).

Q7: Are DTM and NTM equally powerful?

Answer: Yes! Can simulate each other.

Q8: What are three possible outcomes of TM?

Answer: Accept, reject, or loop forever.

Summary

  • Turing Machine: Most powerful computational model
  • Components: Infinite tape, read/write head, finite states, transitions
  • Tape: Infinite both directions, read/write, bidirectional movement
  • Three outcomes: Accept, reject, loop
  • Decidable: TM halts on all inputs
  • Recognizable: TM accepts all strings in language
  • Church-Turing thesis: TM = “algorithm”
  • Universal TM: Can simulate any TM (programmable computer)
  • DTM = NTM: Same power (unlike PDA)
  • Limitations: Halting problem undecidable
  • Hierarchy: Regular ⊂ CFL ⊂ Decidable ⊂ RE ⊂ All
  • Applications: Theory of computation, decidability, complexity
  • Key insight: TM defines limits of computation itself

Turing Machines are the foundation of computer science and theory of computation!