-1
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ Hint: every language is an infinite union of the singletons containing each word... $\endgroup$ – Shaull Nov 11 '14 at 21:12
  • 2
    $\begingroup$ I don't understand your question. You say you've seen a proof so why do you need another one? $\endgroup$ – David Richerby Nov 11 '14 at 21:29
  • 2
    $\begingroup$ @Shaull. Consider turning this hint into an answer. $\endgroup$ – Rick Decker Nov 12 '14 at 1:42
2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

(Following Shaull's comment)

No.

For any $w\in \Sigma^*$, the singleton $L_w=\{ w \}$ is a computable set.

Yet, every set $L$ (finite or infinite, computable or not) can be written as an (in/)finite union of singletons $$ L = \bigcup_{w\in L} L_w$$

Therefore, some infinite unions of computable sets do give a computable set (e.g., union over all the possible singletons), and some infinite unions don't give a computable set.

$\endgroup$

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