patternMinor
Operations under which the class of undecidable languages isn't closed
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?
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.