patternModerate
Are two non-Turing-recognizable languages closed under union?
Viewed 0 times
nonarelanguagesunionclosedrecognizabletwounderturing
Problem
If I have two languages that aren't Turing-recognizable, is the union between them always not T-recognizable? Why?
Solution
Let $U\subseteq \mathbb{N}$ be any unrecognizable set. Let $L_1 = \{0, 2, 4, \dots\} \cup \{2n+1\mid n\in U\}$ and $L_2 = \{1,3,5, \dots\} \cup \{2n\mid n\in U\}$. $L_1$ and $L_2$ are both unrecognizable but their union is $\mathbb{N}$.
Context
StackExchange Computer Science Q#35573, answer score: 11
Revisions (0)
No revisions yet.