(Notes from Chapter 5, Sections 1 - 3)
Let \(A\) be an \(n\)-symbol alphabet \(\{s_1,\ldots,s_n\}\). The string \(w = s_{i_k} s_{i_{k-1}} \cdots s_{i_1} s_{i_0}\) is associated with the integer \[x = i_k \cdot n^k + i_{k-1}\cdot n^{k-1} + \cdots + i_1 \cdot n + i_0.\] The null string \(w = 0\) is associated with the number \(0\). Note that \(0\) is the number for the null string no matter the size of the alphabet.
Given \(x \neq 0\), each of the subscripts \(i_0,\ldots, i_k\) can be extracted by a primitive recursive function.
Recall that \(R(x,y)\) is the remainder of \(x\) divided by \(y\).
Define \[R^+(x,y) = \left \{ \begin{array}{ll} y & \text{if } y \mid x \\ R(x,y) & \text{otherwise}, \end{array}\right .\] \[Q^+(x,y) = \left \{ \begin{array}{ll} \left \lfloor \frac{x}{y}\right \rfloor~\dot{-}~1 & \text{if } y \mid x \\ \left \lfloor \frac{x}{y}\right \rfloor & \text{otherwise}, \end{array}\right .\] and \begin{eqnarray*} g(0,n,x) & = & x \\ g(m+1,n,x) & = & Q^+(g(m,n,x),n). \end{eqnarray*}
Then letting \[h(m,n,x) = R^+(g(m,n,x),n),\] we have \[i_m = h(m,n,x),~~~~~m = 0,1,\ldots, k.\]
To determine the length \(k\) of the string encoded by the number \(x\), it suffices to determine the smallest number that encodes a string of \((k+1)\)-symbols. That number is \(\displaystyle\sum_{j=0}^k n^j\) encoding the string \(s_1^{[k+1]}\). Hence, the function \[\lvert x \rvert = \min_{k \leq x} \left [ \sum_{j=0}^k n^j \gt x \right ]\] gives the length of the string encoded by \(x\).
The following are all primitive recursive:
\(\textbf{concat}_n(u,v) := u\cdot n^{|v|} + v\) gives the number represented by the string \(uv\), the string obtained from concatenating \(u\) and \(v\), in base \(n\).
\(\textbf{concat}_n^m(u_1,\ldots,u_m)\) gives the number represented by the string \(u_1\cdots u_m\).
\(\textbf{rtend}_n(w) := h(0,n,w)\) gives the rightmost symbol of the string \(w\).
\(\textbf{ltend}_n(w) := h(|w|~\dot{-}~1,n,w)\) gives the lefttmost symbol of a given nonempty string \(w\).
\(\textbf{rtrunc}_n(w) := g(1,n,w)\) gives the result of removing the rightmost symbol from a given nonempty string \(w\).
\(\textbf{ltrunc}_n(w) := w~\dot{-}~i_k \cdot n^k\) gives the result of removing the leftmost symbol of a given nonempty string \(w\).
We now define two functions that we need in Section 6 of Chapter 5.
Let \(1 \leq n \lt l\).
Let \(A \subset \tilde{A}\) where \(A\) is an alphabet of \(n\) symbols and \(\tilde{A}\) is an alphabet of \(l\) symbols.
For any \(x\in \mathbb{N}\), let \(w\) be the string in \(A^*\) representing \(x\) in base \(n\). We write \[\textbf{upchange}_{n,l}(x)\] for the number that \(w\) represents in base \(l\).
Now any \(x\in \mathbb{N}\), let \(w\) be the string in \(\tilde{A}^*\) representing \(x\) in base \(l\). Let \(w'\) be obtained from \(w\) by removing all the symbols that are not in \(A\). Then \(w' \in A^*\) and we write \[\textbf{downchange}_{n,l}(x)\] for the number that \(w'\) represents in base \(n\).
Theorem 1.1 The functions \(\textbf{upchange}_{n,l}\) and \(\textbf{downchange}_{n,l}\) are computable.
Input variables: \(X_1,X_2,X_3,\ldots\)
Output variable: \(Y\)
Local variables: \(Z_1,Z_2,Z_3,\ldots\)
Labels: \(A_1,B_1,C_1,D_1,E_1,A_2,B_2,C_2,D_2,E_2,A_3,\ldots\)
the subscript 1 is often omitted; i.e. \(X\) means \(X_1\), \(Z\) means \(Z_1\), \(A\) means \(A_1\).
\(Y\) and the local variables have initial value 0.
The value of a variable is written in lowercase italics. e.g. \(x_5\) is the value of \(X_5\).
We have the following statements:
| Statement | Interpretation |
|---|---|
| \(V \leftarrow \sigma V\) | Place the symbol \(\sigma\) to the left of the string which is the value of \(V\) |
| \(V \leftarrow V^-\) | Delete the final symbol of the string which is the value of \(V\). If the value of \(V\) is 0, leave it unchanged. |
| \(\textbf{if } V \textbf{ ends } \sigma \textbf{ goto } L\)
for each symbol \(\sigma\) in the alphabet \(A\) and each label \(L\) |
If the value of \(V\) ends in the symbol \(\sigma\), execute next the first instructon labelled \(L\); otherwise, proceed to the next instruction the value of \(V\) |
\(X \leftarrow s_i X\) is realized numerically by replacing the numerical value \(x\) with \(i\cdot n^{\lvert x \rvert} + x\).
\(X \leftarrow X^-\) is realized numerically by replacing the numerical value \(x\) with \(Q^+(x,n)\).
Checking \(X \textbf{ ends } s_i\) is done by checking \(R^+(x, n) = i\).
An instruction is either a statement or \([L]\) followed by a statement where \(L\) is a label.
A program of \({\cal S}_n\) consist of a list (a finite sequence) of instructions. The length of this list is called the length of the program.
An \(m\)-ary function on \(A^*\) which is computed by a program in \({\cal S}_n\) is said to be partially computable in \({\cal S}_n\).
If the function is total and partially computable in \({\cal S}_n\), it is called computable in \({\cal S}_n\).
Fact. The functions \(x+1\) and \(x~\dot{-}~1\) are computable in \({\cal S}_n\) for every \(n\).
A predicate is said to be computable (or decidable) if it is computable as a Boolean-valued function.
The macro \(\textbf{if } V \neq 0 \textbf{ goto } L\) has the expansion \[ \begin{array}{l} \textbf{if } V \textbf{ ends } s_1 \textbf{ goto } L \\ \textbf{if } V \textbf{ ends } s_2 \textbf{ goto } L \\ \vdots \\ \textbf{if } V \textbf{ ends } s_n \textbf{ goto } L \\ \end{array} \]
The macro \(V \leftarrow 0\) has the expansion \[\begin{array}{ll} [A] & V \leftarrow V^- \\ & \textbf{if } V \neq 0 \textbf{ goto } A \end{array}\]
The macro \(\textbf{goto } L\) has the expansion \[ \begin{array}{l} Z \leftarrow 0 \\ Z \leftarrow s_1Z \\ \textbf{if } Z \textbf{ ends } s_1 \textbf{ goto } L \end{array} \]
The macro \(V' \leftarrow V\) has the expansion \[ \begin{array}{cll} & Z \leftarrow 0 \\ & V' \leftarrow 0 \\ \begin{array}{l} [A]\end{array} & \textbf{if } V \textbf{ ends } s_i \textbf{ goto } B_i & (1 \leq i \leq n) \\ & \textbf{goto } C \\ \begin{array}{l} [B_i] \\ \\ \\ \\ \end{array} & \left. \begin{array}{l} V \leftarrow V^- \\ V' \leftarrow s_iV' \\ Z \leftarrow s_i Z \\ \textbf{goto } A \end{array} \right\} i = 1,\ldots, n \\ \begin{array}{l} [C]\end{array} & \textbf{if } Z \textbf{ ends } s_i \textbf{ goto } D_i & (1 \leq i \leq n) \\ \begin{array}{l} [D_i] \\ \\ \\ \end{array} & \left. \begin{array}{l} Z \leftarrow Z^- \\ V \leftarrow s_iV \\ \textbf{goto } C \end{array} \right\} i = 1,\ldots, n \\ \end{array}\]
If \(f(x_1,\ldots,x_m)\) is partially computable in \({\cal S}_n\), we permit the use in \({\cal S}_n\) of macros of the form \[V \leftarrow f(V_1,\ldots,V_m).\]
Theorema 3.1. A function is partially computable if and only if it is partially computable in \({\cal S}_1\).
Proof. The languages \({\cal S}\) and \({\cal S}_1\) are essentially the same. The numerical effect of the instructions \[V \leftarrow s_1 V~~~\textbf{and}~~~V \leftarrow V^-\] in \({\cal S}_1\) is the same as that of the corresponding instructions in \({\cal S}\): \[V \leftarrow V + 1~~~\textbf{and}~~~V \leftarrow V~\dot{-}~1.\] The condition “\(V \textbf{ ends } s_1\)” in \({\cal S}_1\) is equivalent to the condition \(V \neq 0\) in \({\cal S}\).
Theorem 3.2. If a function is partially computable, then it is also partially computable in \({\cal S}_n\) for each \(n\).
Later, we will show that if a function is partially computable in \({\cal S}_n\) for any particular \(n\), then it is partially computable in the original sense.