So, I'm continuing on with this computability text by Cutland, and I've reached the Ackermann function. Cutland says he will give a more rigorous proof that the function is computable later on, but gives a "sketch" of a proof in the meantime. Well, half of it makes sense to me, bits of it make no sense to me whatsoever. Here's the full thing:
"The function given by the following equation is computable:
$\psi(0, y) = y + 1,$
$\psi(x + 1, 0) \simeq \psi(x, 1),$
$\psi(x + 1, y + 1) \simeq \psi(x, \psi(x + 1, y)).$
To show rigorously that $\psi$ is computable is quite difficult. We sketch a proof using the idea of a suitable set of triples S. The essential property of a suitable set S (defined below) is that if $(x, y, z)\in S$, then
(5.6)
(i) $z = \psi(x, y)$
(ii) S contains all the earlier triples $(x_1, y_1, \psi(x_1, y_1))$ that are needed to calculate $\psi(x, y)$.
Definition A finite set of triples S is said to be suitable if the following conditions are satisfied:
(a) if $(o, y, z)\in S$ then $z = y + 1$,
(b) if $(x + 1, 0, z) \in S$ then $(x, 1, z) \in S$,
(c) if $(x + 1, y + 1, z) \in S$ then there is $u$ such that $\psi(x + 1, y, u) \in S$ and $(x, u, z) \in S$.
These three conditions correspond to the three clauses in the definition of $\psi$: for instance, (a) corresponds to the statement: if $z = \psi(0, y)$, then $z = y + 1$; (c) corresponds to the statement: if $z = \psi(x + 1, y + 1)$, then there is $u$ such that $u = \psi(x + 1, y)$ and $z = \psi(x, u)$. The definition of a suitable set $S$ ensures that (5.6) is satisfied...
Now a triple $(x, y, z)$ can be coded by the single positive number $u = 2^x \times 3^y \times 5^y$; a finite set of positive numbers {$u_1, u_2, ..., u_k$} can be coded by the single number $p_{u_1}\times p_{u_2} \times ... \times p_{u_k}$ [where $p_n$ is the $n^{th}$ prime number]. Hence a finite set of triples can be coded by a single number $v$ say. Let $S_v$ denote the set of triples coded by the number $v$. Then we have:
$(x, y, z) \in S_v \Leftarrow\Rightarrow p_{2^x \times 3^y \times 5^z}$ divides $v$ [the predicate '$x$ divides $y$' was shown to be decidable earlier on in the text].
So '$(x, y, z) \in S_v$' is a decidable predicate of $x, y, z, v$; and if it holds, then $x, y, z < v$. Hence, using the techniques and functions of earlier sections we can show that the following predicate is decidable:
$R(x, y, v) \equiv$ '$v$ is the code number of a suitable set of triples and $\exists z<v((x, y, z) \in S_v)$.'
Thus the function:
$f(x, y) = \mu vR(x, y, v)$
is a computable function that searches for the code of a suitable set containing $(x, y, z)$ for some $z$. Hence:
$\psi(x, y) = \mu z((x, y, z) \in S_{f(x, y)})$
Which shows that $\psi$ is computable."
Alright, that was all from the text Computability: An introduction to Recursion Theory, by Cutland. I'm pretty sure that I understand most of this section but I'm just having trouble with the very last step and I'd be very grateful if someone could help me out:
$\psi(x, y) = \mu z((x, y, z) \in S_{f(x, y)})$
I just have no idea as to what is denoted by $S_{f(x, y)}$ and therefore, obviously, am having trouble understanding how $\mu z((x, y, z) \in S_{f(x, y)})$ follows from the earlier steps. Otherwise, I'm pretty sure I get the whole thing, so to be stopped short at the very end is enormously frustrating. Please help!
See if this helps.
We have the computable function $f(x,y)=\mu v\,R(x,y,v)$ that returns the least $v$ that makes the following statement true:
That is, $f(x,y)$ is the least $v$ making the previous statement true. This means that $f(x,y)$ is the smallest natural number such that
By the definition of $f(x,y)$ we know that there is a $z<f(x,y)$ such that $\langle x,y,z\rangle\in S_{f(x,y)}$, so there is a least such $z$, and we define $\psi(x,y)$ to be that least $z$:
$$\psi(x,y)=\mu z(\langle x,y,z\rangle\in S_{f(x,y)})\;.$$
As was explained at the beginning, the definition of suitable set of triples then ensures that this function $\psi$ really is the Ackermann function as it was originally defined by recursion.