Примеры машины Тьюринга

Ниже приведены примеры, дополняющие статью о машине Тьюринга .

Самый первый пример Тьюринга [ править ]

Следующая таблица - самый первый пример Тьюринга ( Алан Тьюринг, 1937):

«1. Можно сконструировать машину для вычисления последовательности 0 1 0 1 0 1 ...» (0 <пусто> 1 <пусто> 0 ...) ( Неразрешимо стр. 119)

Относительно того, какие действия машина на самом деле делает, Тьюринг (1936) ( Undecidable p. 121) утверждает следующее:

"Эта [примерная] таблица (и все последующие таблицы того же типа) должны пониматься как означающие, что для конфигурации, описанной в первых двух столбцах, операции в третьем столбце выполняются последовательно, а затем машина переходит в m-конфигурация в последнем столбце ". (Неразрешимо, с. 121)

Он очень ясно дает это понять, когда сокращает приведенную выше таблицу до одной инструкции под названием «b» (« Неразрешимо», стр. 120), но его инструкция состоит из трех строк. Инструкция «b» имеет три различных варианта символа {Нет, 0, 1}. За каждой возможностью следует последовательность действий, пока мы не дойдем до крайнего правого столбца, где окончательная m-конфигурация - «b»:

По наблюдениям ряда комментаторов, включая самого Тьюринга (1937) (например, Пост (1936), Пост (1947), Клини (1952), Ван (1954)), инструкции Тьюринга не атомарны - дальнейшие упрощения модели могут производиться без снижения его вычислительной мощности; см. больше на машине Пост-Тьюринга .

Как указано в статье « Машина Тьюринга» , Тьюринг предложил, чтобы его таблица была дополнительно атомизирована, позволяя только одну печать / стирание с последующим одним движением ленты влево / вправо / влево. Он дает нам этот пример преобразования первого маленького стола ( Undecidable , p. 127):

Утверждение Тьюринга по-прежнему подразумевает пять атомарных операций. По заданной инструкции (m-конфигурация) машина:

1. наблюдает за лентой-символом под головой
2. на основе наблюдаемого символа переходит к соответствующей последовательности инструкций для использования
3. печатает символ S _j, стирает или ничего не делает
4. перемещает ленту влево, вправо или вообще не перемещает
5. переходит к последней m-конфигурации для этого символа

Поскольку действия машины Тьюринга не являются атомарными, моделирование машины должно разбить каждую кортеж из пяти на последовательность более простых действий. Одна из возможностей - использованная в следующих примерах «поведения» его машины - следующая:

(q _i ) Тестовая лента-символ под заголовком: если символ S _0, перейдите к q _i .01, если символ S ₁ перейдите к q _i .11, если символ S ₂ перейдите к q _i .21 и т. д.

(q _i .01) напечатайте символ S _j 0 или сотрите или ничего не делайте, затем перейдите к q _i .02

(q _i .02) переместите ленту влево или вправо или вообще не переместите, затем перейдите к qm0

(q _i .11) напечатайте символ S _j 1 или сотрите или ничего не делайте, затем перейдите к q _i .12

(q _i .12) переместите ленту влево или вправо или вообще не переместите, затем перейдите к qm1

(q _i. 21) напечатайте символ S _j 2 или сотрите или ничего не делайте, затем перейдите к q _i. 22

(q _i .22) переместите ленту влево или вправо или вообще не переместите, затем перейдите к qm2

(и т. д. - все символы должны быть учтены)

Так называемые «канонические» конечные автоматы выполняют символьные тесты «параллельно»; см. больше в микропрограммировании .

В следующем примере того, что делает машина, мы отметим некоторые особенности моделей Тьюринга:

«Условие написания цифр только на чередующихся квадратах очень полезно: я всегда буду им пользоваться». (Неразрешимо, с. 121)

Таким образом, при печати он пропускает все остальные квадраты. Напечатанные квадраты называются F-квадратами; пустые квадраты между ними могут использоваться как «маркеры» и называются «E-квадратами», как в слове «подлежащие стиранию». F-квадраты, в свою очередь, являются его «квадратами фигуры» и содержат только символы 1 или 0 - символы, которые он назвал «цифрами» (как в «двоичных числах»).

В этом примере лента начинается с «пустой», а затем на ней печатаются «цифры». Для краткости здесь показаны только ТАБЛИЧНЫЕ состояния:

Тот же «пробег» со всеми промежуточными лентами и движениями показан здесь:

При внимательном рассмотрении таблицы обнаруживаются определенные проблемы с собственным примером Тьюринга - учтены не все символы.

Например, предположим, что его лента изначально не была пустой. Что случилось бы? Машина Тьюринга считывала значения, отличные от предполагаемых.

Подпрограмма копирования [ править ]

Это очень важная подпрограмма, используемая в подпрограмме "умножение".

Пример машины Тьюринга обрабатывает строку из нулей и единиц, где 0 представлен пустым символом. Его задача - удвоить любую серию единиц, встречающуюся на ленте, записав между ними 0. Например, когда головка читает «111», она записывает 0, а затем «111». На выходе будет «1110111».

