В определении «Рекурсивно перечислимый язык» из Википедии говорится:
«Рекурсивно перечислимый язык - это формальный язык, для которого существует машина Тьюринга (или другая вычислимая функция), которая будет перечислять все допустимые строки языка. Обратите внимание, что, если язык бесконечен, предоставляемый алгоритм перечисления может быть выбран так, чтобы он избегал повторений, так как мы можем проверить, является ли строка, созданная для числа n, "уже" произведена для числа, которое меньше n. Если он уже произведен, используйте выход для ввода n + 1 вместо (рекурсивно), но снова проверьте, является ли он «новым»."
Интересно, как это сделать? что именно? Рассмотрим бесконечный язык L, распознаваемый некоторой машиной Тьюринга. Может ли кто-нибудь показать мне машину Тьюринга, которая будет перечислять все допустимые строки языка и избегать повторений? Спасибо!