I'm struggling to grasp the intuition behind the concept of an index set. By definition, a set $I$ is called an index set if $\forall i,j: i \in I$, $\phi_i = \phi_j \implies j \in I$. This implies that if we have a program with indices $i \in I$ and a different program $j$, both computing the same function, then $j$ is also in $I$. Essentially, this set contains all possible program indices that compute the same function. This is clear for me.

There have been discussions regarding whether certain sets are index sets or not, as seen in these questions:

So my question is how to know if a set is index set or not, I still don't get it, even if I understand the idea of the index set. For example, let's take a simpler version of the halting problem where the halting is on its own encoding. This set is not index set why? can you give me the inution of why it's not index set and formal proof? or the sets $A=\{x∣φ_x(x)=x^2\} ,B=B=\{x∣φ_x(x)=10\}$ from the second link.


1 Answer 1


For your first question about how to prove that the following set is not an index set:

K = { e | e is the code of a machine which halts on e}

Let f be the following function:

f(n) = Code of a machine which halts only on n and gives 1 as output.

I think it is clear why f is a computable function.

We know, By Kleene's fixed point theorem((It is more known as Recursion theorem)) that there is some i which is the code of a machine that computes the same function as f(i)'s machine.

Now, According to f's definition, We know i appears in K. But since f(i) != i and f(i)'s machine halts only on i, f(i) won't appear in K.

In conclusion, we constructed a computable function which has two indices which one of them appears in K but the other one doesn't. So K is not an index set.

For sets A and B, Consider the following functions:

f(n) = Code of a machine which halts only on n and gives n^2 as output. g(n) = Code of a machine which halts only on n and gives 10 as output.

With the same argument which made for K, It can be proven that A and B are not index sets.

I hope my answer would be helpful for you.

  • $\begingroup$ According to our assumptions our new program would halt only on i. In fact the program encoded by i behaves same as the program encoded by f(i). The reason that f(i) cannot be in K is that f(i) doesn't halt with its own code as input but i does halt on i. If I misunderstood your point please let me know so I can help you make things clear $\endgroup$ Dec 31, 2023 at 13:06
  • $\begingroup$ Thanks it's clear now $\endgroup$
    – PPP Legend
    Jan 1 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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