computability - 在排列下关闭的递归可枚举（可计算可枚举）语言？

Question

如果 L 是任何语言。语言 perms(L) 是 L 中所有单词排列的语言。

对或错：如果 L 是递归可枚举的（可计算可枚举的），那么 perms(L) 也是递归可枚举的。

这是在之前的决赛中出现的问题：如果 L 是可判定的，那么 perms(L) 也是可判定的，我发现这是真的。

我想我会说假的，但我没有证据支持这种说法。

Answer 1

想想“递归可枚举”是什么意思。这意味着您可以定义一个 TM，它将用该语言写下每个字符串。如果你给 TM 足够的时间，它最终会写下任何给定的字符串。

对于语言中的任何给定字符串，它具有有限数量的排列。给定字符串，图灵机当然可以写下字符串的所有排列。

想象一下将这两个图灵机放在一起：第一个枚举您的语言中的所有字符串，第二个发出每个字符串的所有排列。结果是第一语言中字符串的所有排列的枚举。

上述图灵机的组合产生了一个新的图灵机。因此，我们有一个图灵机来枚举所需语言的所有字符串。根据定义，这种语言是递归可枚举的。