Primitive Recursive Function is URM Computable
Jump to navigation
Jump to search
Theorem
Every primitive recursive function is URM computable.
Proof
This follows immediately from:
- The fact that the basic primitive recursive functions are URM computable;
- Functions obtained by substitution from URM computable functions are URM computable;
- Functions obtained by primitive recursion from URM computable functions are URM computable;
- The definition of primitive recursive function.
$\blacksquare$
Note
This does not mean that every URM computable function is necessarily primitive recursive.