Я получил доказательство перехода от перечислителя к машине Тьюринга (продолжайте запускать перечислитель и посмотрите, соответствует ли он вводу), но я не вижу, как работает другой способ.
Согласно моим заметкам и книге (Введение в теорию вычислений - Sipser), чтобы получить перечислитель Тьюринга с машины Тьюринга, мы в основном пишем все комбинации алфавита. Затем вы запускаете TM на этом входе, если он принимает распечатать его, замените его новой строкой repeat до бесконечности.
Проблема, с которой я сталкиваюсь, состоит в том, что для этого необходимо, чтобы язык был разрешимым. Иначе оно может застрять на третьем слове в каком-то бесконечном цикле, обреченном никогда не принимать и не отвергать, и, конечно, никогда не печатать весь язык.
Что мне не хватает?