computability - 順列の下で閉じられた再帰的に列挙可能な (計算可能に列挙可能な) 言語?

Question

L が任意の言語の場合。言語 perms(L) は、L からの単語のすべての順列の言語です。

正誤問題: L が再帰的に列挙可能 (計算可能) である場合、perms(L) も再帰的に列挙可能です。

これは以前の決勝戦で、L が決定可能であれば perms(L) も決定可能であるという質問とともにありました。これは真実であることがわかりました。

私は間違っていると思いますが、この主張を裏付ける証拠はありません。

Answer 1

「再帰的に列挙可能」とはどういう意味か考えてみてください。これは、各文字列を言語で書き留める TM を定義できることを意味します。TM に十分な時間を与えると、TM は最終的に任意の文字列を書き留めます。

言語内の任意の文字列について、順列の数は有限です。チューリング マシンは、文字列が与えられた場合、文字列のすべての順列を確実に書き留めることができます。

これら 2 つのチューリング マシンを組み合わせると想像してみてください。最初のチューリング マシンは言語のすべての文字列を列挙し、2 番目のチューリング マシンはこれらの各文字列のすべての順列を出力します。結果は、第一言語の文字列のすべての順列の列挙です。

上記のチューリング マシンの組み合わせにより、新しいチューリング マシンが生まれます。このようにして、目的の言語ですべての文字列を列挙するチューリング マシンができました。定義上、この言語は再帰的に列挙可能です。