質問

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.

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top