# Definition:URM Computability

It has been suggested that this page be renamed.In particular: URM ComputableTo discuss this page in more detail, feel free to use the talk page. |

This page has been identified as a candidate for refactoring of basic complexity.Until this has been finished, please leave
`{{Refactor}}` in the code.
Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Refactor}}` from the code. |

## 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 and only if:

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

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

- the output fails to equal $\map f {n_1, n_2, \ldots, n_k}$
- 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 and only 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 and only if:

- For all ordered $k$-tuples $\tuple {n_1, n_2, \ldots, n_k} \in \N^k$:

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 and only if its characteristic function $\chi_A$ is a URM computable function.

### Relation

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

Then $\RR$ is a **URM computable relation** if and only if its characteristic function $\chi_\RR$ is a URM computable function.