Given a regular language $L$ and Turing machine $T$, is it decidable that $\mathcal{L}_{acc}(T) \subseteq L$?
Rice's Theorem states that for a given nontrivial property $P$ of a Turing machine, that given a Turing machine $T$ that property is undecidable.
Thus I am attempting to show that the property is nontrivial, meaning there are some Turing machines for which the property holds and some for which it doesn't.
I was thinking about using the Chomsky hierarchy to show this, but I am a bit confused on how to go about it.
Chomsky hierarchy:
$\mathcal{R} \subset \mathcal{C} \subset \mathcal{T}_D \subset \mathcal{T}_R \subset \mathcal{L}_{all}$
Where $\mathcal{R}$ is the regular set, $\mathcal{C}$ is the context-free set, $\mathcal{T}_D$ is the Turing-decideable set, $\mathcal{T}_R$ is the Turing-recognizeable set, and $\mathcal{L}_{all}$ is the set of all languages.
So I was thinking that since $L$ is regular, we could find some Turing machine $A$ whose accepting language is a subset of $L$ and some Turing machine $B$ whose accepting language is not a subset of $L$. This is what my intuition tells me, but I'm not sure how to show that as a proof.
Am I on the right track here/can someone provide some insight on how to go about answering the question?
Best Answer
It seems irrelevant that $L$ is regular; any $L$ other than the set of all strings will do what you want. Thanks to Rice's theorem, it's enough to construct (1) a Turing machine that accepts no strings at all (so $\mathcal L_{acc}=\varnothing\subseteq L$) and (2) a Turing machine that accepts exactly one string $s$, chosen from the complement of $L$ (so $\mathcal L_{acc}=\{s\}\not\subseteq L$). Both constructions are easy.