General recursion — the μ-operator = Turing power

Parent: recursive-functions

Add one construct to primitive recursion and you reach all of computability — at the price of possible non-termination.

Minimization (the

μ-operator) μn. [ f(n, x) = 0 ] = the least n such that f(n,x)=0 (and f(k,x) is defined and nonzero for all k<n); undefined if no such n exists. This is an unbounded search — a while-loop with no known bound.

General (

μ-) recursive functions basic functions + composition + primitive recursion + μ. These are the partial recursive functions.

General recursive = Turing-computable

The μ-recursive functions are exactly the Turing-computable (= λ-definable) functions — the Church–Turing thesis made precise.

Why μ is the whole jump

• for → while. Primitive recursion = bounded for-loops (always halt, but limited, can't reach Ackermann-fast growth cheaply). μ = the unbounded while-loop.
• Non-termination enters. The search μn.[…] may run forever, so μ-recursive functions are partial — and "does this μ-search halt?" is the halting-problem.
• This is the phase transition. Bounded recursion is decidable and total; unbounded recursion is Turing-complete and undecidable. μ is the least-fixed-point / unbounded-search operator — the same power as the [[lambda-calculus|Y combinator]]. Everything computable, and not one bit more, lives here.