Let $Q$ be an undecidable subset of $\mathbb{N}$ created by diagonalization. What's the problem with this "algorithm" for computing $Q$?

Question

This is exercise 11 from Hodel, An Introduction to Mathematical Logic, section 1.7. I'm new to computability, so I'm not sure if I got things right.

Define the set $Q$ as follows: first, let $D(\mathbb{N})$ be the set of all decidable subsets of $\mathbb{N}$; enumerate the decidable subsets $R$ such that $D(\mathbb{N}) = \{R_n \: | \; n \in \mathbb{N}\}$. $Q$ is then defined, for every $n \in \mathbb{N}$, as $Q(n) \iff \neg R_n(n)$. It's clear that $Q$ is undecidable (though it's not entirely clear to me why $Q$ is not empty).

Now, consider the following ""algorithm" for deciding $Q$:

1. Input $n \in \mathbb{N}$.
2. Use the algorithm for $R_n$ to decide if $R_n(n)$.
3. If $R_n(n)$, print NO and halt; if $\neg R_n(n)$, print YES and halt.

I first thought that we may not know the algorithm for $R_n$ in order to calculate $R_n(n)$, but it's a given that this subset is decidable. So I'm a bit of loss here, even though I have the feeling I'm missing something obvious. If someone could drop me a hint (also concerning the parenthetical aside above), I'd appreciate it.

Answer 1

The problem is hiding between line 1 and 2 of your algorithm, you have gone from an integer $n$ to a procedure to decide the $n$th decidable subset in enumeration that we picked non-constructively. If you want this to be effective, you have to describe how you go from $n$ to the decision procedure for the $n$th set in the enumeration. (You can't, strictly speaking, effectively go from $n$ to the set $R_n$, because sets aren't computational objects, however, you can try to go for a code to the set, i.e. an $e$ which is an index for a decision procedure for that set.)

The point of the exercise is to show that this can't be done effectively, because, if it could, then the set $Q$, which is not in $D(\mathbb{N})$, is decidable, by the procedure you outline. A contradiction.

As for the non-emptiness of $Q$, notice that $\varnothing$ is decidable, and so $\varnothing= R_n$ for some $n$, hence $n \in Q$. Or even stronger, as every finite set is decidable, and $Q$ is not, then $Q$ is not even finite.

Answer 2

I see two problems:

1. We don't know an enumeration for the decidable subsets.
2. Even if we had such an enumeration, it's not enough, because we need to know a decision procedure for each decidable subset.