2

I'm working through Cutland's Computability. Problem 4.4.5 says:

Show that for each $m$ there is a total ($m+1$)-ary computable function $s^m$ such that for all $n$, $$\phi_{e}^{(m+n)} (\textbf{x},\textbf{y}) \simeq \phi_{s^{m}(e,\textbf{x})}^{(n)}(\textbf{y})$$ where $\textbf{x},\textbf{y}$ are $m,n$ tuples.

It also wants me to show that $s^m$ is primitive recursive.

Now the s-m-n theorem states the existence of a primitive recursive $s^m_n$ such that: $$\phi_{e}^{(m+n)} (\textbf{x},\textbf{y}) \simeq \phi_{s^{m}_{n}(e,\textbf{x})}^{(n)}(\textbf{y})$$ which is significant because for any given $n$ we can write a program that effectively shifts the $n$-tuple $\textbf{y}$ right by $m$, inserts $\textbf{x}$, and runs the program encoded by $e$ on this new input $\textbf{x},\textbf{y}$.

But the problem wants me to find some general $s^m$ that will work regardless of the input size $n$. A hint is given, along the lines of: "Use the fact that $\rho(P_e)$, the maximum space accessed by the $e$-th program, is independent of $n$, and that the output depends only on what's inside the registers $1,2,3, ... , \rho({P_e})$ to begin with."

I think the idea is to simply shift every single block used by the program ($1, 2, ... \rho(P_e)$) up by $m$ and inject $\textbf{n}$ in the style of the proof of s-m-n theorem. But this requires actually finding this value $\rho(P_e)$, and I'm not sure if that's doable, primitive recursively at least. It feels like I would need unbounded search for that, making it not primitive recursive. Am I on the right track here?

Luke
  • 344

1 Answers1

1

The input for $s^m$ is really just a program, $p$. We can examine at $p$ directly to compute $r(p)$, the maximum register number used anywhere inside $p$. Registers that are "used" in this sense need not be used as inputs; they can be used at any stage of the program in any way. So we can determine $r(p)$ in a primitive recursive way by just listing all the register numbers mentioned anywhere in the program.

It is important here that Cutland's register machines, like most register machines (but unlike real CPUs), hard-code the register numbers to be used in each instruction. There is no "indirect addressing" in which an instruction can say something like "look in register 4, and then add 1 to the register whose number is stored there", nor "look in register 8 and then jump to the instruction whose number is stored there". Each instruction directly tells which registers are relevant to evaluating that instruction.

Now, even though not all $r(p)$ registers need to be viewed as inputs of $p$, is certainly true that the result of the program is only dependent on the contents of those registers. So the number of inputs actually used by program $p$ is not more than $r(p)$. Any further inputs are, essentially, ignored by $p$, and so they can be ignored by $s^m(p)$.

So, in the new program $s^m(p)$, we first shift the values of registers $1, 2, \ldots, r(p)$ into registers $m+1, m+2, \ldots, m+r(p)$. Then we copy specific values into registers $1$, ..., $n$, as usual.

Carl Mummert
  • 81,604
  • Thanks for the help, this was indeed the idea I was thinking about. The only problem now, though, is understanding how $r(p)$ is primitive recursive. I don't think it actually is, since it requires knowing how long a program is... if you could find $r(p)$ primitive recursively, I suspect you could also find the max component of any tuple in $\bigcup_{k>0} \mathbb{N}^{k}$ primitive recursively... – Luke Nov 01 '16 at 17:03
  • Yes, it should be perfectly fine to compute the maximum index of a tuple as a function of the tuple. What coding of tuples were you imagining in which that would not be possible? – Carl Mummert Nov 01 '16 at 19:56
  • This is the coding Cutland gives: $\tau (\textbf{x}) = 2^{x_1} + 2^{x_1+x_2 + 1} + 2^{x_1+x_2+x_3+2} + ... + 2^{x_1+x_2+...+x_k + k-1}$. It seems like I would need to "know" how long the tuple is to actually scan through it with a bounded search. Besides that, I can't seem to find an explicit, primitive recursive formula for it, either. – Luke Nov 02 '16 at 05:39
  • 1
    Remember that you have the input $\tau(x)$ itself as a number, and so you can use that to compute bounds. The largest power of $2$ less than a number $n$ can be found by a bounded search using a primitive recursive predicate ("power of 2") and a bound of $n$. Writing out all of the recursion equations would be a lengthy process. – Carl Mummert Nov 02 '16 at 10:20
  • Here is a description of how to find $x_1$ given $n = \tau(x)$: first, test if the $n$ is odd, then see if it is a multiple of $2$ but not a multiple of $4$, then see it is a multiple of $4$ but not a multiple of $8$, etc. Once you find the first of these powers of $2$ that works, you know $x_1$. The search will be bounded by $n$ steps: $2^n > n$. Now to find $x_2$, first subtract $2^{x_1}$ from $n$, then repeat the process. The first power that works is $2^{x_1 + x_2+1}$, so subtracting $x_1 + 1$ gives $x_2$. In this way, with a primitive recursion you can extract all the components of $x$. – Carl Mummert Nov 02 '16 at 10:27