So I was trying to solve following exercise:

Let $(L_{i})_{i \in \mathbb{N}}$ be a family of decidable languages - this means that every $L_{i}$ is decidable. Then $\cup_{i \in \mathbb{N}}L_{i} $ is also decidable. Right or wrong?

The solution states, that this statement is wrong because we can set $L_{i}:=\{f(i)\}$ with $f : \mathbb{N} \rightarrow H_{0}$ and will therefore receive $\cup_{i \in \mathbb{N}}L_{i} = H_{0}$. At the same time $L_{i}$ languages are still decidable, for every $i \in \mathbb{N}$ because they are finite.

However I still struggle to understand how exactly a language can be decidable with $f : \mathbb{N} \rightarrow H_{0}$, because I thought that $H_{0}$ was not decidable.

Thanks in advance!!

  • $\begingroup$ The statement is wrong, as is shown by the fact the the infinite union of the $L_i$'s is not decidable. Actually every language over a finite alphabet can be expressed as a countable union of singleton (and hence decidable) sets. $\endgroup$ – Ariel Aug 10 at 13:36

You don't define $H_0$. Presumably it's an undecidable set.

First, $f : \mathbb{N} \to H_0$ only means that all the values of $f(x)$ are in $H_0$, i.e. the image of $f$ is a subset of $H_0$: $f(\mathbb{N}) \subseteq H_0$. The proof of the counterexample involves a stronger property: it constructs a function $f$ whose image is exactly $H_0$, that is, $f(\mathbb{N}) = H_0$.

Second, the image of a recursive set by a recursive function is not necessarily recursive. It's obviously recursively enumerable, by definition of “recursively enumerable”: if $g$ is recursive, then it's partial recursive, and $g(\mathbb{N})$ is a recursively enumerable set. But $g(\mathbb{N})$ might not be recursive. For example, consider a function $g$ whose input is an encoding of a program (that doesn't take arguments) and an integer: $g(\langle P,n\rangle)$ which runs $P$ for $n$ steps and returns $\langle P\rangle$ if $P$ terminates in less than $n$ steps and $0$ otherwise. The function $g$ is recursive (its definition is an algorithm to run it), but its image is the set of encodings of terminating programs, which is not decidable. Coming back to our original problem, it's possible to have a recursive $f$ such that $f(\mathbb{N}) = H_0$ but $H_0$ is not recursive.

Third, $f$ might not be recursive anyway. (And if you apply the previous paragraph, you'll notice that it can't be recursive if $H_0$ is not recursively enumerable.) All you know is that there exists a function $f$ such that $f(\mathbb{N}) = H_0$. An example of how to define this function is: $f(x) = x$ if $x \in H_0$ and $f(x) = h_0$ if $x \notin H_0$, where $h_0$ is the smallest element of $H_0$. This is a perfectly good mathematical definition, but it isn't an algorithmic definition: since $H_0$ isn't decidable, there's no algorithm to choose between the case $x \in H_0$ and the case $x \notin H_0$.

Intuitively speaking, to decide whether $x \in \bigcup_{i\in\mathbb{N}} L_i$, you need to figure out which $i$ to check, then check whether $x \in L_i$. But there's no reason why there would be an algorithmic way to pick $i$. (And to make things worse, $x$ might be in multiple $L_i$, possibly infinitely many — but the proposed property is wrong even if the $L_i$ are disjoint, as seen with the example of singletons which can easily be renumbered to make them distinct and therefore disjoint.)

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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