Prefix-free Universal Computable Functions

Next on the agenda is prefix-free universal computable functions. First I will talk about universal functions.

A function F (from N->N, taking a natural number and returning a natural number) is called universal if there is some way to encode any other function f and an input to f, call it x, such that when passed to F we get F(f, x) = f(x). Another way to think of this is to encode f and x, concatenate them and pass them to F as F(f ++ x) (using Haskells "++" for concatenation). This makes F a function of one variable that can perform the action of any other function. In other words, this type of function has the same place in recursion theory as a Universal Turing Machine has in automata theory- it shows that there are things in the theory which in some sense encode every other object in the theory, so that the theory contains itself. This kind of self reference appears to be essential to computation and we see it everywhere, the simplest example being in how programs are stored in memory the same way data is- things that compute can generally take encodings of other ones and run them.

A prefix-free code is a fairly simple concept. Given some set of symbols, a prefix free encoding is a set of strings of symbols such that for every pair of strings, neither is a prefix of the other. One example of such a code would be the following encoding of the natural numbers- e(0) = 1, for all n of the form k+1 e(n) = 0 ++ e(k). Written out this would look like {1, 01, 001, 0001, 00001, 000001, ...}, where every natural number n is encoded by n zeros followed by a one. Clearly no number encodes a string that is a prefix of another's encoding, as for that to happen an encoding would have to share each symbol with the symbol in the corresponding location in another string, but all strings longer then a given string (so that they may have the string as a prefix) will have a 0 in the only place the string has a 1, causing it to fail to be a prefix of the longer string.

So, what is a prefix-free universal computable function? This is a universal function whose domain (the numbers for which it is defined) is a prefix-free code. In other words, this allows us to distinguish between the function f encoded as input to the universal function F and the input to f, as we always know when a string ends in a prefix-free code.

There is another piece here- Chaitin's number is best described as having to do with infinite bit streams. However, the part of each stream we are interested in is finite, and we need a way to know where the interesting part of the stream ends. For this reason, we decode the bits of the stream as a prefix-free code, and we them know where to finish looking for the interesting portion.

Thats enough of that for now.