Definition:URM Computability

Definition

Let $P$ be a URM program, and let $k$ be any positive integer.

Program

$P$ is said to compute the function $f: \N^k \to \N$ if:

for all ordered $k$-tuples $\left({n_1, n_2, \ldots, n_k}\right) \in \N^k$, the computation of a URM using the program $P$ with input $\left({n_1, n_2, \ldots, n_k}\right)$ produces the output $f \left({n_1, n_2, \ldots, n_k}\right)$.

If there are any inputs such that either of the following happens:

• the output fails to equal $f \left({n_1, n_2, \ldots, n_k}\right)$;
• the program will never terminate,

then the program does not compute the function $f: \N^k \to \N$.

Function

The function $f: \N^k \to \N$ is said to be URM computable if there exists a URM program which computes it.

Partial Function

$P$ is said to compute the partial function $f: \N^k \to \N$ if:

For all ordered $k$-tuples $\left({n_1, n_2, \ldots, n_k}\right) \in \N^k$:

• If the computation of $P$ with input $\left({n_1, n_2, \ldots, n_k}\right)$ halts, it produces the output $f \left({n_1, n_2, \ldots, n_k}\right)$.

• If the computation of $P$ with input $\left({n_1, n_2, \ldots, n_k}\right)$ does not halt, $f \left({n_1, n_2, \ldots, n_k}\right)$ is undefined.

The partial function $f: \N^k \to \N$ is said to be URM computable if there exists a URM program which computes it.

Note that a URM program can be used with any number of input variables. For any positive integer $k$, the input consists of the state of the registers $R_1, R_2, \ldots, R_k$.

Thus a given URM program $P$ computes a partial function $f: \N^k \to \N$ for each positive integer $k$.

In this context, it is convenient to use the notation $f^k_P$ to denote the partial function of $k$ variables computed by $P$.

Set

Let $A \subseteq \N$.

Then $A$ is a URM computable set if its characteristic function $\chi_A$ is a URM computable function.

Relation

Let $\mathcal R \subseteq \N^k$ be an $n$-ary relation on $\N^k$.

Then $\mathcal R$ is a URM computable relation iff its characteristic function $\chi_\mathcal R$ is a URM computable function.