Single Instruction URM Programs/Successor Function

From ProofWiki
Jump to navigation Jump to search


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.


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.