Recursive Function is URM Computable

Theorem

Every recursive function‎ is URM computable.

Proof

From:

• Functions obtained by minimization from URM computable functions are URM computable;
• Functions obtained by minimization from URM computable relations are URM computable;
• Functions obtained by primitive recursion from URM computable functions are URM computable;
• Functions obtained by substitution from URM computable functions are URM computable;
• Primitive Recursive Function is URM Computable;
• Primitive Recursive Relation is URM Computable;

it follows that all the functions obtained from the basic primitive recursive functions using the operations of substitution, primitive recursion and minimization (on a function or a relation) are URM computable.

$\blacksquare$