patternMinor
Are these sets of indices also index sets?
Viewed 0 times
indicesthesearealsoindexsets
Problem
An index set is a set of all indices of some family of computably enumerable sets. It is known that the empty set is an index set and that $K = \{e \mid e \in W_e\}$ is not an index set.
The following was an exam question I didn't manage to answer:
Which of the following sets are index sets?
1) $\emptyset $
2) $K= \{ x \mid x \in W_x \}$
3) $E = \{2,4,6,8, \dots \}$
4) $\{ x \mid \phi_x = \phi_{x^2}\}$
I think:
It is known $K$ (i.e., the halting set) is not an index set so
(2) is ruled out. I read on this on last page problem 4 that the set
of even numbers is an index set, so I'm not sure that (1) and (3) is
true! But the answer sheet wrote just (1) is true. I don't know what
is the definition of $E$ in (3) and not sure about (4).
Can anyone clarify me in order to better understand this challenging
question? Why are (3) and (4) not index sets? I'm not familiar with
notation (4), any description?
The following was an exam question I didn't manage to answer:
Which of the following sets are index sets?
1) $\emptyset $
2) $K= \{ x \mid x \in W_x \}$
3) $E = \{2,4,6,8, \dots \}$
4) $\{ x \mid \phi_x = \phi_{x^2}\}$
I think:
It is known $K$ (i.e., the halting set) is not an index set so
(2) is ruled out. I read on this on last page problem 4 that the set
of even numbers is an index set, so I'm not sure that (1) and (3) is
true! But the answer sheet wrote just (1) is true. I don't know what
is the definition of $E$ in (3) and not sure about (4).
Can anyone clarify me in order to better understand this challenging
question? Why are (3) and (4) not index sets? I'm not familiar with
notation (4), any description?
Solution
We start with a bit of notation:
Rice's theorem immediately shows that if $I$ is a non-trivial index sets (that is, $x \in I$ and $y \notin I$ for some $x,y$) then $I$ is not computable.
We can now go over the four sets in the question:
-
$\emptyset$ is trivially an index set.
-
$K = \{ e : e \in W_e \}$ is not an index set. Indeed, the recursion theorem shows that some $e$ satisfies $W_e = \{e\}$. There are infinitely many programs which halt only on input $e$ and output $\phi_e(e)$. Pick one of them, $e' \neq e$. Then $e \in K$ and $e' \notin K$ even though $\phi_e = \phi_{e'}$. (This proof is taken from S. Barry Cooper, Computability Theory, mention by Pål GD in the comments.)
-
$E = \{2,4,6,8,\ldots\}$ is computable and so not an index set by Rice's theorem.
-
$\{ x : \phi_x = \phi_{x^2} \}$ is (probably) not an index set. Indeed, for it to be an index set it must hold that whenever $\phi_x = \phi_{x^2} = \phi_y$ then also $\phi_y = \phi_{y^2}$, which sounds unlikely. (The recursion theorem gives us infinitely many $x$ such that $\phi_x = \phi_{x^2}$, and for each such $x$, there are infinitely many $y$ such that $\phi_x = \phi_y$. It would be a major coincidence if for all $x,y$ we would have $\phi_y = \phi_{y^2}$.)
In part 4 there is an argument but not a proof, and this is not a coincidence. Whether $I = \{ x : \phi_x = \phi_{x^2} \}$ is an index set or not depends on the definition of $\phi$, that is on the universal Turing machine. Every choice corresponds to an admissible numbering, and there are some admissible numberings for which $I$ is an index set (see here), and there are others for which $I$ is not an index set (see here). So the answer for part 4 is really "we don't know" or "it depends". Nevertheless, for any natural admissible numbering, you will find out that $I$ is not an index set; unless you engineer $I$ to be an index set, it won't be an index set.
For convenience, I will repeat the constructions showing that $I$ can be an index set and can be not an index set:
-
$I$ can be an index set: Fix some admissible numbering $\phi_x$. Let $p_i$ be the $i$th prime. Define a new admissible numbering $\psi_x$ by $\psi_{p_i^k} = \phi_i$ for all $k \geq 1$, and $\psi_x = 0$ whenever $x$ is not a prime power. Thew new admissible numbering satisfies $\psi_x = \psi_{x^2}$ for all $x$ and so $I = \mathbb{N}$ is trivially an index set.
-
$I$ can be not an index set: Fix some admissible numbering $\phi_x$. Define a new admissible numbering $\psi_x$ by
$$ \psi_x = \begin{cases} 0 & x = 0,1,2,3 \\ 1 & x = 4 \\ \phi_{x-5} & x \geq 5 \end{cases} $$
In this case $\psi_1 = \psi_{1^2} = \psi_2$ but $\psi_2 \neq \psi_{2^2}$, showing that $I$ is not an index set.
I conjecture that under some reasonable interpretation, the fraction of admissible numberings for which $I$ is an index set tends to zero.
- $\phi_x$ is the partial function computed by program $x$.
- $W_x = \operatorname{dom} \phi_x$, that is, the set of inputs on which program $x$ halts.
- An index set is a set of programs $I$ such that if $\phi_x = \phi_y$ then $x \in I \Leftrightarrow y \in I$. (That is, $I$ is a union of equivalence classes of the equivalence relation $x \equiv y \Leftrightarrow \phi_x = \phi_y$.)
Rice's theorem immediately shows that if $I$ is a non-trivial index sets (that is, $x \in I$ and $y \notin I$ for some $x,y$) then $I$ is not computable.
We can now go over the four sets in the question:
-
$\emptyset$ is trivially an index set.
-
$K = \{ e : e \in W_e \}$ is not an index set. Indeed, the recursion theorem shows that some $e$ satisfies $W_e = \{e\}$. There are infinitely many programs which halt only on input $e$ and output $\phi_e(e)$. Pick one of them, $e' \neq e$. Then $e \in K$ and $e' \notin K$ even though $\phi_e = \phi_{e'}$. (This proof is taken from S. Barry Cooper, Computability Theory, mention by Pål GD in the comments.)
-
$E = \{2,4,6,8,\ldots\}$ is computable and so not an index set by Rice's theorem.
-
$\{ x : \phi_x = \phi_{x^2} \}$ is (probably) not an index set. Indeed, for it to be an index set it must hold that whenever $\phi_x = \phi_{x^2} = \phi_y$ then also $\phi_y = \phi_{y^2}$, which sounds unlikely. (The recursion theorem gives us infinitely many $x$ such that $\phi_x = \phi_{x^2}$, and for each such $x$, there are infinitely many $y$ such that $\phi_x = \phi_y$. It would be a major coincidence if for all $x,y$ we would have $\phi_y = \phi_{y^2}$.)
In part 4 there is an argument but not a proof, and this is not a coincidence. Whether $I = \{ x : \phi_x = \phi_{x^2} \}$ is an index set or not depends on the definition of $\phi$, that is on the universal Turing machine. Every choice corresponds to an admissible numbering, and there are some admissible numberings for which $I$ is an index set (see here), and there are others for which $I$ is not an index set (see here). So the answer for part 4 is really "we don't know" or "it depends". Nevertheless, for any natural admissible numbering, you will find out that $I$ is not an index set; unless you engineer $I$ to be an index set, it won't be an index set.
For convenience, I will repeat the constructions showing that $I$ can be an index set and can be not an index set:
-
$I$ can be an index set: Fix some admissible numbering $\phi_x$. Let $p_i$ be the $i$th prime. Define a new admissible numbering $\psi_x$ by $\psi_{p_i^k} = \phi_i$ for all $k \geq 1$, and $\psi_x = 0$ whenever $x$ is not a prime power. Thew new admissible numbering satisfies $\psi_x = \psi_{x^2}$ for all $x$ and so $I = \mathbb{N}$ is trivially an index set.
-
$I$ can be not an index set: Fix some admissible numbering $\phi_x$. Define a new admissible numbering $\psi_x$ by
$$ \psi_x = \begin{cases} 0 & x = 0,1,2,3 \\ 1 & x = 4 \\ \phi_{x-5} & x \geq 5 \end{cases} $$
In this case $\psi_1 = \psi_{1^2} = \psi_2$ but $\psi_2 \neq \psi_{2^2}$, showing that $I$ is not an index set.
I conjecture that under some reasonable interpretation, the fraction of admissible numberings for which $I$ is an index set tends to zero.
Context
StackExchange Computer Science Q#40972, answer score: 6
Revisions (0)
No revisions yet.