Тьюринг узнаваемый => перечислимый

10

Я получил доказательство перехода от перечислителя к машине Тьюринга (продолжайте запускать перечислитель и посмотрите, соответствует ли он вводу), но я не вижу, как работает другой способ.

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

Проблема, с которой я сталкиваюсь, состоит в том, что для этого необходимо, чтобы язык был разрешимым. Иначе оно может застрять на третьем слове в каком-то бесконечном цикле, обреченном никогда не принимать и не отвергать, и, конечно, никогда не печатать весь язык.

Что мне не хватает?

Т. Кили
источник

Ответы:

9

Чего не хватает, так это того, как вы запускаете машину Тьюринга для получения перечислителя. Вместо того, чтобы генерировать каждую строку, запустите M , а затем выведите эту строку, если M принимает - что, как вы определили, не будет работать - вы делаете что-то вроде следующего, которое принимает стратегию моделирования многих экземпляров M в разных строках "в параллельно".MMMM

Предположим , что лента имеет содержание , где ж я есть какое - либо слово на рассмотрении и ˙s я это текущее состояние М , работающего на ш I . Это означает, что n копий M моделируются. w i хранится, чтобы мы знали, какой был исходный ввод.вес1,S1##весN,SNвесяSяMвесяNMвеся

Теперь запустите следующий цикл

  1. В конце ленты запись следующая строка из , наряду с исходной конфигурации S из M , то есть, запись # ш , S .весΣ*SM#вес,S
  2. Смоделируйте каждую копию на ленте за один шаг. (Предположительно используйте другую ленту.)M
  3. Если любой из s входит в принимающее состояние, поместите соответствующую строку на выходную ленту. Удалите этот экземпляр M с ленты.MM
  4. Если какой-либо из s входит в состояние отклонения, удалите этот экземпляр M с ленты.MM
  5. Перейти к шагу 1.

Нетрудно утверждать, что все строки принятые M , в конечном итоге будут выведены на ленту.весΣ*M

Дэйв Кларк
источник
4
он же "голубь".
Каве