IX Международная студенческая научная конференция Студенческий научный форум - 2017

Введение. Машины Тьюринга являются важным элементом в изучении курса математической логики и теории алгоритмов. Машина Тьюринга дает один из путей уточнения понятия алгоритма. Известен тезис Тьюринга: «Всякий алгоритм может быть задан посредством тьюринговой функциональной схемы и реализован в соответствующей машине Тьюринга». Многие пытаются опровергнуть эту гипотезу – ищут пример алгоритма, который не может быть реализован с помощью тьюринговой функциональной схемы. Однако на данный момент опровергнуть гипотезу никому не удалось.

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

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

Основные понятия. Машины Тьюринга являются одними из первых аппаратов в исследованиях по теории алгоритмов. Понятие «машин Тьюринга» было введено английским математиком и логиком Аланом Тьюрингом.

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

В состав машины Тьюринга входят: 1) бесконечная лента, разделенная на ячейки, на которой записано слово; 2) управляющее устройство, которое осуществляет преобразование слова.

В каждой ячейке записывается один символ слова. Выделяется особый пустой символ. Он заполняет все ячейки слева и справа от слова. Один из символов ленты является текущим, или, говорят, что на него указывает головка. Текущий символ можно выделять цветом или указывать на него стрелкой.

c

a



Управляющее устройство характеризуется алфавитом символов, из которых может состоять слово, и множеством состояний, в котором оно может находиться. Считается, что в алфавите символов всегда присутствует пустой символ.

Работа управляющего устройства состоит из последовательно выполняющихся тактов.

Каждый такт работы состоит в следующем: 1) чтение текущего символа ленты; 2) запись на его место нового (или, в частном случае, того же самого) символа; 3) смещение головки на одну ячейку влево, вправо или отсутствие смещения; 4) переход в новое состояние (возможно, совпадающее с текущим) или происходит останов (завершение работы).

Характеристики управляющего устройства удобно записывать в виде таблицы, в которой по строкам записываются состояния, а по столбцам символы. При этом используются следующие обозначения: R- смещение головки вправо, L- смещение головки влево, N- отсутствие смещения, ! – останов (т.е. завершение работы), q₁, q₂, … - состояния, ƛ – пустой символ

Пример Машины Тьюринга. Алфавит символов состоит из {a,b,c}. Количество состояний – 2.

	ƛ	a		c
q1	ƛN!	ƛRq2	ƛRq1	ƛRq1
q2	aN!	ƛRq2	ƛRq2	ƛRq2

Пояснение. Возьмем для примера клетку на пересечении состояния q₁ и символа a. В ней записана тройка ƛRq₂-это означает, что если головка указывает на символ a и машина Тьюринга, точнее ее управляющее устройство находится в состоянии q₁, то надо записать в данную клетку символ ƛ, сдвинуть головку на одну позицию вправо и перейти в состояние q₂. Аналогично интерпретируются записи в других клетках.

Действие управляющего устройства в некотором такте зависит от: 1) символа, на который указывает головка, 2) состояния, в котором оно находится.

Считается, что в начальный момент головка указывает на самый символ слова и текущим состоянием является состояние q_1. Считается также, что внутри исходного слова нет пустых символов; если слово пустое, то головка может указывать на любую ячейку ленты.

Практическое применение машины Тьюринга.

Пример 1. Алфавит символов - {a,b,c}. Данная машина Тьюринга преобразует слово следующим образом: если в нем есть хотя бы одна буква «а», то результатом преобразования является слово «а»; если же в слове нет букв «а», то результатом является пустое слово.

	ƛ	a		c
q1	ƛN!	ƛRq2	ƛRq1	ƛRq1
q2	aN!	ƛRq2	ƛRq2	ƛRq2

Идея алгоритма: просматриваем слово слева направо, удаляя его символы, т.е. заменяя каждый символ пустым символом. Как уже отмечалось, первоначально машина Тьюринга находится в состоянии q₁. Как только встретим букву «а», переходим в состояние q₂. По окончании просмотра слова, т.е. по достижении пустого символа, оставляем на этом месте его же, если находимся в состоянии q₁ и ставим символ «а», если находимся в состоянии q₂. Затем останавливаемся.

Последовательность тактов, или последовательность шагов работы данной машины Тьюринга для слова cbacbba. Это слово содержит буквы «а».

ba с bba

Шаг 1. q₁ ƛRq₁

с ba с bba

 

Шаг 2. q₁ ƛRq₁

с bba

Шаг 3. q₁ ƛRq₂

aс bba

 

bba

Шаг 4. q₂ ƛRq₂

ba

Шаг 5. q₂ ƛRq₂

a

Шаг 6. q₂ ƛRq₂

Шаг 7. q₂ ƛRq₂

a

Шаг 8. q₂ƛN!

Итог:

Рассмотрим последовательность шагов работы данной машины Тьюринга для слова cbbc.Это слово не содержит букв «а».

 

