Defining Partial Recursive Functions with their indices

Question

I am working on learning recursion theory and I would like to know if there is any danger in defining a partial recursive function that uses its own enumeration.

For example:

$h(x) = \begin{cases} n & f(n \cdot x)\downarrow\\ \uparrow & else \\ \end{cases} $

Where n is the enumeration of h (i.e., $\{n\} = h(x)$), and $f$ is some partial recursive function.

Or, even more simply, $$g(x) = k$$

where k is the enumeration index of g (i.e., $\{k\} = g$)

My confusion on this point is whether the enumeration index depends on the function definition, and if there are other ways to enumerate the partial recursive functions so that these function definitions are valid. I am hesitant, as things like in the Gödel coding of sentences, the code/enumeration is dependent on its contents.

Answer 1

Yes, there is a subtlety here - our numbering of partial computable functions has to be sufficiently nice.

First, I'll give the proof that such an $h$ does in fact exist; then I'll talk about the assumption on the numbering of partial computable functions we're using which is needed for this proof to actually work.

---

Proof that your $h$ exists

We use the recursion theorem. Fix a partial computable function $f$. Let $I$ be a total computable function sending each $n$ to an index $I(n)$ for the function $$x\mapsto \begin{cases} n & f(n \cdot x)\downarrow\\ \uparrow & else. \\ \end{cases} $$

By the recursion theorem, there is some $c$ such that $c$ itself is an index for the function

$$x\mapsto \begin{cases} c & f(c \cdot x)\downarrow\\ \uparrow & else. \\ \end{cases} $$

So $c$ is an index for a partial computable function with the desired property.

---

Details of numberings

A numbering $\Phi_-$ is a map sending a natural number $n$ to a partial function $\Phi_n$ (I'm using this notation in place of your $\{n\}$ - it's more modern, and avoids possible confusion with set notation) with the following three properties:

1. Each $\Phi_n$ should be a partial computable function.

2. For each partial computable function $f$ there should be at least one $n$ such that $f\simeq\Phi_n$.

3. The numbering itself should be computable, in the sense that the partial binary function $$(a,b)\rightarrow\Phi_a(b)$$ should itself be computable.

The above properties are what one generally thinks of as constituting Turing completeness of $\Phi_-$. However, it turns out they aren't really enough. For example, consider the following three additional properties:

• Padding property: For each partial computable $f$ there are infinitely many $m$ with $f\simeq \Phi_m$.

• Rice's property: For each set $X\subseteq\mathbb{N}$ such that whenever $\Phi_m\simeq\Phi_n$ we have either $m,n\in X$ or $m,n\not\in X$, either $X=\mathbb{N}$ or $X=\emptyset$ or $X$ is not computable.

• Recursion property: For each total computable $f$ there is some $c\in\mathbb{N}$ such that $\Phi_c\simeq\Phi_{f(c)}$.

These are each pretty fundamental - the third especially so (and as we saw above, it's this property that's needed for the OP specifically).

It turns out that we can find a numbering $\Phi$ which lacks each of the Padding, Rice, and Recursion properties! The standard example of such a horrible beast is a Friedberg numbering; this is a $\Phi$ such that each partial computable $f$ has exactly one $\Phi$-index. It's easy to check that the Padding, Rice, and Recursion properties each fail in a Friedberg numbering. See here for some details and sources.

So in order for a numbering $\Phi$ to actually be useful to us, we need an additional property. It turns out that the key is the following "maximality" property:

4. For every other numbering $\Psi_-$, there is a total computable $f$ such that for each $n$ we have $$\Psi_n\simeq\Phi_{f(n)}.$$

Numberings satisfying this additional property are called acceptable. Again it's not at all obvious at first glance that such numberings actually exist, but they do - and indeed when a numbering of Turing machines is presented in a computability theory class, it's always chosen to be acceptable. Acceptability turns out to be the crucial property behind all the usual theorems in computability theory, including the three mentioned above. Conversely, any two acceptable numberings are ultimately equivalent (although one may be more convenient than another) for every purpose I've seen.

---

Back to the OP

So now we can give a more precise answer to your question:

Suppose $\Phi$ is a numbering of Turing machines. If $\Phi$ has the Recursion property - and in particular, if $\Phi$ is acceptable - then for each partial computable $f$ there is some $n$ such that $$\Phi_n(x) = \begin{cases} n & \mbox{if }f(n \cdot x)\downarrow,\\ \uparrow & \mbox{else}. \\ \end{cases} $$ However, we can also find a "weird" numbering $\Psi$ such that for some partial computable $f$ there is no $m$ such that $$\Phi_m(x) = \begin{cases} m & \mbox{if }f(m \cdot x)\downarrow,\\ \uparrow & \mbox{else.} \\ \end{cases} $$