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

Question

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.

Answer 1

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

Answer 2

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