# Is this c.e. set obtained via the Recursion Theorem?

Reading through a text on computability I came across a c.e. set defined as follows: Let $K=\lbrace x \in W_x \rbrace$ and let $f$ be a computable function. Then there exists $n \in \omega$ such that $W_n=\lbrace x \in K : x \leq f(n) \rbrace$.

My question is how can we find such an index $n$? My first thought was to let $g$ be a computable function such that $g(k)$ enumerates an index for $\lbrace x \in K : x \leq f(k)\rbrace$ and then apply the Kleene Recursion Theorem to obtain the desired index. But thinking about it, I cannot figure out how to actually name a computable function $g$ which enumerates the desired indices. Any help here?

-

## 1 Answer

Taking the point of view (as in Rogers's book) that an index for a c.e. set $A$ amounts to a program that converges on exactly those inputs that are in $A$, here's an informal description of the program $g(k)$: "On input $x$, first check whether $x\leq f(k)$; if not, diverge (say by going into a loop). If so, start running program $x$ on input $x$; if and when that converges, halt." Note that this program uses $f(k)$, which I think of as hard-wired into the program, for each fixed $k$; the rest of the program doesn't depend on $k$. The recursive function $g$ is computed as follows: "On input $k$, first compute $f(k)$, and then hard-wire that into the program exhibited above as $g(k)$."

If you want to take another point of view on indexing, for example Kleene indices, or explicit Turing machine programs, then you should say what indexing you want, and hope for an answer from someone much more industrious than I am.

-
Computability theorists should just learn to program in a decent programming language (they'd like Haskell), where many of these arguments are beautiful, simple programs. – Andrej Bauer Feb 3 '12 at 8:05