HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Are two non-Turing-recognizable languages closed under union?

Submitted by: @import:stackexchange-cs··
0
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.