[Solved]: Is the infinite union of computable sets computable?

Problem Detail: 

My intuition is telling me that this is untrue. But I am having trouble formulating a proof for this. Can anyone point me in the right direction? I've seen a proof by contradiction involving the union of all singletons in an infinite language but I am needing a to look at this from a different angle.

Related question: Is the infinite union of computably enumerable sets also computably enumerable? I also believe this to be untrue.

Asked By : Cain

Answered By : Yuval Filmus

The claim as stated is easy to refute, so let's ask a (slightly) more difficult question: is the countable union of computable languages computable? The answer is again negative: the language $L = \{ 1^e : \text{ program $e$ halts on the empty input}\}$ is not computable, but is the union of countably many singletons.

What if we require the countably many languages to be uniformly computable? This means that not only is there a one-parameter program $P_i$ for the $i$th language $L_i$ such that $P_i(x) = T$ iff $x \in L_i$, but also there is a two-parameter program $P$ such that $P(i,x) = T$ iff $x \in L_i$ (both $P_i$ and $P$ are required to always halt). In this case, the union still need not be computable. For example, let $L_n = \{ e : \text{ program $e$ halts on the empty input within $n$ steps}\}$. These programs are uniformly computable, but their union $L$ is not computable.

A union of a sequence of uniformly computable languages is known as recursively enumerable (r.e.) or computationally enumerable (c.e.), and is a fundamental concept in computability theory. The relation between computable languages and c.e. ones is the same as that between P and NP.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32998