アルファベット順にTuring認識可能な言語を列挙する

Question

Turing認識可能な言語も列挙できます。

しかし、列挙子がTuring認識可能な言語を辞書順に「印刷」することは可能ですか？

Answer 1

いいえ、可能であるとします。その後、言語は次のように決定されます。

1. 受理したすべての文字列を順番に列挙し始めます。
2. 探している文字列よりも辞書順が大きい文字列を表示する場合は、拒否を停止します。
3. 探している文字列を表示する場合は、受け入れを中止してください。

最終的には任意の入力文字列に対して終了することになります。なぜなら、より小さい辞書順で多数の列挙された文字列が存在するからです。ターゲット文字列が見つからない場合は常に拒否を停止し、そうであれば受け入れを停止します。あなたの文字列が欠落していることを心配する必要はありません。なぜなら、文字列を列挙しておくことで、文字列の位置を知ることができるからです。

決定可能でない列挙可能な言語があることがわかっているので、列挙可能な言語を順番に列挙できないようにする必要があります。