Цель работы: разработать методические материалы для студентов по теме «Машины Тьюринга» для изучения курса теории алгоритмов.
Данные материалы полезны при первоначальном знакомстве с понятием машины Тьюринга. Теоретический материал изложен очень лаконично и поэтому будет понятен любому человеку, желающему расширить свой кругозор. Тема раскрывается посредством многообразия примеров и задач со схематическим изображением.
Основные понятия. Машины Тьюринга являются одними из первых аппаратов в исследованиях по теории алгоритмов. Понятие «машин Тьюринга» было введено английским математиком и логиком Аланом Тьюрингом.
Машина Тьюрингапредставляет собой гипотетический аппарат преобразования слов. Под словом понимается произвольная последовательность символов, входящих в алфавит символов (обычно это или цифры, или начальные буквы латинского алфавита).
В состав машины Тьюринга входят: 1) бесконечная лента, разделенная на ячейки, на которой записано слово; 2) управляющее устройство, которое осуществляет преобразование слова.
В каждой ячейке записывается один символ слова. Выделяется особый пустой символ. Он заполняет все ячейки слева и справа от слова. Один из символов ленты является текущим, или, говорят, что на него указывает головка. Текущий символ можно выделять цветом или указывать на него стрелкой.
c |
a |
||||||||||||||||||
|
Управляющее устройство характеризуется алфавитом символов, из которых может состоять слово, и множеством состояний, в котором оно может находиться. Считается, что в алфавите символов всегда присутствует пустой символ.
Работа управляющего устройства состоит из последовательно выполняющихся тактов.
Каждый такт работы состоит в следующем: 1) чтение текущего символа ленты; 2) запись на его место нового (или, в частном случае, того же самого) символа; 3) смещение головки на одну ячейку влево, вправо или отсутствие смещения; 4) переход в новое состояние (возможно, совпадающее с текущим) или происходит останов (завершение работы).
Характеристики управляющего устройства удобно записывать в виде таблицы, в которой по строкам записываются состояния, а по столбцам символы. При этом используются следующие обозначения: R- смещение головки вправо, L- смещение головки влево, N- отсутствие смещения, ! – останов (т.е. завершение работы), q1, q2, … - состояния, ƛ – пустой символ
Пример Машины Тьюринга. Алфавит символов состоит из {a,b,c}. Количество состояний – 2.
ƛ |
a |
c |
||
q1 |
ƛN! |
ƛRq2 |
ƛRq1 |
ƛRq1 |
q2 |
aN! |
ƛRq2 |
ƛRq2 |
ƛRq2 |
Пояснение. Возьмем для примера клетку на пересечении состояния q1 и символа a. В ней записана тройка ƛRq2-это означает, что если головка указывает на символ a и машина Тьюринга, точнее ее управляющее устройство находится в состоянии q1, то надо записать в данную клетку символ ƛ, сдвинуть головку на одну позицию вправо и перейти в состояние q2. Аналогично интерпретируются записи в других клетках.
Действие управляющего устройства в некотором такте зависит от: 1) символа, на который указывает головка, 2) состояния, в котором оно находится.
Считается, что в начальный момент головка указывает на самый символ слова и текущим состоянием является состояние q1. Считается также, что внутри исходного слова нет пустых символов; если слово пустое, то головка может указывать на любую ячейку ленты.
Практическое применение машины Тьюринга.
Пример 1. Алфавит символов - {a,b,c}. Данная машина Тьюринга преобразует слово следующим образом: если в нем есть хотя бы одна буква «а», то результатом преобразования является слово «а»; если же в слове нет букв «а», то результатом является пустое слово.
ƛ |
a |
c |
||
q1 |
ƛN! |
ƛRq2 |
ƛRq1 |
ƛRq1 |
q2 |
aN! |
ƛRq2 |
ƛRq2 |
ƛRq2 |
Идея алгоритма: просматриваем слово слева направо, удаляя его символы, т.е. заменяя каждый символ пустым символом. Как уже отмечалось, первоначально машина Тьюринга находится в состоянии q1. Как только встретим букву «а», переходим в состояние q2. По окончании просмотра слова, т.е. по достижении пустого символа, оставляем на этом месте его же, если находимся в состоянии q1 и ставим символ «а», если находимся в состоянии q2. Затем останавливаемся.
Последовательность тактов, или последовательность шагов работы данной машины Тьюринга для слова cbacbba. Это слово содержит буквы «а».
ba с bba
|
с ba с bba
с bba
|
aс bba
bba
|
ba
|
a
|
a
|
Рассмотрим последовательность шагов работы данной машины Тьюринга для слова cbbc.Это слово не содержит букв «а».
с bb с
bbc
|
bc
|
c
|
Пример 2. Алфавит символов - {0,1,2}. Слово интерпретируется как запись троичного числа. Данная машина Тьюринга прибавляет к троичному числу единицу.
ƛ |
0 |
1 |
2 |
|
q1 |
ƛLq2 |
0Rq1 |
1Rq1 |
2Rq1 |
q2 |
1N! |
1N! |
2N! |
0Lq2 |
Идея алгоритма в том, что мы в начале двигаемся по слову слева направо до конца (это необходимо лишь для того, чтобы добраться до правого символа; вначале головка всегда указывает на левый символ). Затем двигаемся по слову справа налево до первого символа-цифры, отличного от «2» и одновременно заменяем все двойки нулями. Затем заменяем найденный (отличный от «2») символ-цифру следующим по своему цифровому значению символом и останавливаемся. Если слово состоит из одних двоек, то (после замены их нулями) добавляем слева «1».
Исходное слово: 102.
1 0 2
102
|
1 0 2
|
1 0 2
|
1 0 2
|
1 0 0
|
1 1 0
|
В некоторых случаях на машину Тьюринга накладывается дополнительное условие: по окончании преобразования слова головка должна указывать на левый символ полученного слова. Это условие не является обязательным. Оно необходимо в случае, когда надо несколько раз последовательно преобразовать слово одной и той же или разными машинами Тьюринга, так как в начале каждого преобразования головка должна указывать на левый символ слова. Данное действие обычно реализуется с помощью дополнительного состояния машины Тьюринга.
Рассмотрим пример 2, в котором по окончанию преобразований слова головка ставится на левый символ слова.
ƛ |
0 |
1 |
2 |
|
q1 |
ƛLq2 |
0Rq1 |
1Rq1 |
2Rq1 |
q2 |
1N! |
1Lq3 |
2Lq3 |
0Lq2 |
q3 |
ƛR! |
0Lq3 |
1Lq3 |
2Lq3 |
Преобразование слова 102 выглядит следующим образом:
102
|
1 0 2
1 0 2
|
1 0 2
|
1 0 2
|
1 0 0
|
1 1 0
|
1 1 0
|
1 1 0
|
Пример 3. Алфавит символов - {a,b}. Данная машина Тьюринга выдает слово «а» для исходного слова «аb» и пустое слово для любого другого исходного слова.
ƛ |
a |
||
q1 |
ƛN! |
ƛRq2 |
ƛRq4 |
q2 |
ƛN! |
ƛRq4 |
ƛRq3 |
q3 |
aN! |
ƛRq4 |
ƛRq4 |
q4 |
ƛN! |
ƛRq4 |
ƛRq4 |
Примечание: у слова «ab»первый символ – «а», второй символ – «b», а третий символ – отсутствует. Необходимо проверить эти три условия.
Преобразование слова «ab»:
|
ab
a
|
Рассмотрим преобразование слова, отличного от «ab»:
ba b
a b
|
|
Применимость машин Тьюринга к словам. Машина Тьюринга называется применимой к некоторому слову, если последовательность шагов преобразования этого слова является конечной, т.е. если после нескольких шагов преобразования слова (возможно, сразу) работа машины Тьюринга завершается.
Машина Тьюринга называется неприменимой к некоторому слову, если последовательность шагов преобразования этого слова является бесконечной, т.е. машина Тьюринга зацикливается на этом слове.
Пример 1. Алфавит символов - {a,b}. Данная машина Тьюринга применима к любому слову, содержащему нечетное количество букв «а» и четное количество букв «b»; к другим словам она неприменима.
ƛ |
a |
||
q1 |
ƛRq1 |
aRq2 |
bRq3 |
q2 |
ƛN! |
aRq1 |
bRq4 |
q3 |
ƛRq3 |
aRq4 |
aRq1 |
q4 |
ƛRq4 |
aRq3 |
aRq2 |
При просмотре слова текущим состоянием машины Тьюринга является одно из состояний q1, q2, q3 или q4 в зависимости от четности количеств просмотренных букв «а» и «b», как показано в правой колонке таблицы.
ƛ |
a |
Четность a и b |
||
q1 |
ƛRq1 |
aRq2 |
bRq3 |
чет.чет. |
q2 |
ƛN! |
aRq1 |
bRq4 |
нечет.чет. |
q3 |
ƛRq3 |
aRq4 |
aRq1 |
чет.нечет. |
q4 |
ƛRq4 |
aRq3 |
aRq2 |
нечет.нечет. |
Рассмотрим зацикливание машины Тьюринга на слове «ab».
Исходное слово – ab.
ab
a b
|
a b
|
a b
|
Зацикливание.
Рассмотрим работу машины Тьюринга на слове «abb».
ab b
a b b
|
a b b
|
a b b
|
a b b
|
Машина Тьюринга останавливается после просмотра этого слова.
Пример 2. Алфавит символов - {a,b}. Данная машина Тьюринга применима к пустому слову и неприменима к любому непустому слову.
ƛ |
a |
||
q1 |
ƛN! |
aRq2 |
bRq2 |
q2 |
ƛRq2 |
aRq2 |
bRq2 |
Если слово пустое, то останавливаемся (состояние q1), иначе переходим в состояние q2и движемся вправо до бесконечности.
Рассмотрим зацикливание машины Тьюринга на слове, состоящем из одной буквы «a».
Исходное слово – ab.
a
|
a
a
|
Зацикливание.
Замечание. Машина Тьюринга считается применимой к некоторому слову не только в случае, если последовательность шагов преобразования является конечной, но и в случае, если на некотором шаге происходит выполнение трех условий:
Текущий символ на ленте не меняется;
Состояние не меняется
Головка не сдвигается.
Приведенные ниже две машины Тьюринга являются эквивалентными, несмотря на то, что для первой из них последовательность шагов на любом слове формально является бесконечной, а вторая сразу останавливается.
ƛ |
a |
|
q1 |
ƛNq1 |
aNq1 |
ƛ |
a |
|
q1 |
ƛN! |
aN! |
Поэтому задачу применимости только к пустому слову нельзя решить с помощью приведенной ниже машины Тьюринга.Она применима к любому слову.
ƛ |
a |
||
q1 |
ƛN! |
aNq1 |
bNq1 |
Пример 3. Алфавит символов - {a,b}. Данная машина Тьюринга применима к любому слову, кроме слова «ab».
ƛ |
a |
||
q1 |
ƛN! |
ƛRq2 |
bN! |
q2 |
ƛN! |
aN! |
bRq3 |
q3 |
ƛRq3 |
aN! |
bN! |
Останавливаемся в каждом из трех случаев: первый символ – не «а», второй символ – не «b», третий символ – не пустой. Зацикливаемся в противном случае.
Исходное слово - ab.
ab
a b
|
a b
|
a b
|
Зацикливание.
Исходное слово - abb.
ab b
a b b
|
a b b
|
a b b
|
Пример 4. Алфавит символов - {0,1,2}. Слово интерпретируется как запись троичного числа.
Требуется составить машину Тьюринга, вычитающую из ненулевого троичного числа единицу и неприменимую к нулевому троичному числу, а также к пустому слову.
Данную задачу решает приведенная ниже машина Тьюринга.
ƛ |
0 |
1 |
2 |
|
q1 |
ƛRq1 |
0Rq1 |
1Rq2 |
2Rq2 |
q2 |
ƛLq3 |
0Rq2 |
1Rq2 |
2Rq2 |
q3 |
2Lq3 |
0N! |
1N! |
Алгоритм: Если слово – пустое или состоит из нулей, то зацикливаемся (состояние q1). В противном случае движемся вправо до конца слова (состояние q2), после чего вычитаем единицу (состояние q3).
Как следует из алгоритма решения задачи, в состоянии q3головка никогда не указывает на пустой символ. Поэтому соответствующую клетку не заполняем.
Рассмотрим вычитание единицы из слова 20.
2 0
2 0
|
2 0
|
2 0
|
2 2
|
1 2
К словам, для которых требуется выполнить некоторое преобразование, машина Тьюринга должна быть применима, т.е. ситуация, когда преобразование правильно выполняется, а затем происходит зацикливание, недопустима.
Данные задачи являются простейшими примерами применения машины Тьюринга.
Эмулятор машин Тьюринга. Эмулятор машин Тьюринга – специальная программа, позволяющая моделировать работу машин Тьюринга. Исходными данными этой программы являются характеристики управляющего устройства машины Тьюринга и исходное слово, а результатом работы программы является слово, получившееся после его преобразования управляющим устройством.
Внешний вид эмулятора выглядит следующим образом:
Рассмотрим несколько задач, составим для их решения программы и проверим алгоритм на эмуляторе.
Пример 1. Алфавит символов - {0,1,2,3,4,5,6,7,8,9}. Данная машина Тьюринга перемещает автомат, заменяет символы.
Пусть Р – непустое слово; значит, Р – это последовательность из десятичных цифр, т.е. запись неотрицательного целого числа вдесятичной системе. Требуется получить на ленте запись числа, которое на 1больше числа Р.
Алгоритм:
Перегнать автомат под последнюю цифру числа.
Если это цифра от 0 до 8, то заменить её цифрой на 1 больше и остановиться;
Если же это цифра 9, тогда заменить её на 0 и сдвинуть автомат кпредыдущей цифре, после чего таким же способом увеличить на 1 этупредпоследнюю цифру;
Особый случай: в Р только девятки (например, 99). Тогда автомат будетсдвигаться влево, заменяя девятки на нули, и в конце концов окажется под пустойклеткой. В эту пустую клетку надо записать 1 и остановиться (ответом будет 100).
Составим программу:
ƛ |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
q1 |
ƛLq2 |
0Rq1 |
1Rq1 |
2Rq1 |
3Rq1 |
4Rq1 |
5Rq1 |
6Rq1 |
7Rq1 |
8Rq1 |
9Rq1 |
q2 |
1N! |
1N! |
2N! |
3N! |
4N! |
5N! |
6N! |
7N! |
8N! |
9N! |
0Lq2 |
Проверим выполнение алгоритма на эмуляторе, взяв за исходное слово –число5139.
Результат:
Пример 2. Алфавит символов - {a,b}. Данная машина Тьюринга переставляет первый символ слова в его конец.
Для решения этой задачи предлагается выполнить следующие действия:
1. Запомнить первый символ слова P, а затем стереть этот символ.
2. Перегнать автомат вправо под первую пустую клетку за P и записать в неё запомненный символ. Для этого надо использовать разные состояния автомата. Если первый символ – это a, то надо перейти в состояние q2, в котором автоматбежит вправо и записывает в конце a. Если же первым был символ b, тогда надоперейти в состояние q3, где делается всё то же самое, только в конце записывается символ b.
Следовательно, то, каким был первый символ, мы фиксируем переводом автомата в разныесостояния. С учетом сказанного программа будет такой:
ƛ |
a |
||
q1 |
ƛN! |
ƛRq2 |
ƛRq3 |
q2 |
аN! |
aRq2 |
bRq2 |
q3 |
bN! |
aRq3 |
ƛRq3 |
Проверим выполнение алгоритма на эмуляторе, взяв за исходное слово –abba
Результат:
Пример 3. Алфавит символов - {0,1}. Данная машина Тьюринга делит двоичное число на 2. (Удаляем правую цифру, а, если она единственная, то добавляем 0). Программа имеет следующий вид:
ƛ |
0 |
1 |
|
q1 |
ƛLq2 |
0Rq1 |
1Rq1 |
q2 |
ƛLq3 |
ƛLq3 |
|
q3 |
0N! |
0N! |
1N! |
Проверим выполнение алгоритма на эмуляторе, взяв за исходное слово – 101.
Результат:
Рассмотрим несколько задач на применимость машины Тьюринга в повседневной жизни.
Пример 4. Алфавит символов - {a,b}. Задача:прочитать серию книг. Представим серию книг в виде последовательности x1 x2 x3..xn , где n-номер последней книги в серии, а xi принимают значения а, если номер книги в серии нечетный, и b, если четный. По окончании работы алгоритм должен напечатать слово bb.
ƛ |
a |
||
q1 |
bRq2 |
ƛR1 |
ƛR1 |
q2 |
bN0 |
- |
- |
Проверим работу алгоритма, взяв за серию книг Л.Н. Толстого «Война и мир» 4 тома: abab.
Результат:
Пример 5. Алфавит символов - {R,L,D}. Задача: доехать до некоторого места на машине и обратно. Представим маршрут в виде последовательности x1 x2 x3..xn , где xi принимают значения R — поворот направо, L — поворот налево, D — движение прямо.
По окончании работы алгоритм должен «затереть» входное слово, то есть напечатать последовательность пустых символов. Таким образом, нужно пройти входное слово слева направо, заменив символы R на L, L на R, и оставив символ D, а затем справа налево, заменив все символы пустыми символами.
1 |
2 |
|
ƛ |
ƛL2 |
ƛL0 |
R |
LП1 |
ƛL2 |
L |
RП1 |
ƛL2 |
D |
DП1 |
ƛL2 |
Проверим работу алгоритма, выбрав произвольный маршрут: RRDRRLLDLLR.
Результат:
Библиография
Машина Тьюринга.Тренажер для изучения универсального исполнителя [Электронный ресурс] — Режим доступа. — URL: http://kpolyakov.narod.ru/prog/turing.htm (дата обращения 26.12.2016).
Абрамов В.Г. Машина Тьюринга и алгоритмы Маркова. Решение задач: учебное пособие / В.Г. Абрамов, В.Н. Пильщиков, А.А. Вылиток, И.В. Горячая. - М.: МГУ, 2006. – 47 с.
Игошин В.И. Математическая логика и теория алгоритмов: учебное пособие / В.И. Игошин. – М.: Издательский центр «Академия», 2004.-448 с.
Носов В.А. Основы теории алгоритмов и анализа их сложности: курс лекций [Электронный ресурс] — Режим доступа. — URL: http://www.twirpx.com/file/39379/ (дата обращения 03.01.2017).
Теория алгоритмов. Введение в теорию алгоритмов [Электронный ресурс] — Режим доступа. — URL: http://th-algoritmov.narod.ru/1.htm (дата обращения 28.12.2016).
17