Turing Machines

The Turing machine (TM) is the most powerful computational model. It defines what it means for a problem to be "computable" and forms the theoretical foundation of all of computer science.

Definition

A Turing machine M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject) consists of:

• Q: Finite set of states
• Σ: Input alphabet (doesn't include blank symbol ⊔)
• Γ: Tape alphabet (Σ ⊂ Γ, includes ⊔)
• δ: Transition function δ: Q × Γ → Q × Γ × {L, R} (read symbol, write symbol, move head)
• q₀: Start state
• q_accept: Accepting state (halts and accepts)
• q_reject: Rejecting state (halts and rejects)

The Tape

An infinite tape of cells, each holding a symbol from Γ. Initially contains the input followed by blanks.

... ⊔ ⊔ [a] [b] [a] [b] ⊔ ⊔ ⊔ ...
              ^
          head position

Computation

1. Read the symbol under the head.
2. Based on current state and symbol: write a new symbol, move head left or right, transition to new state.
3. Repeat until reaching q_accept or q_reject.

If the machine never reaches q_accept or q_reject, it loops (runs forever).

Configuration

A configuration captures the complete state of a computation: (current state, tape contents, head position).

Written as: uqv where q is the state, u is the tape to the left, and v is the tape from the head onward.

Example

TM recognizing {w#w | w ∈ {0,1}*} (two identical strings separated by #):

1. Scan right to find #.
2. Match characters: mark first unmatched character in first half (replace with X),
   scan right past # to find corresponding character in second half (replace with X).
3. If all matched, accept. If mismatch, reject.

Variants

Multi-Tape Turing Machine

Multiple tapes, each with its own head. Transition: read all heads simultaneously, write to each, move each independently.

Theorem: Every multi-tape TM can be simulated by a single-tape TM (with polynomial slowdown).

Nondeterministic Turing Machine (NTM)

δ: Q × Γ → P(Q × Γ × {L, R}). Multiple possible transitions at each step.

Accepts if any computation path reaches q_accept.

Theorem: Every NTM can be simulated by a deterministic TM (with exponential slowdown in worst case).

Two-Way Infinite Tape

Tape extends infinitely in both directions. Equivalent to standard TM (simulate with two tracks on one tape).

Stay-Put Head

Head can stay in place (δ includes S for "stay"). Equivalent to standard TM (simulate stay by moving right then left).

Universal Turing Machine

A Universal Turing Machine U takes as input the description of any TM M and an input w, and simulates M on w.

U(⟨M⟩, w) = M(w)

U accepts (⟨M⟩, w) iff M accepts w.

Significance: U is the theoretical model of a stored-program computer — a single machine that can execute any program. This is the foundation of general-purpose computing.

Encoding: TM descriptions ⟨M⟩ are strings over a fixed alphabet. There is a standard encoding scheme (e.g., binary encoding of states, transitions).

Church-Turing Thesis

Thesis (Church, 1936; Turing, 1936): The class of functions computable by a Turing machine is exactly the class of functions that are effectively computable (by any reasonable notion of computation).

This is a thesis, not a theorem — it can't be formally proved because "effectively computable" is an informal concept. But it has been validated by the equivalence of many independent computational models:

• Turing machines
• Lambda calculus (Church)
• Recursive functions (Gödel, Kleene)
• Post systems
• Markov algorithms
• Register machines
• Modern programming languages (with unbounded memory)

Consequence: Any problem solvable by any conceivable computer is solvable by a Turing machine. If a TM can't solve it, nothing can (assuming Church-Turing thesis).

Extended Church-Turing Thesis

A stronger claim: The class of functions efficiently computable (in polynomial time) is the same across all "reasonable" computational models.

This is more controversial — quantum computers may violate it (BQP vs BPP is unknown).

Computational Power

DFA ⊊ DPDA ⊊ NPDA ⊊ TM

Regular ⊊ DCFL ⊊ CFL ⊊ CSL ⊊ Recursive ⊊ RE

Each model is strictly more powerful than the previous:

• DFA can't count (can't recognize aⁿbⁿ)
• PDA can't count two things independently (can't recognize aⁿbⁿcⁿ)
• TM can compute anything computable

What TMs Can Do That PDAs Can't

• aⁿbⁿcⁿ: Count three symbols simultaneously.
• ww: Check if a string is a repeated word.
• Prime numbers: Decide if a binary number is prime.
• Any decidable problem: Type checking, theorem proving, optimization.

What TMs Can't Do

Some problems are undecidable — no TM can solve them. The halting problem is the most famous example (covered in next file).

Encoding and Computation History

Encoding

Any finite object can be encoded as a string: ⟨M⟩ = encoding of TM M. ⟨G⟩ = encoding of graph G. ⟨M, w⟩ = encoding of TM M and input w.

Computation History

A computation history of M on w is the sequence of configurations C₁, C₂, ..., Cₖ where:

• C₁ is the start configuration
• Each Cᵢ₊₁ follows from Cᵢ by one step of M
• Cₖ is an accepting/rejecting configuration

Accepting computation history: Ends in q_accept.

Computation histories are used in many undecidability proofs and complexity theory results.

Enumerators

A TM can be used as an enumerator — it generates (prints) all strings in a language, one by one, possibly with repetition.

Theorem: L is recursively enumerable (recognized by a TM) iff L can be enumerated by a TM.

Linear Bounded Automata (LBA)

A TM restricted to use only the tape cells containing the input (no additional tape). Recognizes exactly the context-sensitive languages.

LBAs are more powerful than PDAs but less powerful than general TMs.

Example: LBA can decide {aⁿbⁿcⁿ | n ≥ 0} by crossing off matched triples.

RAM Model

The Random Access Machine is a more practical computational model (closer to real computers):

• Memory cells addressed by integers
• Each cell holds an arbitrarily large integer
• Operations: arithmetic, comparison, memory access by address

Equivalence: RAMs and TMs can simulate each other with polynomial overhead. The RAM model is used in algorithm analysis (it's the standard model for O(n log n) bounds, etc.).

Applications in CS

• Computability: Defines what computers can and cannot solve. The halting problem, Rice's theorem, and other undecidability results use TMs.
• Complexity theory: P, NP, PSPACE — all defined in terms of TM resource bounds.
• Programming language theory: Turing completeness — a language/system is Turing complete if it can simulate any TM. Most practical languages are Turing complete.
• Compiler theory: Language recognition. The distinction between regular, context-free, and context-sensitive determines which parsing techniques are needed.
• Formal verification: Undecidability results from TM theory tell us which verification problems are impossible in general.