A TURING MACHINE CONSISTS OF: · AN INFINITE TAPE divided into cells, each holding one symbol · A READ/WRITE HEAD positioned over one cell · A FINITE CONTROL — a finite set of states ON EACH STEP THE MACHINE: 1. READS the symbol under the head 2. WRITES a symbol to that cell (possibly the same one) 3. MOVES the head ONE cell LEFT or RIGHT 4. CHANGES state THAT IS THE ENTIRE MODEL. It is deliberately, almost perversely simple — and the claim of the section is that nothing more powerful is possible. ── THE FORMAL DEFINITION ─────────────────────────────────── M = (Q, Σ, Γ, δ, q₀, B, F) Q finite set of STATES Σ INPUT alphabet Γ TAPE alphabet, with Σ ⊆ Γ δ TRANSITION FUNCTION δ : Q × Γ → Q × Γ × {L, R} q₀ start state B the BLANK symbol, B ∈ Γ but B ∉ Σ F accepting states READ δ CAREFULLY: δ(q, X) = (p, Y, D) means "in state q reading X, go to state p, WRITE Y over X, and move in direction D". ── HOW IT DIFFERS FROM WHAT CAME BEFORE ──────────────────── The whole section is best understood as a sequence of memory upgrades: FINITE AUTOMATON no memory beyond the state reads input once, left to right PUSHDOWN AUTOMATON a STACK — last-in-first-out only input still read once, left to right TURING MACHINE an unbounded TAPE that can be READ AND WRITTEN AT ANY POSITION, and the head MOVES IN BOTH DIRECTIONS THREE CAPABILITIES ARE NEW, AND EACH MATTERS: 1. THE HEAD CAN MOVE LEFT, so the machine can revisit and re-read. 2. THE MACHINE CAN WRITE, so the tape is memory rather than merely input. 3. THE INPUT ITSELF CAN BE OVERWRITTEN — the tape serves as input, working memory and output at once. THIS IS WHY A TM CAN RECOGNISE aⁿbⁿcⁿ WHILE A PDA CANNOT: it can mark an a, walk right to mark a b, walk further to mark a c, then walk all the way back — comparing three counts by physically crossing them off, which no single stack allows. ── INSTANTANEOUS DESCRIPTION ─────────────────────────────── The complete configuration is written α q β where q is the current state, α is the tape content to the LEFT of the head, and β is the content from the head RIGHTWARD. The head is on the FIRST SYMBOL OF β. So X X q₀ a b b means: tape reads XXabb, machine in state q₀, head on the third cell. ── ACCEPTANCE AND HALTING ────────────────────────────────── A TM ACCEPTS w if, started with w on the tape and the head on its first symbol, it reaches an accepting state. THE CRITICAL DIFFERENCE FROM ALL EARLIER MODELS: A TURING MACHINE NEED NOT HALT. A finite automaton always stops — it reads the input and finishes. A TM may loop forever, and there is no way in general to detect this from outside. THIS SINGLE FACT GENERATES EVERYTHING IN THE LATER TOPICS: the halting problem, undecidability, and the distinction between recursive and recursively enumerable languages. HENCE TWO CLASSES OF LANGUAGE: RECURSIVELY ENUMERABLE (Turing-recognisable) — some TM accepts exactly the strings in L. On strings NOT in L it may reject OR LOOP FOREVER. RECURSIVE (decidable) — some TM accepts exactly L AND ALWAYS HALTS. It answers yes or no on every input. RECURSIVE ⊊ RECURSIVELY ENUMERABLE, and the strictness of that containment is proved by the halting problem. ── A FULLY WORKED MACHINE: L = { aⁿbⁿ } ──────────────────── THE STRATEGY: repeatedly cross off one a and one b until both run out. q₀ — find the leftmost unmarked a δ(q₀, a) = (q₁, X, R) mark the a as X, go right δ(q₀, Y) = (q₃, Y, R) no a's left — check the rest δ(q₀, B) = ACCEPT empty input accepted q₁ — scan right for the first unmarked b δ(q₁, a) = (q₁, a, R) δ(q₁, Y) = (q₁, Y, R) δ(q₁, b) = (q₂, Y, L) mark the b as Y, turn back q₂ — scan left to the marked X δ(q₂, a) = (q₂, a, L) δ(q₂, Y) = (q₂, Y, L) δ(q₂, X) = (q₀, X, R) back at the marker, repeat q₃ — verify only Y's remain δ(q₃, Y) = (q₃, Y, R) δ(q₃, B) = ACCEPT TRACE ON aabb, head position shown in brackets: q₀ [a]abb mark a → X, move right q₁ X[a]bb scan right over a q₁ Xa[b]b found b → mark Y, turn left q₂ X[a]Yb scan left q₂ [X]aYb reached X, turn right q₀ X[a]Yb mark second a → X q₁ XX[Y]b skip Y q₁ XXY[b] found b → mark Y, turn left q₂ XX[Y]Y scan left q₂ X[X]YY reached X, turn right q₀ XX[Y]Y no a's left → state q₃ q₃ XXY[Y] skip Y q₃ XXYY[B] blank reached → ACCEPT THIRTEEN STEPS. Verified: aabb and ab ACCEPT; aab and abb REJECT; the empty string ACCEPTS. THE MECHANISM IS WORTH NAMING: THE MACHINE IS **COUNTING BY PAIRING**, crossing off one of each. It never stores a number anywhere — the marks on the tape ARE the count, and that idea recurs throughout Turing machine construction.

