State Code Function is Primitive Recursive

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $k \in \N^*$.

Let $e = \map \gamma P$ be the code number of a URM program $P$.

Let $\tuple {n_1, n_2, \ldots, n_k}$ be the input of $P$.


Let $S_k: \N^{k + 2} \to \N$ be the function defined as:

$\map {S_k} {e, n_1, n_2, \ldots, n_k, t}$ is the state code for $P$ at stage $t$ of computation of $P$.

If $e$ does not code a URM Program then $S_k = 0$.

Also, if $P$ terminates at stage $t_0$, then we put:

$\forall t > t_0: \map {S_k} {e, n_1, n_2, \ldots, n_k, t} = \map {S_k} {e, n_1, n_2, \ldots, n_k, t_0}$


Then for all $k \ge 1$, the function $S_k$ is primitive recursive.


Proof

It can easily be seen that $S_k$ is a total function.

Suppose $e = \map \gamma P$ for some URM program $P$.

At stage $0$, we are about to carry out instruction $1$ with the input $\tuple {n_1, n_2, \ldots, n_k}$.

So we have:

$\map {S_k} {e, n_1, n_2, \ldots, n_k, 0} = \begin{cases}

2^1 3^{n_1} 5^{n_2} \cdots p_{k + 1}^{n_k} & : e \in \operatorname{Prog} \\ 0 & : \text{otherwise} \end{cases}$ where $\operatorname{Prog}$ is the set of code numbers of all URM programs.

We see that $\map {S_k} {e, n_1, n_2, \ldots, n_k, 0}$ does not actually depend upon the actual program being run, beyond the fact that it matters whether it actually is a program or not.


Now $\operatorname{Prog}$ is a primitive recursive set.

So from results about primitive recursive functions, the relations defining the cases are primitive recursive.

We can also deduce from various results about primitive recursive functions that the functions given by the formulas $2^1 3^{n_1} 5^{n_2} \cdots p_{k + 1}^{n_k}$ and $0$ are primitive recursive.

In particular, we use the results:

So from Definition by Cases is Primitive Recursive, $\map {S_k} {e, n_1, n_2, \ldots, n_k, 0}$ is primitive recursive.


Now we want to be able to express $\map {S_k} {e, n_1, n_2, \ldots, n_k, t + 1}$ in terms of $e, \tuple {n_1, n_2, \ldots, n_k}, t$ and $\map {S_k} {e, n_1, n_2, \ldots, n_k, t}$ using known primitive recursive functions.

We need to consider a number of cases:

  1. $e$ does not code a URM program;
  2. $e = \map \gamma P$ and the computation halts at stage $t$ or earlier;
  3. $e = \map \gamma P$ and the instruction to be carried out at stage $t$ is a Zero instruction;
  4. $e = \map \gamma P$ and the instruction to be carried out at stage $t$ is a Successor instruction;
  5. $e = \map \gamma P$ and the instruction to be carried out at stage $t$ is a Copy instruction;
  6. $e = \map \gamma P$ and the instruction to be carried out at stage $t$ is a Jump instruction.

These cases are clearly mutually exclusive and exhaustive.


First we need to check that each case corresponds to a primitive recursive relation.

So 1. is a primitive recursive relation.


  • So we have that $e$ codes a URM program. Call that program $P$.

From the definition of state code, we see that if a computation halts at stage $t$ or earlier, then the number of the instruction to be carried out at stage $t$ is greater than the number of instructions in $P$.

From the definition of the code number of $P$, the number of instructions in $P$ is $\map \len e$ where $\map \len e$ is the length of $e$, which is primitive recursive.

Now let $r = \map {S_k} {e, n_1, n_2, \ldots, n_k, t}$.

Let $\tuple r_j$ be defined as the prime exponent function.

By the definition of the state code, the number of the instruction to be carried out at stage $t$ is $\tuple r_1$, which is primitive recursive.

So 2. can be expressed as:

$e \in \operatorname{Prog} \text { and } \tuple {\map {S_k} {e, n_1, n_2, \ldots, n_k, t} }_1 > \map \len e$

Both $\operatorname{Prog}$ and $\tuple r_1$ are primitive recursive, so from Set Operations on Primitive Recursive Relations, 2. is a primitive recursive relation.


  • So, let the number of the instruction to be carried out at stage $t$ be $a = \tuple {\map {S_k} {e, n_1, n_2, \ldots, n_k, t} }_1$.

