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

Operations under which the class of undecidable languages isn't closed

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
theoperationsundecidablelanguagesclosedunderwhichisnclass

Problem

Do there exist undecidable languages such that their union/intersection/concatenated language is decidable? What is the physical interpretation of such example because in general, undecidable languages are not closed under these operations?

What can we say about the kleene closure? Do we have examples for it too? I.e. can the closure of an undecidable language be decidable?

Also, can we generalize such undecidable classes?

Solution

We know that the halting language is undecidable. Let H be its binary encoding. We can also state that complement of H is undecidable. Therefore, union/intersection of H and HComp are $\Sigma^*$ and $\phi$, which are decidable.

Context

StackExchange Computer Science Q#1549, answer score: 9

Revisions (0)

No revisions yet.