patternMinor
Intersection of Turing-recognizable language and regular language
Viewed 0 times
andregularrecognizablelanguageintersectionturing
Problem
True or false:
An intersection of a Turing-recognizable and a regular language is always Turing-decidable.
This was asked on a practice test and the answer is False. Why? I thought regular languages were a subset of decidable languages. So if you intersect regular and recognizable the result would also have to be a subset of decidable.
Is that not correct?
An intersection of a Turing-recognizable and a regular language is always Turing-decidable.
This was asked on a practice test and the answer is False. Why? I thought regular languages were a subset of decidable languages. So if you intersect regular and recognizable the result would also have to be a subset of decidable.
Is that not correct?
Solution
The intersection is a subset of a decidable set, but so is every language. After all, the language of all strings over a given alphabet is trivially decidable (the decider always says "yes"), and any language is a subset of the language of all strings over its alphabet.
Context
StackExchange Computer Science Q#49361, answer score: 4
Revisions (0)
No revisions yet.