с bb с

 

bbc

Шаг 1. q₁ ƛRq₁

bc

Шаг 2. q₁ ƛRq₁

c

Шаг 3. q₁ ƛRq₁

Шаг 4. q₁ ƛRq₁

Шаг 5. q₁ ƛN!

Итог:

Пример 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. q₁1Rq₁

1 0 2

Шаг 2. q₁0Rq₁

1 0 2

Шаг 3. q₁2Rq₁

1 0 2

Шаг 4. q₁ ƛLq₂

1 0 0

Шаг 5. q₂0Lq₂

1 1 0

Шаг 5. q₂1N!

Итог:

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

Рассмотрим пример 2, в котором по окончанию преобразований слова головка ставится на левый символ слова.

	ƛ	0	1	2
q1	ƛLq2	0Rq1	1Rq1	2Rq1
q2	1N!	1Lq3	2Lq3	0Lq2
q3	ƛR!	0Lq3	1Lq3	2Lq3

Преобразование слова 102 выглядит следующим образом:

102

Шаг 1. q₁ 1Rq₁

1 0 2

 

1 0 2

Шаг 2. q₁ 0Rq₁

1 0 2

Шаг 3. q₁ 2Rq₁

1 0 2

Шаг 4. q₁ ƛLq₂

1 0 0

Шаг 5. q₂0Lq₂

1 1 0

Шаг 6. q₂1Lq₃

1 1 0

Шаг 7. q₃1Lq₃

1 1 0

Шаг 8. q₃ƛR!

Итог:

Пример 3. Алфавит символов - {a,b}. Данная машина Тьюринга выдает слово «а» для исходного слова «аb» и пустое слово для любого другого исходного слова.

	ƛ	a
q1	ƛN!	ƛRq2	ƛRq4
q2	ƛN!	ƛRq4	ƛRq3
q3	aN!	ƛRq4	ƛRq4
q4	ƛN!	ƛRq4	ƛRq4

Примечание: у слова «ab»первый символ – «а», второй символ – «b», а третий символ – отсутствует. Необходимо проверить эти три условия.

Преобразование слова «ab»:

Шаг 1. q₁ ƛRq₂

ab

 

Шаг 2. q₂ ƛRq₃

a

Шаг 3. q₃aN!

Итог:

Рассмотрим преобразование слова, отличного от «ab»:

ba b

 

a b

Шаг 1. q₁ ƛRq₄

Шаг 2. q₄ ƛRq₄

Шаг 3. q₄ ƛRq₄

Шаг 4. q₄ ƛN!

Итог:

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

Машина Тьюринга называется неприменимой к некоторому слову, если последовательность шагов преобразования этого слова является бесконечной, т.е. машина Тьюринга зацикливается на этом слове.

Пример 1. Алфавит символов - {a,b}. Данная машина Тьюринга применима к любому слову, содержащему нечетное количество букв «а» и четное количество букв «b»; к другим словам она неприменима.

	ƛ	a
q1	ƛRq1	aRq2	bRq3
q2	ƛN!	aRq1	bRq4
q3	ƛRq3	aRq4	aRq1
q4	ƛRq4	aRq3	aRq2

При просмотре слова текущим состоянием машины Тьюринга является одно из состояний q_1, q₂, q₃ или q₄ в зависимости от четности количеств просмотренных букв «а» и «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

Шаг 1. q₁aRq₂

a b

Шаг 2. q₂bRq₄

a b

Шаг 3. q₃ƛRq₄

Шаг 4. q₄ƛRq₄

Зацикливание.

Рассмотрим работу машины Тьюринга на слове «abb».

ab b

 

a b b

Шаг 1. q₁aRq₂

a b b

Шаг 2. q₂bRq₄

a b b

Шаг 3. q₄bRq₂

a b b

Шаг 4. q₂ ƛN!

Итог:

Машина Тьюринга останавливается после просмотра этого слова.

Пример 2. Алфавит символов - {a,b}. Данная машина Тьюринга применима к пустому слову и неприменима к любому непустому слову.

	ƛ	a
q1	ƛN!	aRq2	bRq2
q2	ƛRq2	aRq2	bRq2

Если слово пустое, то останавливаемся (состояние q₁), иначе переходим в состояние q₂и движемся вправо до бесконечности.

Рассмотрим зацикливание машины Тьюринга на слове, состоящем из одной буквы «a».

Исходное слово – ab.

a

Шаг 1. q₁aRq₂

a

 

a

Шаг 2. q₂ƛRq₂

Шаг 3. q₃ƛRq₂

Зацикливание.

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

1. Текущий символ на ленте не меняется;

2. Состояние не меняется

3. Головка не сдвигается.

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

	ƛ	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

Шаг 1. q₁aRq₂

a b

Шаг 2. q₂bRq₃

a b

