turing-machines - 決定可能性の質問

Question

実数を決定する NFA はありますか?

Answer 1

いいえ、できません。非決定性有限オートマトンは、文字列を入力として受け入れます。すべての文字列の集合は可算であるため、実数の集合よりも小さくなります。したがって、NFA への入力として任意の実数をエンコードすることさえできません。

Answer 2

いいえ。

実数の小数点以下の桁数は無限です。これらの桁にはシステムが存在しない場合があります (つまり、ランダムなプロセスによって生成される場合があります)。その場合、シーケンス自体よりも大幅に短い数字のシーケンスの記述はあり得ません。

このような実数rを取ります。任意の NFA には有限数の状態しかなく、有限に記述できるため、実数rのみを受け入れるのは不十分です (そうしないと、 rの有限記述が存在できないという事実と矛盾するため)。