Презентация к лекции: Машина Тьюринга

ТЕМА: МАШИНА ТЬЮРИНГА

План

• Основные понятия.
• Решение задач
• Применимость машины Тьюринга

1. Основные понятия.

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

Автор машин Тьюринга – английский математик и логик Алан Тьюринг .

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

Состав машины Тьюринга 1. Бесконечная лента, разделенная на ячейки на которой записано слово. 2. Управляющее устройство,которое осуществляет преобразование слова .

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

b

c

a

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

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

Характеристики управляющего устройства удобно записывать в виде таблицы . Обозначения: R – смещение вправо, L – смещение влево, N –отсутствие смещения, ! -останов, q 1 ,.q 2 ,…- состояния, Λ – пустой символ .

Пример. Алфавит символов – {a,b,c} количество состояний – 2.

Λ

q1

a

Λ N !

q2

b

A N !

Λ R q2

Λ R q2

c

Λ R q1

Λ R q2

Λ R q1

Λ R q2

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

Свойства машины Тьюринга как алгоритма

Дискретность . Машина Тьюринга может перейти к (к + 1)-му шагу только после выполнения к-го шага, т.к. именно к-й шаг определяет, каким будет (к + 1)-й шаг.

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

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

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

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

3.Решение задач

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

q1

Λ

q2

a

Λ N !

b

Λ R q2

A N !

Λ R q2

c

Λ R q1

Λ R q1

Λ R q2

Λ R q2

q1

Λ

a

Λ N !

q2

A N !

b

Λ R q2

Λ R q1

c

Λ R q2

Λ R q2

Λ R q1

Λ R q2

Идея алгоритма. Просматриваем слово слева направо, удаляя его символы. Как уже отмечалось, первоначально символы. Как уже отмечалось, первоначально машина Тьюринга находится в состоянии q 1 . Как только встречаем букву ‘a’, переводим в состояние q 2 . По окончании просмотра слова, т.е. по достижению пустого символа, оставляем на этом месте его же,если находимся в состоянии q1 и ставим символ ‘a’, если находимся в состоянии q2. Затем останавливаемся.

Λ

q1

q2

a

Λ N !

b

Λ R q2

A N !

Λ R q2

Λ R q1

c

Λ R q1

Λ R q2

Λ R q2

Λ R q1

c

b

a

c

b

b

a

Λ R q1

b

a

c

b

b

a

Λ R q2

a

c

b

b

a

Исходное слово – cbacbba. Шаг 1 Шаг 2 Шаг 3 Шаг 4 Шаг 5 Шаг 6 Шаг 7 Шаг 8 Итог:

Λ R q2

c

b

b

a

Λ R q2

b

b

a

Λ R q2

b

a

Λ R q2

a

a N !

a

Λ

q1

Λ N !

q2

a

Λ R q2

b

A N !

c

Λ R q1

Λ R q2

Λ R q2

Λ R q1

Λ R q2

Λ R q1

c

b

b

b

b

C

b

C

C

C

Исходное слово – cbbc Шаг 1 Шаг 2 Шаг 3 Шаг 4 Шаг 5 Итог:

Λ R q1

Λ R q1

Λ R q1

Λ R !

Пример 2. Алфавит символов – {0,1,2}.Слово интерпретируется как запись троичного числа. Данная машина Тьюринга прибавляет к троичному числу единицу. Идея алгоритма. Двигаемся по слову слева направо до конца (это необходимо лишь для того, чтобы добраться до правого символа; вначале головка всегда указывает на левый символ).Затем двигаемся по слову справа налево до первого символа-цифры, отличного от ‘2’ и одновременно заменяет все двойки нулями . Затем заменяем найденный (отличая от ‘2’) символ-цифра следующим по своему цифровому значению символом и останавливаемся. Если слово состоит из одних двоек то (после замены их нулями) добавляем слева ‘1’.

Λ

q1

q2

0

Λ L q2

1

1 N !

0 R q1

1 N !

1 R q1

2

2 N !

2 R q1

0 R q2

q1

Λ

q2

0

Λ L q2

1

0 R q1

1 N !

1 R q1

2

1 N !

2 N !

2 R q1

0 R q2

Исходное число: 102. Шаг 1 Шаг 2 Шаг 3 Шаг 4 Шаг 5 Шаг 6 Итог:

1 R q1

1

1

0

0

1

2

0

1

2

0

2

1

1

0

2

0

1

2

1

0

0

0 R q1

2 R q1

Λ L q2

0 R q2

1 N !

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

Пример: 2. Алфавит символов – (0, 1,2). Данная машина Тьюринга прибавляет единицу к троичному числу и возвращает головку на левый символ слова.

q1

Λ

q2

0

Λ L q2

q3

0 R q1

1

1 N !

2

Λ R !

1 l q3

1 R q1

2 R q1

2 l q3

0 l q3

0 l q2

1 l q3

2 l q3

q1

Λ

q2

0

Λ L q2

1 N !

1

0 R q1

q3

1 l q3

1 R q1

2

Λ R !

2 R q1

2 l q3

0 l q3

1 l q3

0 l q2

2 l q3

1 R q1

1

1

0

0

1

2

0

1

2

0

2

1

2

0

1

1

0

2

1

1

0

1

0

1

0

1

0

0 R q1

2 R q1

Λ L q2

Шаг 1 Шаг 2 Шаг 3 Шаг 4 Шаг 5 Шаг 6 Шаг 7 Шаг 8 Итог:

0 l q2

1 l q3

1 l q3

Λ R !

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

q1

Λ

Λ N !

Q2

a

b

Λ R q2

Λ N !

Q3

Λ R q4

Λ N !

q4

Λ R q4

Λ R q3

Λ R q4

Λ N !

Λ R q4

Λ R q4

Λ R q4

У слова ‘ab’ первый символ – ‘a’, второй символ – ‘b’,а третий символ - отсутствует

Λ

q1

a

Λ N !

Q2

b

Λ R q2

Λ N !

Q3

Λ N !

Λ R q4

Λ R q4

q4

Λ N !

Λ R q4

Λ R q3

Λ R q4

Λ R q4

Λ R q4

Λ R q2

a

b

b

a

Λ R q3

Шаг 1 q1 Шаг 2 q2 Шаг 3 q3 Итог:

A N !

Λ

q1

Λ N !

Q2

a

b

Λ R q2

Λ N !

Q3

Λ R q4

q4

Λ R q4

Λ N !

Λ R q3

Λ N !

Λ R q4

Λ R q4

Λ R q4

Λ R q4

Λ R q4

b

a

b

a

b

b

Λ R q4

Шаг 1 q1 Шаг 2 q2 Шаг 3 q3 Шаг 4 q4 Итог:

Λ R q4

Λ N !

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

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

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

q1

Λ

a

Q2

Λ R q1

b

Q3

a R q2

Λ N !

q4

b R q3

a R 1

Λ R q3

Λ R q4

b R q4

a R q4

b R q1

a R q3

b R q2

Λ

q1

a

Λ R q1

Q2

Q3

b

a R q2

Λ N !

a R 1

Четность

b R q3

q4

Λ R q3

Λ R q4

a R q4

b R q4

Чет. чет.

a и b

Нечет. чет.

b R q1

a R q3

b R q2

Чет. Нечет.

Нечет. Нечет.

Машина Тьюринга находится в одном из состояний q1,q2,q3 или q4 в зависимости от четности количеств просмотренных букв ‘a’ и‘b’, как показано в правой колонке таблицы.

Λ

q1

a

Λ R q1

q2

b

a R q2

Λ N !

q3

a R 1

Λ R q3

b R q3

q4

a R q4

b R q4

Λ R q4

b R q1

a R q3

b R q2

a R q2

Исходное слово – ab. Шаг q1 Шаг q2 Шаг q3 Шаг q4 Зацикливание.

a

a

b

a

b

a

b

b

b R q4

Λ R q4

Λ R q4

Λ

q1

a

Λ R q1

q2

b

Λ N !

q3

a R q2

Λ R q3

q4

b R q3

a R 1

b R q4

a R q4

Λ R q4

a R q3

b R q1

b R q2

a R q2

a

a

b

a

b

b

a

b

b

b

b

a

b

b

b

Исходное слово – abb. Шаг q1 Шаг q2 Шаг q3 Шаг q4 Итог:

b R q4

b R q2

Λ N !

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

Λ

q1

Λ N !

a

q2

b

a R q2

Λ N q2

b R q2

a R q2

b R q2

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

q1

Λ

a

Λ N !

q2

Λ N q2

b

a R q2

b R q2

a R q2

b R q2

Исходное слово – ab. Шаг q1 Шаг q2 Шаг q3 Зацикливание.

a R q2

a

a

a

a R q2

a R q2

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

Так, приведенные ниже две машины Тьюринга

Λ

q1

a

Λ R q1

a N q1

Считаются эквивалентными

q1

Λ

a

Λ N !

a N !

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

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

Λ

q1

Λ N !

a

b

a N !

b N q1

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

Пример 3. Алфавит символов – {a,b}. Данная машина Тьюринга применима к любому слову, кроме слово ’ab’. Останавливаемся в каждом из трех случаев: первый символ – не ‘a’, второй символ – не ‘b’,третий символ – не пустой. Зацикливаем в противном случае.

q1

Λ

Λ N !

q2

a

q3

Λ N !

a R q2

b

b N !

Λ R q3

a N !

b R q3

a N !

B N !

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

Контрольные вопросы

• Назовите состав машины Тьюринга.
• Чем характеризуется управляющее устройство?
• От чего зависит действие управляющего устройства машины Тьюринга?
• Что образует систему команд в машине Тьюринга.
• Зависит ли работа машины Тьюринга от исходного состояния машины?