A TURING MACHINE COMPUTES A FUNCTION f : Σ* → Σ* IF, STARTED WITH w ON THE TAPE, IT HALTS WITH f(w) ON THE TAPE. Such a machine is called a TRANSDUCER, as opposed to the ACCEPTOR of the previous topic. The distinction is only in how the result is read: an acceptor's answer is its final STATE, a transducer's answer is its final TAPE. ── TOTAL AND PARTIAL FUNCTIONS ───────────────────────────── A TOTAL function is defined for every input. A PARTIAL function may be undefined for some inputs — and for a Turing machine, "undefined at w" means THE MACHINE DOES NOT HALT ON w. TURING MACHINES COMPUTE EXACTLY THE PARTIAL RECURSIVE FUNCTIONS. THOSE THAT ALWAYS HALT COMPUTE THE TOTAL RECURSIVE FUNCTIONS. THE CORRESPONDENCE WITH THE PREVIOUS TOPIC IS EXACT: acceptor that may loop ↔ recursively enumerable language acceptor that always halts ↔ recursive language transducer that may loop ↔ partial recursive function transducer that always halts ↔ total recursive function THE SAME DISTINCTION APPEARS TWICE BECAUSE IT IS THE SAME PHENOMENON: halting cannot be guaranteed. ── REPRESENTING NUMBERS ──────────────────────────────────── UNARY is standard in Turing machine work: the number n is written as n consecutive 1s. · 0 is the empty string or a single 0, by convention · 3 is 111 · the pair (m, n) is written 1ᵐ 0 1ⁿ, with 0 as a separator WHY UNARY RATHER THAN BINARY: arithmetic becomes trivial to program — addition is concatenation, and comparison is pairing off — at the price of exponentially longer tapes. SINCE COMPUTABILITY IS THE QUESTION AND EFFICIENCY IS NOT, THE TRADE IS WORTH IT. BINARY IS USED WHEN COMPLEXITY MATTERS, which is why the later complexity topics assume it: an input of value n has length log n in binary and n in unary, and that difference is precisely what makes some problems look polynomial in unary and exponential in binary. ── WORKED: THE SUCCESSOR FUNCTION f(n) = n + 1 ───────────── Input 1ⁿ, output 1ⁿ⁺¹. "Scan right to the first blank; write 1; halt." TWO STATES SUFFICE. The simplest non-trivial computation there is. ── WORKED: ADDITION f(m, n) = m + n ──────────────────────── Input 1ᵐ 0 1ⁿ, output 1ᵐ⁺ⁿ. THE ELEGANT METHOD: the tape already holds m + n ones, just with a 0 in the middle. So: "1. Scan right to the 0 and REPLACE IT WITH 1. 2. Scan right to the blank, step back, and ERASE THE LAST 1. 3. Halt." VERIFICATION on 3 + 2, input 111011 of length 6: after step 1: 111111 (six 1s) after step 2: 11111 (five 1s) = 5 = 3 + 2 ✓ AND ON 1 + 1, input 101 of length 3: after step 1: 111 after step 2: 11 = 2 ✓ AND ON 4 + 3, input 11110111 of length 8: after step 1: 11111111 after step 2: 1111111 = 7 ✓ THE OUTPUT IS ALWAYS ONE SHORTER THAN THE INPUT, since the separator became a 1 and one 1 was deleted — a useful check that the construction is right. ── WORKED: MULTIPLICATION f(m, n) = m × n ────────────────── Harder, and it introduces the loop-and-copy idiom: "1. Mark the first 1 of the m-block. 2. Copy the entire n-block to the far right of the tape, after a delimiter. 3. Return, mark the next 1 of the m-block, and repeat from step 2. 4. When every 1 of the m-block is marked, erase everything except the copied region. 5. Halt." THE n-BLOCK IS COPIED m TIMES, giving m × n ones. THE MACHINE HAS IMPLEMENTED A LOOP, with the marks on the m-block serving as the loop counter. ── WORKED: PROPER SUBTRACTION ────────────────────────────── f(m, n) = m − n if m ≥ n, and 0 otherwise ("proper" or "monus" subtraction, since the naturals have no negatives). "Repeat: erase one 1 from each block. Stop when either block is exhausted. If the n-block emptied first, what remains of the m-block is the answer; otherwise the answer is 0." THE SAME PAIRING IDIOM AS THE aⁿbⁿ RECOGNISER, used arithmetically.