── THE REMARKABLE ROBUSTNESS OF THE MODEL ────────────────── Every one of the following variants recognises EXACTLY THE SAME CLASS OF LANGUAGES as the basic machine: · MULTIPLE TAPES (any fixed number) · MULTIPLE TRACKS on one tape · A TWO-WAY INFINITE TAPE (infinite in both directions) · NON-DETERMINISM · A STAY-PUT option in addition to L and R · Larger tape alphabets · MULTIPLE HEADS · TWO-DIMENSIONAL tape · A machine with TWO STACKS instead of a tape NONE OF THESE ADDS POWER. Each is simulated by the basic model with at most a polynomial slowdown (except non-determinism, which costs exponentially in time but nothing in computability). THE TWO-STACK RESULT IS THE ONE THAT TIES THIS SECTION TO THE LAST: A PDA WITH **TWO** STACKS IS EQUIVALENT TO A TURING MACHINE. One stack holds the tape to the left of the head, the other the tape to the right; moving the head is popping from one and pushing to the other. THAT IS PRECISELY WHY {aⁿbⁿcⁿ} NEEDED TWO STACKS AND WHY CONTEXT-FREE LANGUAGES ARE NOT CLOSED UNDER INTERSECTION. ── THE CHURCH-TURING THESIS ──────────────────────────────── Developed fully in a later topic, but stated here because it is what gives the model its significance: ANY FUNCTION THAT CAN BE COMPUTED BY ANY EFFECTIVE PROCEDURE WHATSOEVER CAN BE COMPUTED BY A TURING MACHINE. THIS IS NOT A THEOREM. It cannot be proved, because "effective procedure" is an informal notion. IT IS A THESIS — a claim about the relationship between a formal model and an intuitive idea. THE EVIDENCE IS THE CONVERGENCE OF INDEPENDENT DEFINITIONS. In the 1930s several mathematicians formalised computation in completely different ways: TURING MACHINES (Turing, 1936) λ-CALCULUS (Church, 1936) RECURSIVE FUNCTIONS (Gödel, Herbrand) POST SYSTEMS (Post) REGISTER MACHINES (later) ALL WERE PROVED EQUIVALENT. Every subsequent model — cellular automata, quantum computers, every programming language ever designed — has also proved equivalent in COMPUTABILITY, whatever its advantages in speed or convenience. THAT IS THE SAME STYLE OF ARGUMENT USED FOR REGULAR LANGUAGES IN AN EARLIER TOPIC, where four independent definitions converged. Here the stakes are higher: the claim is about the limits of computation itself. ── WHAT A TURING MACHINE IS FOR ──────────────────────────── IT IS NOT A PRACTICAL COMPUTER. Nobody programs one to get work done; a machine to add two numbers takes dozens of states. ITS PURPOSE IS TO MAKE "COMPUTABLE" A MATHEMATICALLY PRECISE TERM, so that one can PROVE things are impossible. · Without a formal model, "no algorithm exists for X" is not a statement that can be proved — only a report of failure so far. · With one, it becomes a theorem, and the later topics of this section prove several. THE THREE ROLES A TM PLAYS, each a later topic: LANGUAGE RECOGNISER — decides membership FUNCTION COMPUTER — transforms input to output on the tape ENUMERATOR — generates the strings of a language AND ONE MORE, WHICH IS THE DEEPEST: a Turing machine can be ENCODED AS A STRING and given as input to another Turing machine. THE UNIVERSAL TURING MACHINE, covered later, is the theoretical statement of the STORED-PROGRAM COMPUTER — the idea that a program is just data, which is the single most consequential idea in computing.