# Given a regular language $L$ and Turing machine $T$, is it decidable that $\mathcal{L}_{acc}(T) \subseteq L$?

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?

## 1 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.