Primitive Recursive Relation is URM Computable

Theorem

Every primitive recursive relation is URM computable.

Proof

This follows immediately from:

• a relation is primitive recursive if its characteristic function is a primitive recursive
• the fact that every Primitive Recursive Function is URM Computable.

$\blacksquare$

Note

This does not mean that every URM computable relation is necessarily primitive recursive.