Mu Recursion

The next topic in our discussion of Chaitin's number is Recursion Theory- another topic I don't talk about much on this blog. Recursion Theory is concerned with (possibly partial) functions from natural numbers to natural numbers. The recursive functions are those functions which are computable by a Turing Machine, and all Turing Machines can be expressed (albeit indirectly) by some (Mu) recursive function. Like the Lambda Calculus, this is just one more way to talk about computation- many systems give rise to computation, and they all share some overarching properties while differing in the details.

More formally, a function from natural numbers to natural numbers (N^m -> N with m a natural number) is called primitive recursive if it can be expressed using the following rules. The function plus(n, m) = n+m is primitive recursive (addition is clearly computable). A function that selects a one of its arguments fi(x0, x1, ..., xn) = xi for 0 <= i <= n is computable (sometimes called a projection because it is suggestive of projecting the first or second number in a coordinate on a plane to its axis). A function f that takes k arguments along with m functions of k arguments can be used to construct a function of k arguments as h(x0, x1, ..., xk) = f(g0(x0, x1, ..., xk), g1((x0, x1, ..., xk), ..., gm(x0, x1, ..., xk)). No function is primitive recursive if it can't be described using the facts just stated.

Many functions can be described using only the rules given so far, despite possibly seeming restrictive. However, there are functions that can be computed by a Turing Machine that aren't in the set of primitive recursive functions- this type of function is not quite powerful enough. We need one more rule to get all the power we need (and all the power possible- this will give us the full power of universal computation). This rule is often rewritten as Mu, which I will write as u, and is given as follows: for a function f that takes k+1 arguments, we construct the function uf(x1, x2, ..., xk) = z such that z is the smallest number such that f(x, x1, x2, ..., xk) = 0. I find this last rule less intuitive than the previous ones, but it isn't so bad when you get to know it.

Consider trying to compute the mu function for some easily computable function f. We have some fixed inputs that we where given and we want to find some small number that causes f to be 0 when given this number and all the fixed inputs. Clearly we would start with 0, compute the result, and if the result was itself 0, we would be done. If not we would try 1, than 2, than 3, and so on. If we found a number that resulted in a 0 we would be done, but if no number exists than we would be searching forever. This is the reason that mu brings us from the primitive recursive functions, whose computation always halts, to the full power of computation where we may have some function and some inputs that can't be calculated (their calculation will not halt).