Шаг 3. q₃ƛRq₃

Шаг 4. q₃ƛRq₃

Зацикливание.

Исходное слово - abb.

ab b

 

a b b

Шаг 1. q₁aRq₂

a b b

Шаг 2. q₂bRq₃

a b b

Шаг 3. q₃bN!

Итог:

Пример 4. Алфавит символов - {0,1,2}. Слово интерпретируется как запись троичного числа.

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

Данную задачу решает приведенная ниже машина Тьюринга.

	ƛ	0	1	2
q1	ƛRq1	0Rq1	1Rq2	2Rq2
q2	ƛLq3	0Rq2	1Rq2	2Rq2
q3		2Lq3	0N!	1N!

Алгоритм: Если слово – пустое или состоит из нулей, то зацикливаемся (состояние q₁). В противном случае движемся вправо до конца слова (состояние q₂), после чего вычитаем единицу (состояние q₃).

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

Рассмотрим вычитание единицы из слова 20.

2 0

 

2 0

Шаг 1. q₁ 2Rq₂

2 0

Шаг 2. q₂ 0Rq₂

2 0

Шаг 3. q₂ ƛLq₃

2 2

Шаг 4. q₃2Lq₃

Шаг 5. q₃1N!

Итог:

1 2

 

К словам, для которых требуется выполнить некоторое преобразование, машина Тьюринга должна быть применима, т.е. ситуация, когда преобразование правильно выполняется, а затем происходит зацикливание, недопустима.

Данные задачи являются простейшими примерами применения машины Тьюринга.

Эмулятор машин Тьюринга. Эмулятор машин Тьюринга – специальная программа, позволяющая моделировать работу машин Тьюринга. Исходными данными этой программы являются характеристики управляющего устройства машины Тьюринга и исходное слово, а результатом работы программы является слово, получившееся после его преобразования управляющим устройством.

Внешний вид эмулятора выглядит следующим образом:

Рассмотрим несколько задач, составим для их решения программы и проверим алгоритм на эмуляторе.

Пример 1. Алфавит символов - {0,1,2,3,4,5,6,7,8,9}. Данная машина Тьюринга перемещает автомат, заменяет символы.

Пусть Р – непустое слово; значит, Р – это последовательность из десятичных цифр, т.е. запись неотрицательного целого числа вдесятичной системе. Требуется получить на ленте запись числа, которое на 1больше числа Р.

Алгоритм:

1. Перегнать автомат под последнюю цифру числа.

2. Если это цифра от 0 до 8, то заменить её цифрой на 1 больше и остановиться;

3. Если же это цифра 9, тогда заменить её на 0 и сдвинуть автомат кпредыдущей цифре, после чего таким же способом увеличить на 1 этупредпоследнюю цифру;

4. Особый случай: в Р только девятки (например, 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, то надо перейти в состояние q₂, в котором автоматбежит вправо и записывает в конце a. Если же первым был символ b, тогда надоперейти в состояние q₃, где делается всё то же самое, только в конце записывается символ 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}. Задача:прочитать серию книг. Представим серию книг в виде последовательности x₁ x₂ x₃..xn , где n-номер последней книги в серии, а x_i принимают значения а, если номер книги в серии нечетный, и b, если четный. По окончании работы алгоритм должен напечатать слово bb.

	ƛ	a
q1	bRq2	ƛR1	ƛR1
q2	bN0	-	-

Проверим работу алгоритма, взяв за серию книг Л.Н. Толстого «Война и мир» 4 тома: abab.

Результат:

Пример 5. Алфавит символов - {R,L,D}. Задача: доехать до некоторого места на машине и обратно. Представим маршрут в виде последовательности x₁ x₂ x₃..xn , где x_i принимают значения 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.

Результат:

Библиография

1. Машина Тьюринга.Тренажер для изучения универсального исполнителя [Электронный ресурс] — Режим доступа. — URL: http://kpolyakov.narod.ru/prog/turing.htm (дата обращения 26.12.2016).

2. Абрамов В.Г. Машина Тьюринга и алгоритмы Маркова. Решение задач: учебное пособие / В.Г. Абрамов, В.Н. Пильщиков, А.А. Вылиток, И.В. Горячая. - М.: МГУ, 2006. – 47 с.

3. Игошин В.И. Математическая логика и теория алгоритмов: учебное пособие / В.И. Игошин. – М.: Издательский центр «Академия», 2004.-448 с.

4. Носов В.А. Основы теории алгоритмов и анализа их сложности: курс лекций [Электронный ресурс] — Режим доступа. — URL: http://www.twirpx.com/file/39379/ (дата обращения 03.01.2017).

5. Теория алгоритмов. Введение в теорию алгоритмов [Электронный ресурс] — Режим доступа. — URL: http://th-algoritmov.narod.ru/1.htm (дата обращения 28.12.2016).

17

Код для цитирования: Скопировать