From the definition of the code number of $P$, the code number of this instruction is $\tuple e_a$.

Now from Set of Codes for URM Instructions is Primitive Recursive, each of the sets $\operatorname{Zinstr}$, $\operatorname{Sinstr}$, $\operatorname{Cinstr}$ and $\operatorname{Jinstr}$ are primitive recursive.

So each of 3. to 6. above can be expressed as:

$e \in \operatorname{Prog} \text { and } a \le \map \len e \text { and } \tuple e_a \in \operatorname{Instr}$

and is a primitive recursive relation.


So relations 1. to 6. are all primitive recursive.


Now we need to show how, in each case, $\map {S_k} {e, n_1, n_2, \ldots, n_k, t + 1}$ can be obtained from $e, \tuple {n_1, n_2, \ldots, n_k}, t$ and $\map {S_k} {e, n_1, n_2, \ldots, n_k, t}$ using known primitive recursive functions.


First, if $e$ does not code a URM program then $\map {S_k} {e, n_1, n_2, \ldots, n_k, t + 1} = 0$, which is primitive recursive.


Second, we have adopted the convention that if $P$ has halted, then $S_k$ does not change.

So if $P$ halts at or before stage $t$, we have that $\map {S_k} {e, n_1, n_2, \ldots, n_k, t + 1} = \map {S_k} {e, n_1, n_2, \ldots, n_k, t}$


Next, we look at the individual commands.

As an example we will investigate the Successor command. The others are treated similarly.


Suppose the instruction to be carried out at stage $t$ is a Successor command.

We know that the code number $c$ is given by $c = \tuple e_a$ where $a = \tuple {\map {S_k} {e, n_1, n_2, \ldots, n_k, t} }_1$.

Suppose the instruction is $\map S n$.

Then $c = 6 n$.

So $n = \map {\operatorname{quot} } {6, n}$ which is recursive from Quotient is Primitive Recursive.

This instruction adds $1$ to the number in $R_n$.

This increases the exponent $p_{n + 1}$ in the state code by $1$.

This is achieved by multiplying $\map {S_k} {e, n_1, n_2, \ldots, n_k, t}$ by $\map p {n + 1}$, where $\map p {n + 1}$ is the prime enumeration function which is primitive recursive.

Since the instruction to be carried out at stage $t$ is a Successor the instruction number at stage $t+1$ is $a+1$ so the factor $2^a$ in $\map {S_k} {e, n_1, n_2, \ldots, n_k, t}$ is replaced by $2^{a + 1}$.

So:

$\map {S_k} {e, n_1, n_2, \ldots, n_k, t + 1} = 2 \times p_{n + 1} \times \map {S_k} {e, n_1, n_2, \ldots, n_k, t}$

where:

$n = \map {\operatorname{quot} } {6, n}$
$c = \tuple e_a$
$a = \tuple {\map {S_k} {e, n_1, n_2, \ldots, n_k, t} }_1$

This is the required expression for $\map {S_k} {e, n_1, n_2, \ldots, n_k, t + 1}$ obtained by substitution from primitive recursive functions.


The proofs for $\operatorname{Zinstr}$, $\operatorname{Cinstr}$ and $\operatorname{Jinstr}$ are along the same lines.

In each case, the value of $\map {S_k} {e, n_1, n_2, \ldots, n_k, t + 1}$ can be obtained by substitution from primitive recursive functions (but I'd hate to have to do the calculations on my fingers).


Thus by Definition by Cases is Primitive Recursive, $\map {S_k} {e, n_1, n_2, \ldots, n_k, t + 1}$ is primitive recursive.


Hence $S_k$ is defined by primitive recursion from functions known to be primitive recursive.

Hence the result.

$\blacksquare$


Note

The function $S_k$ starts with an arbitrary sequence of numbers $\tuple {e, n_1, n_2, \ldots, n_k, t}$.

If it so happens that $e$ is the code of some program $P$, then $\tuple {n_1, n_2, \ldots, n_k}$ are taken to be the state of $R_1, R_2, \ldots, R_k$ before $P$ starts executing.

Then we determine what would happen when $P$ is left to run for $t$ stages (during which time it may have terminated).

Then we examine the state of $P$ at that point.

Then we calculate the state code for that state, and output it.


Of course, if $e$ does not actually code any program, then we fall at the first fence and output zero.

Retrieved from "https://proofwiki.org/w/index.php?title=State_Code_Function_is_Primitive_Recursive&oldid=685017"