patternMinor
Non Recursively Enumerable Languages
Viewed 0 times
languagesenumerablerecursivelynon
Problem
Can someone give me an example of Non Recursively Enumerable language... i.e. A language which no Turing machine can accept ? What makes a language non recursively enumerable ?
Solution
Every undecidable yet semi-decidable language provides an example: its complement.
That is because if $L$ and $\overline{L}$ are both semi-decidable, they are also both decidable -- proving that is an easy exercise.
You should know at least one such language from class.
The Halting language, and probably numerous others from exercise problems.
That is because if $L$ and $\overline{L}$ are both semi-decidable, they are also both decidable -- proving that is an easy exercise.
You should know at least one such language from class.
The Halting language, and probably numerous others from exercise problems.
Context
StackExchange Computer Science Q#52503, answer score: 9
Revisions (0)
No revisions yet.