the mu-recursive functions
/ mu -> MYOO /
Suppose you want to define, from scratch, every function on the natural numbers that a person could in principle compute by hand. You start with a few utterly trivial building blocks and a few rules for gluing them together, and you ask: how far can these reach? The mu-recursive functions are the answer mathematicians gave in the 1930s, a purely arithmetic definition of computability that never mentions a machine, a tape, or a step, only functions built from functions.
You start with three base functions: the zero function (always returns 0), the successor function (n maps to n+1), and the projections (pick out one argument from several). You combine them with two safe rules, composition (feed the output of functions into another) and primitive recursion (define f(n+1) in terms of f(n), like a for-loop). These yield the primitive recursive functions, which include nearly all ordinary arithmetic but, it turns out, not quite everything computable. The final ingredient is the mu-operator (minimization): mu m [g(m) = 0] means 'search m = 0, 1, 2, ... and return the first m that makes g zero'. This is an unbounded search, like a while-loop that might never stop, and it is precisely what lifts the primitive recursive functions up to the full class.
The mu-recursive functions matter because the class they define is exactly the Turing-computable functions, computed by an apparatus with no resemblance whatsoever to a machine. This is one more strand of the great convergence behind the Church-Turing thesis: Turing machines, the lambda calculus, and mu-recursion, three completely different definitions, all carve out the identical set of functions. The honest subtlety is the mu-operator: because the search can run forever when no m works, mu-recursive functions are in general partial (undefined on some inputs), exactly mirroring how a Turing machine can loop forever. Without minimization you get only the primitive recursive functions, a strictly smaller, total class.
Addition is primitive recursive: add(m, 0) = m and add(m, n+1) = succ(add(m, n)). But Ackermann's function grows too fast to be primitive recursive yet is still mu-recursive (and Turing-computable). The minimization operator is what reaches such functions, at the cost of possibly searching forever.
Composition and recursion alone give the primitive recursive functions; adding minimization reaches all computable ones.
The unbounded search of the mu-operator is what makes the functions possibly partial, exactly mirroring a looping Turing machine. The primitive recursive functions (no minimization) are total but strictly weaker.