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?
Asked
Active
Viewed 169 times
0
-
Evidently NO. L=A^* is very decidable, and contains ervery non-decidable language. – Gyro Gearloose May 06 '20 at 13:53
2 Answers
1
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.
Captain Lama
- 25,743
1
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.
Gyro Gearloose
- 1,142