# Rice's Theorem - usage on $DFA$ or $LBA$

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.

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$$.

• Thank you, fabulous explanation.
– Alan
Apr 2 '19 at 8:50

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).

• Thank you for a great answer.
– Alan
Apr 2 '19 at 8:50