Are all URM computable functions recursive? (Part 3)

Let's just summarise here. We know that primitive recursive functions are URM-computable in which case the set of primitive recursive functions is countably infinite. Previously we saw that the set of all functions is not countably infinite and so not all functions are primitive recursive. In the opening to unit ML3 of the mathematical logic course it is shown, using the diagonal argument again, that not all URM-computable functions are primitive recursive.

The key to progress in understanding the relationship between recursive functions and URM programs is to realise that not all programs halt for a given input (that is reach the stage where there are no more instructions to process and an output is obtained). Some can loop round indefinitely and never reach an instruction that points outside of the program. To incorporate this into our idea of recursive functions, partial functions are introduced. A URM program computes a partial function f if for a given input, the program either halts and produces the output of f or it does not halt and f is undefined.

This either finding an output or not is equivalent to unbounded searches and the new process that is introduced is called minimisation (previously we had bounded minimisation). A new definition of recursive function is introduced (as opposed to primitive recursive) which says that a function is recursive if it can be obtained from basic primitive recursive functions using the operations of substitution, primitive recursion and minimisation on a function a finite number of times.

This allows us to finally answer the question that we originally asked. Are all URM-computable functions recursive? The answer is yes! This is part of the course that I think I really understood. The reason is relatively simple (although the proof was quite long and only sketched out); if you are at a particular stage of processing a URM program you can always determine what instruction you should process next based on the current values in the registers and what the current instruction says you should do. Unless you are at a jump instruction the next instruction to process is the one following the one you are at. Jump instructions depend on the contents of the registers. The key is that you can again provide a code number for all these situations of the program (imagine the trace table and a code that went with each entry in the table). This is clearly a recursive process except that, as we have said, an output may or may not be defined.

The chapter goes on to discuss Kleene's Normal Form Theorem, a consequence of which is that each recursive function can be obtained from the basic primitive recursive functions using the operations of substitution, primitive recursion and at most one minimisation on a function. The discussion was then broadened to Church's Thesis which says that the notion of an algorithmically computable function coincides with that of a recursive function. This is not a mathematical theorem but a statement that is believed to be true. Finally, algorithmically undecidable problems were looked at and this is where I came close to chucking the book out of the window. I struggled with some of these proofs.