Если L — любой язык. Язык perms(L) — это язык всех перестановок слов из L.
Верно или неверно: если L рекурсивно перечислимо (вычислимо перечислимо), то perms(L) также рекурсивно перечислимо.
Это было в предыдущем финале вместе с вопросом: если L разрешима, то и perms(L) разрешима, что я нашел верным.
Полагаю, я бы сказал, что это ложь, но у меня нет доказательств, подтверждающих это утверждение.
Подумайте о том, что означает «рекурсивно перечисляемый». Это означает, что вы можете определить НП, который будет записывать каждую строку на языке вниз. Если вы дадите TM достаточно времени, он в конечном итоге запишет любую заданную строку.
Для любой заданной строки языка существует конечное число перестановок. Машина Тьюринга, безусловно, могла бы записать все перестановки строки, заданной строкой.
Представьте себе, что эти две машины Тьюринга объединяются: первая перебирает все строки вашего языка, а вторая генерирует все перестановки каждой из этих строк. Результатом является перечисление всех перестановок строк на первом языке.
Комбинация описанных выше машин Тьюринга приводит к новой машине Тьюринга. Таким образом, у нас есть машина Тьюринга, перебирающая все строки на желаемом языке. По определению этот язык рекурсивно перечислим.
