1
$\begingroup$

I have read about Rice's Theorem on Sipser's book, and I think I understand it quite well. I understand that it can be used to show that a language is not decidable.

However I am not sure about one question -

Can I use Rice's theorem on languages which are defined on $LBA$ or $DFA$? For example, the following language -

$$ALL_{LBA} = \left \{ \langle M \rangle \mid \text{$M$ is an LBA and $L(M) = \Sigma^*$} \right \}$$

Since an $LBA$ is a "private case" of a turing machine, I am not sure I can use Rice's theorem here to prove the language is undecidable.

$\endgroup$
3
$\begingroup$

If when you say "$M$ is a $LBA$ (or $DFA$ or $PDA$)" you mean that $M$ has a fixed decidable structure (i.e. some properties of its internal state/transition structure) that forces its behaviour to be like a $LBA$ (or $DFA$ or $PDA$) then Rice's theorem cannot be applied directly.

For example, if "$M$ is a $DFA$", is formally defined as "$M$ has no left moves and always enters a halting state on the first blank symbol whatever the current state is" then

$ALL_{DFA} = \left \{ \langle M \rangle \mid \text{$M$ is a DFA and $L(M) = \Sigma^*$} \right \}$ is decidable

Note that even if "$M$ is a $LBA/PDA$" is formally defined using some decidable properties of the structure of $M$, the sets $ALL_{LBA}$ and $ALL_{PDA}$ are undecidable but the proof cannot rely on Rice's theorem: it must use the LBA/PDA ability to "parse" a valid partial computation trace (tape+state) of an arbitrary Turing machine $M$.

$\endgroup$
  • $\begingroup$ Thank you, fabulous explanation. $\endgroup$ – Alan Apr 2 at 8:50
2
$\begingroup$

No, you can not.

To use Rice, we need to have an "index set", i.e. a set $A$ satisfying $\langle M\rangle\in A \land L(M)=L(N) \implies \langle N\rangle \in A$ for all TMs $M,N$. In other words, the set membership must only depends on the language of $M$, and nothing else.

$M$ being a DFA is not a property of the language of $M$.

For a concrete counterexample, consider

$$ A = \{ \langle M\rangle \ |\ M\mbox{ is a DFA and } \epsilon\in L(M)\} $$ If we could apply Rice, we would conclude that the set above is undecidable. However, we know it is decidable since 1) checking whether $M$ is a DFA is decidable and 2) checking whether an automaton accepts the empty string is decidable (for a DFA, simply check if the initial state is final).

$\endgroup$
  • $\begingroup$ Thank you for a great answer. $\endgroup$ – Alan Apr 2 at 8:50

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.