Are all URM-computable functions recursive? (Part 1)

I have just got to that point in ML3 of M381 where this question has been answered affirmatively and it has been an interesting read getting there. I can't help feeling that this is really important but as yet I haven't understood all the implications of the theory. Before I forget I will try and outline how we arrived at that point by way of a summary, so I don't forget the basic ideas.

What is a URM-computable function? A URM is an unlimited register machine and a URM-computable function is a function that can be computed by such a machine (in other words the machine and the function produce the same output for the same given input). So what is it? Well, its a theoretical computer that can process a program with a very limited set of instructions (4 in fact) but has an unlimited (but finite) set of registers in which to store numbers (the integers 0, 1, 2, ...). The four instructions are Z(n) (Zero n; replace the number in register n by 0), S(n) (Successor n; add 1 to the number in register n), C(m,n) (Copy m to n; copy the number in register m to register n) and J(m,n,q) (Jump m, n, q; jump to instruction q if the numbers in register m and n are equal, otherwise go to the next instruction).

ML1 deals with some simple functions of two variables that can be computed by such machines; add, multiply, max, min etc. by showing how they can be programmed directly. However, the focus of the investigations is to find new ways of creating URM-computable functions by building them up from more basic functions. Firstly it is shown how programs can be concatenated by placing one program after another, so that the output of one becomes the input for another. Then, using this technique, two important theorems are proved - that new URM-computable functions can be obtained from existing ones by substitution and primitive recursion. For substitution, the new URM-computable function is obtained from existing ones by substituting URM-computable functions for the inputs of another. For primitive recursion, a sequence of new URM-computable functions are obtained by basing each new function on the previous one, which is again a form of substitution and requires two URM-computable functions 'to start the process off'.

The more interesting and, at times, difficult material appears in unit ML2. As said before, instead of programming functions directly, new URM-computable functions are obtained from existing ones by substitution and primitive recursion. The basic URM-computable functions considered were the zero, successor and projection functions which are the one-line programs containing the instructions Z(1), S(1) and C(m,1), respectively. Confusingly, perhaps, these are called the basic primitive recursive functions. Another function is said to be primitive recursive if it can be obtained from these basic ones by substitution and primitive recursion a finite number of times. ML2 goes on to show how more and more complicated primitive recursive functions can be obtained from these basic ones.

An important idea was introduced as to how to define such functions by cases. This is of the form 'if such and such is true then the function has this form, but if this is true then it has this form'. This required a detour into characteristic functions of sets and relations and determining if such functions are primitive recursive. This culminated in a proof that a function defined by cases is primitive recursive if the functions and relations that defined it (i.e. the cases) were primitive recursive.