Are all URM computable functions recursive? (Part 2)

This is where ML2 becomes more interesting. So far it had been shown that all primitive recursive functions are URM-computable. But are all URM-computable functions primitive recursive? Are there any functions of any sort that are not primitive recursive?

To answer this question required a diversion into infinite sets and Cantor's theory of countably infinite sets. This is the rather neat idea that a set is countably infinite if you can find a one-to-one correspondence between it and the set of natural numbers {0, 1, 2, 3, ...}. So, rather bizarrely, the set of even numbers {0, 2, 4, ...} is countably infinite since there is a one-one function f(n)=n/2 that maps the even numbers to the natural numbers. In fact, any infinite subset of the natural numbers is countably infinite.

Now the text goes on to show how we can assign each URM program a unique code number using the properties of prime numbers. Recall that the fundamental theorem of arithmetic means that a given natural number can only be written as positive powers of primes in one way. So, by assigning each instruction in a program a unique positive number (also referred to as a code number) and then creating a new number which is a product of primes raised to the power of these instruction numbers, then each program can be assigned a unique code number drawn from the set of natural numbers. So, of course, this subset is countably infinite. The advantage is that given a code number, we can recover the program uniquely.

So we come to the question as to whether there are any functions of any sort which are not primitive recursive. Here we use a diagonal argument of Cantor's (the same one he used to show that the set of real numbers is not countably infinite) to show that there are, i.e. that the set of functions is not countably infinite (as the set of primitive recursive functions is).

The rest of unit ML2 works towards proving that the set Prog of code numbers of URM programs is primitive recursive. This involves showing that the characteristic function of the set of prime numbers, the function p which enumerates the prime numbers and the set Instr of code numbers of URM instructions are all primitive recursive. The function p that enumerates the primes is simply the one that says, for example, that the 4th prime number is 7, i.e. that P(4)=7. The important concepts of bounded minimisation on a function or a relation are introduced. This is the the process of looking for a minimal solution of a function within a bounded (i.e. known) range.

So what does it mean to say that the set Prog of code numbers of URM programs is primitive recursive? I think it means that there is a primitive recursive function that can determine what these code numbers are and that in turn means that such a function is URM-computable, i.e. that there is a URM program that can compute them.