If a language is Turing decidable, does that make the sublanguages also Turing decidable

170 Views Asked by At

Let $L$ be a language over a finite alphabet $A$. A language $L'$ over the same alphabet $A$ is called a sublanguage of $L$ if $L' \subset L$. Assume that $L$ is Turing-decidable. Does it follow that all of its sublanguages $L'$ are likewise Turing-decidable?

2

There are 2 best solutions below

0
On

Take $L$ to be the language with every single possible word. It is trivially Turing-decidable (just take a machine that always says "yes").

But obviously some sublanguages are not decidable, since the sublanguages of $L$ are all languages.

0
On

NO.

Take any language $L$ with infinitely many words. Then the set of languages $L'\subset L$ is uncountable, but there are only countably many Turing machines.