3
$\begingroup$

Kleene's second recursion theorem easily yields a self-referential program. What is more, it gives a program $P_a$ that computes any computable function of its index $a$ and its input. But does an injective recursive function exist, such that all its values are also its indexes. In other words does an injective recursive function $g$ exist, such that for each value $g(n)$ the program $P_{g(n)}$ computes the said function $g$?

EDIT: To make it absolutely clear let $\varphi_a$ denote the one argument function calculated by the program $P_a$ with index $a$. I am looking for an injective function $g$ such that for all natural numbers $n$, $\varphi_{g(n)}(x)=g(x)$

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

It is easy for $g$ to exist if you don't require that $g$ hits all indices for a program that computes $g$. In that case we can say, essentially

$$\begin{align}g(n) = &\text{let } x = \text{the source for this program (by any standard quine construction)}\\ &\text{in the index of the program that consists of }n\text{ "skip"s followed by }x \end{align}$$

Variants of this construction can be produced under even very abstract conditions on how we're enumerating computable functions (basically the $s$-$n$-$m$ theorem has to hold, and composition of functions has to be computable, and perhaps one or two similar conditions which I may have forgotten).

However, $g$ cannot exist if we require it to output all of its indices. If it did, we could use it to decide the halting problem. Suppose we want to know whether Turing machine $T$ halts. Now consider the program

$$ P_q(n) = \begin{cases} 0 &\text{if }T\text{ halts in at most }n\text{ steps} \\ g(n) &\text{otherwise}\end{cases}$$

Then $P_q$ program computes $g$ exactly if $T$ doesn't halt. So we can find out whether $T$ halts by enumerating all of the outputs of $P_q$ and look for either $0$ or $q$ itself.

$\endgroup$
10
  • $\begingroup$ Thank you, Mr. Makholm. I'm not sure I understand what you mean by "skips." Assume for a moment that I am familiar with some quine construction. Would you explain in more detail how you define $g$ under the said abstract conditions? $\endgroup$
    – superAnnoyingUser
    Nov 23, 2013 at 12:44
  • $\begingroup$ @Ivan: "Skip" is a command that does nothing -- I'm here supposing that you're encoding computable functions as source code in some programming language. If you're thinking in terms of Turing machines instead, you can imagine adding $n$ new states that are never actually reached. $\endgroup$
    – hmakholm left over Monica
    Nov 23, 2013 at 12:48
  • $\begingroup$ I looked up the general construction (see for example Jones, Computability and Complexity From a Programming Perspective, lemma 1.4.4). The relevant property is that there's always a computable injective function $f:\mathbb N\times\mathbb N$ such that $P_x$ and $P_{f(x,y)}$ compute the same function for all $x$ and $y$. The proof from general abstract conditions is rather involved, since all it assumes is Kleene's fixpoint theorem and the s-m-n theorem. $\endgroup$
    – hmakholm left over Monica
    Nov 23, 2013 at 12:54
  • 1
    $\begingroup$ It's on page 233 in the revised PDF found at diku.dk/~neil/Comp2book.html -- the tricky details are in Theorem 14.4.2 one page earlier. $\endgroup$
    – hmakholm left over Monica
    Nov 23, 2013 at 13:49
  • 1
    $\begingroup$ Then, writing $[\![x]\!]$ for $\phi_x$, we have for all $d$: $$[\![ [\![\mathtt e]\!](d) ]\!] = [\![ \pi(\mathtt e,d)]\!] = [\![ \mathtt e ]\!]$$ where the first equality is from the recursion theorem and the second is from the padding lemma. And $[\![ \mathtt e ]\!]$ is injective because $\pi$ is and the recursion theorem clearly preserves injectivity. $\endgroup$
    – hmakholm left over Monica
    Nov 29, 2013 at 18:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .