Реализуйте перечислитель, используя машину Тьюринга - избыточные отпечатки

Question

По следующему алгоритму:

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

Почему мы не можем просто сказать - "для каждого слова в Σ* запустить M на нем. Если оно принимает, то печатать, если отклоняет, затем переходить к следующему слову". Тогда мы не будем печатать каждое слово более одного раза.

Почему ненужные отпечатки?

Алгоритм из изображения:

Если ТМ M признает язык Aмы можем построить следующий перечислитель для A, Предполагать s1, s2, s3,... это список возможных строк в Σ*,

E = "Игнорировать ввод

1) Повторите следующее для i = 1, 2, 3,...

2) Беги M за i шаги на каждом входе s1, s2, s3.,, si,

3) Если какие-либо вычисления принимают, распечатайте соответствующие sj".

Если M принимает определенную строку, она появится в списке, сгенерированном E (на самом деле бесконечно много раз)

Спасибо

Answer 1

Как указано в комментариях: проблема в том, что некоторые вычисления могут не завершиться. Поэтому, если вы сделаете их последовательно, те, которые будут выполнены после первого не завершающегося вычисления, никогда не будут выполнены.

Данный алгоритм использует стандартную технику, чтобы обойти это: ласточкин хвост.

Вы можете изменить шаг 3 на "Если какое-либо вычисление принимает после i шаги, затем печать " - тогда нет ненужных отпечатков. Но тогда вам нужно подсчитывать шаги во время каждого моделирования, что означает некоторую дополнительную работу. Автор выбирает вариант, который прост в программировании, но не очень эффективен.