Turing Machines

A Turing machine (Alan Turing, 1936) has a finite control and an infinite tape it can read, write and move along in both directions. It's a 7-tuple (Q, Σ, Γ, δ, q₀, B, F) with δ: Q × Γ → Q × Γ × {L, R}.

TM for L = {aⁿbⁿ | n ≥ 1}

Idea: repeatedly mark the leftmost a as X and the matching b as Y.

  State | a          | b          | X          | Y          | B
 -------+------------+------------+------------+------------+-----------
  q0    | (q1, X, R) |     –      |     –      | (q3, Y, R) |     –
  q1    | (q1, a, R) | (q2, Y, L) |     –      | (q1, Y, R) |     –
  q2    | (q2, a, L) |     –      | (q0, X, R) | (q2, Y, L) |     –
  q3    |     –      |     –      |     –      | (q3, Y, R) | (q4, B, R)
  q4    |  accept (halting state)

Trace of aabb:  aabb → Xabb → XaYb → XXYb → XXYY → accept

Variants (All Equivalent in Power)

Multi-tape, multi-track, two-way infinite tape, non-deterministic TM, and TM with stay option. All recognise the same class of languages.

Church–Turing Thesis

Anything that can be computed by an algorithm can be computed by a Turing machine.

Recursive vs Recursively Enumerable