Примеры машины Тьюринга
Ниже приведены примеры, дополняющие статью Машина Тьюринга .
Самый первый пример Тьюринга
[ редактировать ]Следующая таблица представляет собой самый первый пример Тьюринга ( Алан Тьюринг , 1937):
- «1. Можно построить машину для вычисления последовательности 0 1 0 1 0 1...» (0 <пробел> 1 <пробел> 0...) ( Неразрешимо, стр. 119)
| Конфигурация | Поведение | ||
|---|---|---|---|
| м-конфигурация (состояние) | Символ ленты | Ленточные операции | Окончательная m-конфигурация (состояние) |
| б | пустой | П0, Р | с |
| с | пустой | Р | и |
| и | пустой | П1, Р | ж |
| ж | пустой | Р | б |
Относительно того, какие действия на самом деле совершает машина, Тьюринг (1936) ( Неразрешимо, стр. 121) утверждает следующее:
- «Эту [примерную] таблицу (и все последующие таблицы того же типа) следует понимать так, что для конфигурации, описанной в первых двух столбцах, операции в третьем столбце выполняются последовательно, а затем машина переходит в режим m-конфигурация в последнем столбце». (Неразрешимо стр. 121)
Он очень ясно дает это понять, когда сводит приведенную выше таблицу к одной инструкции под названием «b» ( «Неразрешимо» , стр. 120), но его инструкция состоит из 3 строк. Инструкция «b» имеет три различных символьных варианта {Нет, 0, 1}. За каждой возможностью следует последовательность действий, пока мы не дойдем до крайнего правого столбца, где финальная m-конфигурация — «b»:
| Текущая м-конфигурация (инструкция) | Символ ленты | Операции на ленте | Окончательная м-конфигурация (инструкция) |
|---|---|---|---|
| б | Никто | Р0 | б |
| б | 0 | Р, Р, П1 | б |
| б | 1 | Р, Р, П0 | б |
Как заметили ряд комментаторов, включая самого Тьюринга (1937) (например, Пост (1936), Пост (1947), Клини (1952), Ван (1954)) инструкции Тьюринга не являются атомарными — дальнейшие упрощения модели могут быть произведено без снижения его вычислительной мощности; подробнее см. «Машина Пост-Тьюринга» .
Как сказано в статье « Машина Тьюринга» , Тьюринг предложил дополнительно атомизировать свою таблицу, разрешив только одну операцию печати/стирания, за которой следует одно движение ленты L/R/N. Он приводит нам следующий пример преобразованной первой маленькой таблицы ( «Undecidable» , стр. 127):
| Текущая m-конфигурация (состояние Тьюринга) | Символ ленты | Операция печати | Лента-движение | Окончательная m-конфигурация (состояние Тьюринга) |
|---|---|---|---|---|
| д 1 | пустой | Р0 | Р | qq2 |
| qq2 | пустой | P пусто, т.е. E | Р | q 3 |
| q 3 | пустой | П1 | Р | q 4 |
| q 4 | пустой | P пусто, т.е. E | Р | д 1 |
Утверждение Тьюринга по-прежнему подразумевает пять атомарных операций. По заданной команде (m-конфигурация) машина:
- наблюдает за символом ленты под головой
- на основе наблюдаемого символа переходит к соответствующей последовательности инструкций для использования
- печатает символ S j или стирает или ничего не делает
- перемещает ленту влево, вправо или вообще не перемещает
- переходит к окончательной m-конфигурации для этого символа
Поскольку действия машины Тьюринга не являются атомарными, симуляция машины должна атомизировать каждую пятерку в последовательность более простых действий. Одна из возможностей, использованная в следующих примерах «поведения» его машины, заключается в следующем:
- (q i ) Проверьте символ ленты под заголовком: если символ S 0, перейдите к q i .01, если символ S 1, перейдите к q i .11, если символ S 2, перейдите к 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 — символы, которые он называл «цифрами» (как в «двоичных числах»).
В этом примере лента начинается «пустой», а затем на ней печатаются «цифры». Для краткости здесь показаны только ТАБЛИЧНЫЕ состояния:
| Последовательность | Идентификатор инструкции | Голова | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | ||
| 1 | 1 | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
| 2 | 2 | . | . | . | . | . | 0 | . | . | . | . | . | . | . | . | . | . | . | . |
| 3 | 3 | . | . | . | . | . | . | 0 | . | . | . | . | . | . | . | . | . | . | . |
| 4 | 4 | . | . | . | . | . | 1 | . | 0 | . | . | . | . | . | . | . | . | . | . |
| 5 | 1 | . | . | . | . | . | . | 1 | . | 0 | . | . | . | . | . | . | . | . | . |
| 6 | 2 | . | . | . | . | . | 0 | . | 1 | . | 0 | . | . | . | . | . | . | . | . |
| 7 | 3 | . | . | . | . | . | . | 0 | . | 1 | . | 0 | . | . | . | . | . | . | . |
| 8 | 4 | . | . | . | . | . | 1 | . | 0 | . | 1 | . | 0 | . | . | . | . | . | . |
| 9 | 1 | . | . | . | . | . | . | 1 | . | 0 | . | 1 | . | 0 | . | . | . | . | . |
| 10 | 2 | . | . | . | . | . | 0 | . | 1 | . | 0 | . | 1 | . | 0 | . | . | . | . |
| 11 | 3 | . | . | . | . | . | . | 0 | . | 1 | . | 0 | . | 1 | . | 0 | . | . | . |
| 12 | 4 | . | . | . | . | . | 1 | . | 0 | . | 1 | . | 0 | . | 1 | . | 0 | . | . |
| 13 | 1 | . | . | . | . | . | . | 1 | . | 0 | . | 1 | . | 0 | . | 1 | . | 0 | . |
| 14 | 2 | . | . | . | . | . | 0 | . | 1 | . | 0 | . | 1 | . | 0 | . | 1 | . | 0 |
Здесь показан тот же «прогон» со всеми промежуточными распечатками ленты и движениями:
При внимательном рассмотрении таблицы обнаруживаются определенные проблемы с собственным примером Тьюринга — не все символы учтены.
Например, предположим, что его лента изначально не была пустой. Что произойдет? Машина Тьюринга будет считывать значения, отличные от предполагаемых.
Подпрограмма копирования
[ редактировать ]Это очень важная подпрограмма, используемая в процедуре «умножения».
Пример машины Тьюринга обрабатывает строку из 0 и 1, где 0 представлен пустым символом. Его задача — удвоить любую последовательность единиц, встречающуюся на ленте, записывая между ними 0. Например, когда голова читает «111», она пишет 0, затем «111». Результатом будет «1110111».
Для выполнения своей задачи этой машине Тьюринга потребуется всего 5 состояний работы, которые называются {s 1 , s 2 , s 3 , s 4 , s 5 }. Каждое состояние выполняет 4 действия:
- Прочитайте символ под заголовком
- Запишите выходной символ, определенный государством
- Переместить ленту влево или вправо по решению штата.
- Переключиться в следующее состояние, определяемое текущим состоянием
| Начальная м-конфигурация (текущая инструкция) | Символ ленты | Операция печати | Движение ленты | Окончательная m-конфигурация (следующая инструкция) |
|---|---|---|---|---|
| с 1 | 0 | Н | Н | ЧАС |
| с 1 | 1 | И | Р | ss2 |
| ss2 | 0 | И | Р | с 3 |
| ss2 | 1 | П1 | Р | ss2 |
| с 3 | 0 | П1 | л | с 4 |
| с 3 | 1 | П1 | Р | с 3 |
| с 4 | 0 | И | л | с 5 |
| с 4 | 1 | П1 | л | с 4 |
| с 5 | 0 | П1 | Р | с 1 |
| с 5 | 1 | П1 | л | с 5 |
| ЧАС | — | — | — |
Операция печати : печатает символ S или стирает или ничего не делает .
«Прогон» машинных последовательностей через 16 машинных конфигураций (так называемый Тьюринг):
| Последовательность | Идентификатор инструкции | Голова | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | с 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 2 | ss2 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 3 | ss2 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 4 | с 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 5 | с 4 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 6 | с 5 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 7 | с 5 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 8 | с 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 9 | ss2 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 10 | с 3 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| 11 | с 3 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 12 | с 4 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
| 13 | с 4 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 14 | с 5 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 15 | с 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
| 16 | ЧАС | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
Поведение этой машины можно описать как цикл:он начинается с s 1 , заменяет первую 1 на 0, затем использует s 2 для перемещения вправо, пропуская 1 с и первый встреченный 0. s 3 затем пропускает следующую последовательность единиц (изначально их нет) и заменяет первый найденный 0 на 1. s 4 перемещается обратно влево, пропуская 1 с, пока не найдет 0 и не переключится на s 5 . Затем s 5 перемещается влево, пропуская 1 с, пока не найдет 0, который изначально был записан s 1 .
Он заменяет этот 0 на 1, перемещается на одну позицию вправо и снова вводит s 1 для следующего раунда цикла.
Это продолжается до тех пор, пока s 1 не найдет 0 (это 0 в середине двух строк из 1), после чего машина останавливается.
Альтернативное описание
[ редактировать ]В другом описании проблема заключается в том, как отслеживать количество единиц. Мы не можем использовать одно состояние для каждого возможного числа (состояние для каждого из 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» - аналогично доказательству методом математической индукции .
Полный «прогон», показывающий результаты промежуточных «движений». Чтобы увидеть его лучше, нажмите на изображение, затем нажмите на загрузку в более высоком разрешении:
с 3 штатами Занятый бобр
[ редактировать ]Следующая таблица инструкций Тьюринга была получена из Петерсона (1988), стр. 198, рис. 7.15. Петерсон двигает головой; в следующей модели лента движется.
| Символ ленты | Текущее состояние А | Текущее состояние Б | Текущее состояние C | ||||||
|---|---|---|---|---|---|---|---|---|---|
| Написать символ | Переместить ленту | Следующее состояние | Написать символ | Переместить ленту | Следующее состояние | Написать символ | Переместить ленту | Следующее состояние | |
| 0 | 1 | Р | Б | 1 | л | А | 1 | л | Б |
| 1 | 1 | л | С | 1 | Р | Б | 1 | Н | ОСТАНОВКА |
Рисунок «состояния» занятого бобра с тремя состояниями показывает внутренние последовательности событий, необходимые для фактического выполнения «состояния». Как отмечалось выше, Тьюринг (1937) совершенно ясно дает понять, что это правильная интерпретация пятикортежей, описывающих инструкцию ( «Неразрешимо» , стр. 119). Дополнительную информацию об атомизации кортежей Тьюринга из 5 см. в разделе « Машина Пост-Тьюринга» :
В следующей таблице показан «сжатый» прогон — только утверждения Тьюринга:
| Последовательность | Идентификатор инструкции | Голова | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | б | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | Б | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | А | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | С | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | Б | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 6 | А | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 7 | Б | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 8 | Б | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 9 | Б | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 10 | Б | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 11 | Б | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| 12 | А | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 13 | С | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 14 | ЧАС | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Полный «пробег» занятого бобра с 3 состояниями. Результирующие Тьюринг-состояния (то, что Тьюринг назвал «m-конфигурациями» — «конфигурациями машины») выделены серым цветом в столбце A, а также под инструкциями машины (столбцы AF-AU)):
Ссылки
[ редактировать ]Полные ссылки см. в разделе «Машина Тьюринга» .
- Иварс Петерсон, 1988, Математический турист: снимки современной математики , WH Freeman and Company, Нью-Йорк, ISBN 0-7167-2064-7 (пбк.). Машины Тьюринга описаны на стр. 194 и далее, пример занятого бобра показан на рис. 7.15 на стр. 198.
- Редактор Мартина Дэвиса , 1965, «Неразрешимое: основные статьи о неразрешимых предложениях, неразрешимых проблемах и вычислимых функциях» , Raven Press, Нью-Йорк, нет ISBN, нет номера карточного каталога.
- Алан Тьюринг, 1937, «О вычислимых числах с применением к проблеме Entscheidungs» , стр. 116 и далее, с кратким комментарием Дэвиса на странице 115.
- Алан Тьюринг, 1937, «О вычислимых числах с применением к проблеме Entscheidungs». Исправление , с. 152-154.