── THE μ-RECURSIVE FUNCTIONS ─────────────────────────────── An entirely different formalisation of computation, developed by Gödel and Kleene, which turns out to define exactly the same class of functions. THE INITIAL FUNCTIONS: ZERO Z(x) = 0 SUCCESSOR S(x) = x + 1 PROJECTION Pᵢⁿ(x₁,…,xₙ) = xᵢ THE OPERATIONS THAT BUILD NEW FUNCTIONS: 1. COMPOSITION h(x̄) = f( g₁(x̄), …, gₖ(x̄) ) 2. PRIMITIVE RECURSION h(x̄, 0) = f(x̄) h(x̄, n+1) = g( x̄, n, h(x̄, n) ) — definition by recursion on one argument, with the recursion guaranteed to terminate because n decreases. 3. MINIMISATION (the μ-operator) h(x̄) = μy [ f(x̄, y) = 0 ] — "the SMALLEST y making f(x̄, y) zero". THIS IS AN UNBOUNDED SEARCH, and it is the only operation that can fail to terminate: if no such y exists, the search runs forever. THE FUNCTIONS BUILT WITHOUT MINIMISATION ARE THE PRIMITIVE RECURSIVE FUNCTIONS. Adding minimisation gives the μ-RECURSIVE (partial recursive) FUNCTIONS. THE THEOREM: A FUNCTION IS COMPUTABLE BY A TURING MACHINE IF AND ONLY IF IT IS μ-RECURSIVE. AND THE INSTRUCTIVE PART: MINIMISATION IS EXACTLY WHAT CORRESPONDS TO A POSSIBLY-NON-HALTING COMPUTATION. Primitive recursive functions are all TOTAL — every one of them always terminates — because every loop is bounded in advance. THE UNBOUNDED SEARCH IS THE "while" LOOP, AND THE "while" LOOP IS WHERE NON-TERMINATION LIVES. THIS MAPS DIRECTLY ONTO PROGRAMMING: a language with only "for" loops of predetermined length computes exactly the primitive recursive functions and always terminates; adding "while" makes it Turing complete and makes termination undecidable. THE TRADE IS UNAVOIDABLE AND IS MADE DELIBERATELY IN TOTAL FUNCTIONAL LANGUAGES AND IN PROOF ASSISTANTS, WHICH RESTRICT RECURSION TO GUARANTEE TERMINATION. ── THE ACKERMANN FUNCTION ────────────────────────────────── A famous witness that the primitive recursive functions are a PROPER subset: A(0, n) = n + 1 A(m, 0) = A(m − 1, 1) A(m, n) = A(m − 1, A(m, n − 1)) IT IS TOTAL AND COMPUTABLE — it always terminates and a Turing machine can evaluate it — BUT IT IS NOT PRIMITIVE RECURSIVE, because it grows faster than any primitive recursive function. A(4, 2) already has 19,729 digits. SO "ALWAYS TERMINATES" DOES NOT IMPLY "BOUNDED LOOPS ARE ENOUGH", which is exactly why minimisation had to be added. ── THE MODELS THAT ALL AGREE ─────────────────────────────── TURING MACHINES (Turing, 1936) λ-CALCULUS (Church, 1936) μ-RECURSIVE FUNCTIONS (Gödel, Kleene) POST SYSTEMS (Post, 1936) REGISTER MACHINES (Minsky) CELLULAR AUTOMATA every programming language ALL PROVED EQUIVALENT IN WHAT THEY COMPUTE. THREE OF THEM WERE PUBLISHED IN THE SAME YEAR, BY PEOPLE APPROACHING THE PROBLEM FROM MACHINES, FROM FUNCTIONS AND FROM LOGIC — and they landed on the same class. THAT CONVERGENCE IS THE EVIDENCE FOR THE CHURCH-TURING THESIS, and it is the same form of argument used for regular languages, where four definitions converged. Here it supports a far bolder claim: that this class is not one notion of computation among many, but COMPUTATION ITSELF.