MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 7 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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