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.

  • 1
    $\begingroup$ A priori, it is not clear whether such a function exist. To prove that it does exist (if it does), you'll have to use tools like the smn theorem. $\endgroup$ – Olivier Roche May 13 at 10:41

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:

  1. 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} $$

| cite | improve this answer | |
  • $\begingroup$ Many thanks--this is an extremely interesting answer $\endgroup$ – Cantorexample May 13 at 17:51
  • $\begingroup$ Is your definition of acceptable numbering equivalent to the one here? en.wikipedia.org/wiki/Admissible_numbering They require that there exist two total computable functions with the appropriate properties, but you (and other sources I've seen) require only one such function. $\endgroup$ – user634426 May 26 at 3:13
  • $\begingroup$ @user634426 Yes, acceptability is the same as admissibility. (Interestingly, google tells me that admissibility is more commonly used! Whoopsie.) But the wiki definition is phrased a bit oddly. Basically, they're doing something similar to Rogers, namely working with a canonical setup (there called $\psi$). So the way they've defined admissibility/acceptability there is basically: "$\eta$ is admissible iff [boring stuff and] $\eta$ can be "folded into" the standard numbering and the standard numbering can be "folded into" $\eta$." (continued) $\endgroup$ – Noah Schweber May 26 at 3:45
  • $\begingroup$ But one of the first things we prove about that standard numbering $\psi$ is that every other numbering "folds into" it (that is, that $\psi$ is admissible in my sense), and after having proved this the "fold $\eta$ into $\psi$" part of the wiki definition is pointless since it holds for every (computable) $\eta$. Basically, my version is "Admissible iff everything can be folded into it," and the wiki version is "Admissible iff $\psi$ can be folded into it and also by the way everything can be folded into $\psi$." (continued) $\endgroup$ – Noah Schweber May 26 at 3:47
  • $\begingroup$ They're the same thing. The wiki version is more concrete in that it starts with a specific choice of how we should do things, but it also requires us to prove something (namely the admissibility-in-my-sense of $\psi$) before the definition they give is reasonable. On the other hand, the definition I give makes perfect sense right out of the box ... but it's kind of abstract, and we still have to prove the same thing (namely that something is admissible in that sense) before we can do anything interesting with the definition. $\endgroup$ – Noah Schweber May 26 at 3:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.