Single Instruction URM Programs/Successor Function

Theorem

The successor function $\Succ: \N \to \N$, defined as:

$\forall n \in \N: \map \Succ n = n + 1$

is URM computable by a single-instruction URM program.

Proof

The successor function is computed by the following URM program:

Line		Command
$1$		$\map S 1$

The input $n$ is in $R_1$ when the program starts.

The program adds $1$ to $r_1$ and then stops.

The output $n + 1$ is in $R_1$ when the program terminates.

$\blacksquare$