Mu-recursive functions#
Theorem 8
There is a primitive recursive relation of numbers \(T_{numbers}(p,x,z)\) so that for all numbers \(p\) and \(n\),
\(\varphi_p(n)\!\!\downarrow\) if and only if there is some \(z\) such that \(T_{numbers}(p,n,z)\).
Corollary 1
Every 1#-computable function \(f: N\to N\) is \(\mu\)-computable.
Proof. Let \(f:N\to N\) be computable by the program \(p\). So \(f\) is \(\varphi_{s(p)}\). This means that for all numbers \(n\),
If \(f(n)\!\!\downarrow\), then there is some number \(z\) such that \(T_{numbers}(s(p),n,z)\). In this case, we can find \(f(n)\) by looking through all numbers \(z\), starting with \(z =0\), and checking whether or not \(T_{numbers}(s(p),n,z)\). Since \(T_{numbers}\) is primitive recursive, for each \(n\) we do get a value in finite time. If and when we find some \(z\) such that \(T_{numbers}(s(p),n,z)\), we use the \(upshot\) function to give the value of \(\varphi_{s(p)}(n)\). In other words,
We can do all of this with a 1#-program. We use the primitive recursiveness of \(T_{numbers}\).
This equation also holds in the case that \(f(n)\!\!\uparrow\). For this time, we can still look for \(z\) so that \(T_{numbers}(s(p),n,z)\) but we never find one. And so the computation of the program which we defined also goes on forever.
Theorem 8
Every \(\mu\)-computable function \(f: N\to N\) is 1#-computable.
Proof. We use induction on the set of \(\mu\)-computable functions.
We have seen the base cases when we showed that primitive recursive functions are 1#-computable. The induction steps for composition and primitive recursion are basically the same as what we have seen as well. The interesting induction step is for the \(\mu\)-construct. Suppose that
By induction hypothesis, \(g(n,x)\) is 1#-computable. So we have a program \(p\) so that