0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.