Для выполнения своей задачи этой машине Тьюринга потребуется всего 5 состояний работы, которые называются {s ₁ , s ₂ , s ₃ , s ₄ , s ₅ }. Каждое состояние выполняет 4 действия:

1. Прочтите символ под головой
3. Запишите выходной символ, определяемый состоянием
5. Переместите ленту влево или вправо в зависимости от государства.
7. Перейти в следующее состояние, определяемое текущим состоянием

«Прогон» машинных последовательностей через 16 машинных конфигураций (также известных как состояния Тьюринга):

Поведение этой машины можно описать как цикл: он начинается с s ₁ , заменяет первую 1 на 0, затем использует s ₂ для перемещения вправо, пропуская 1 с и первый встреченный 0. Затем s ₃ пропускает следующую последовательность единиц (изначально их нет) и заменяет первый найденный 0 на 1. s ₄ перемещается назад влево, пропуская единицы, пока не найдет 0 и не переключится на s ₅ . Затем s ₅ перемещается влево, пропуская 1 с, пока не найдет 0, который изначально был записан s ₁ .

Он заменяет 0 на 1, перемещает на одну позицию вправо и снова вводит s ₁ для следующего раунда цикла.

Это продолжается до тех пор, пока s _{1 не} найдет 0 (это 0 в середине двух цепочек единиц), после чего машина остановится.

Альтернативное описание [ править ]

В другом описании проблема заключается в том, как отслеживать количество единиц. Мы не можем использовать одно состояние для каждого возможного числа (состояние для каждого из 0,1,2,3,4,5,6 и т. Д.), Потому что тогда нам понадобятся бесконечные состояния для представления всех натуральных чисел, а конечный автомат конечен - нам придется как-то отследить это с помощью ленты.

Основной способ его работы - копирование каждой «1» на другую сторону, перемещение вперед и назад - он достаточно умен, чтобы запомнить, на какой части пути он находится. Более подробно, он переносит каждую «1» на другую сторону, распознавая разделяющий «0» в середине и распознавая «0» на другой стороне, чтобы знать, что он достиг конца. Он возвращается тем же методом, обнаруживая средний «0», а затем «0» на исходной стороне. Этот «0» на исходной стороне - ключ к разгадке того, как он отслеживает количество единиц.

Хитрость в том, что перед переносом «1» он помечает эту цифру как «взятая», заменяя ее на «0». Когда он возвращается, он заполняет этот «0» снова цифрой «1», затем переходит к следующему , отмечая его «0» и повторяя цикл, перенося эту «1» и так далее. При каждом движении вперед и назад маркер «0» перемещается на один шаг ближе к центру . Вот как он отслеживает, сколько «1» он принял.

Когда он возвращается, маркер «0» выглядит как конец набора «1» для него - любые «1», которые уже были пройдены, невидимы для него (с другой стороны маркера «0» ), и поэтому он как будто работает с (N-1) числом «1» s - аналогично доказательству с помощью математической индукции .

Полный «пробег» с отображением результатов промежуточных «движений». Чтобы лучше его увидеть, нажмите на изображение, а затем нажмите на загрузку с более высоким разрешением:

Занят Бобер с 3 состояниями [ править ]

Следующая таблица инструкций Тьюринга была взята из Peterson (1988), стр. 198, рис. 7.15. Петерсон двигает головой; в следующей модели движется лента.

Рисунок «состояния» занятого бобра с 3 состояниями показывает внутренние последовательности событий, необходимые для фактического выполнения «состояния». Как отмечалось выше, Тьюринг (1937) совершенно ясно дает понять, что это правильная интерпретация 5-кортежей, описывающих инструкцию ( Undecidable , p. 119). Для получения дополнительной информации об атомизации кортежей Тьюринга см. Машину Пост-Тьюринга :

В следующей таблице показан «сжатый» прогон - только состояния Тьюринга:

Полный "пробег" занятого бобра с 3 состояниями. Полученные в результате состояния Тьюринга (то, что Тьюринг назвал «m-конфигурациями» - «конфигурациями машины») выделены серым цветом в столбце A, а также под инструкциями машины (столбцы AF-AU)):

Ссылки [ править ]

Для полных ссылок см. Машину Тьюринга .

• Иварс Петерсон, 1988, Турист по математике: снимки современной математики , WH Freeman and Company, New York, ISBN  0-7167-2064-7 (pbk.). Машины Тьюринга описаны на стр. 194 и далее, пример занятого бобра - на рис. 7.15 на стр. 198.
• Редактор Мартина Дэвиса , 1965, «Неразрешимые: основные статьи о неразрешимых предложениях, неразрешимых задачах и вычислимых функциях» , Raven Press, Нью-Йорк, без ISBN, без номера карточки в каталоге.

• Алан Тьюринг, 1937, О вычислимых числах, с приложением к Entscheidungsproblem , стр. 116 и далее, с кратким комментарием Дэвиса на стр. 115.
• Алан Тьюринг, 1937 г., О вычислимых числах, в приложении к Entscheidungsproblem. Поправка , стр. 152-154.