Рассмотрим примеры на составление программ для машины Тьюринга. Для сокращения формулировки задач введём следующие два соглашения:
– буквой Р будем обозначать входное слово;
– буквой А будем обозначать алфавит входного слова, т.е. набор тех символов, из которых и только которых может состоять Р (отметим, однако, что в промежуточных и выходном словах могут появляться и другие символы).
Пример 1 (перемещение автомата,замена символов)
А ={0,1,2,3,4,5,6,7,8,9}.Пусть Р –непустое слово;значит, Р –это последовательность из десятичных цифр, т.е. запись неотрицательного целого числа в десятичной системе. Требуется получить на ленте запись числа, которое на 1 больше числа Р.
Решение
Для решения данной задачи выполним следующие действия:
Перегнать автомат под последнюю цифру числа.
Если это цифра от 0 до 8, то заменить её цифрой на 1 больше и остановиться; например:
| → | → | ||||||||||||||||||
| ↑ | ↑ | ↑ |
3. Если же это цифра 9, тогда заменить её на 0 и сдвинуть автомат к предыдущей цифре, после чего таким же способом увеличить на 1 эту предпоследнюю цифру; например:
| → | → | → | ||||||||||||||||||||
| ↑ | ↑ | ↑ | ↑ |
4. Особый случай: в Р только девятки (например, 99). Тогда автомат будет сдвигаться влево, заменяя девятки на нули, и в конце концов окажется под пустой клеткой. В эту пустую клетку надо записать 1 и остановиться (ответом будет 100):
| → | → | → | → | |||||||||||||||||||||||||
| ↑ | ↑ | ↑ | ↑ | ↑ |
В виде программы для МТ эти действия описываются следующим образом:
| Λ | ||||||||||||
| q1 | 0,R,q1 | 1,R,q1 | 2,R,q1 | 3,R,q1 | 4,R,q1 | 5,R,q1 | 6,R,q1 | 7,R,q1 | 8,R,q1 | 9,R,q1 | Λ,L,q2 | |
| q2 | 1,N,! | 2, N,! | 3, N,! | 4, N,! | 5, N,! | 6, N,! | 7, N,! | 8, N,! | 9, N,! | 0,L,q2 | 1,N,! |
Пояснения.
q1 –это состояние,в котором автомат«бежит»под последнюю цифру числа.Для этого он всё время движется вправо, не меняя видимые цифры и оставаясь в том же состоянии. Но здесь есть одна особенность: когда автомат находится под последней цифрой, то он ещё не знает об этом (ведь он не видит, что записано в соседних клетках) и определит это лишь тогда, когда попадёт на пустую клетку. Поэтому, дойдя до первой пустой клетки, автомат возвращается назад под послед-нюю цифру и переходит в состояние q2 (вправо двигаться уже не надо).
q2 –это состояние,в котором автомат прибавляет1к той цифре,которуювидит в данный момент. Сначала это последняя цифра числа; если она – в диапазоне от 0 до 8, то автомат заменяет её цифрой, которая на 1 больше, и останавливается. Но если это цифра 9, то автомат заменяет её на 0 и сдвигается влево, оставаясь в состоянии q2. Тем самым, он будет теперь прибавлять 1 к предыдущей цифре. Если и эта цифра равна 9, то автомат заменяет её на 0 и сдвигается влево, оставаясь по-прежнему в состоянии q2, т.к. должен выполнить то же самое действие – увеличить на 1 видимую цифру. Если же автомат сдвинулся влево, а в видимой клетке нет цифры (а есть «пусто»), то он записывает сюда 1 и останавливается.
Отметим, что для пустого входного слова наша задача не определена, поэтому на этом слове МТ может вести себя как угодно. В нашей программе, например, при пустом входном слове МТ останавливается и выдает ответ 1.
Выше мы привели запись программы в полном, несокращённом виде. Теперь же приведём запись программы в сокращённом, более наглядном виде, при этом справа дадим краткое пояснение действий, которые реализуются в соответствующих состояниях автомата:
| Λ | |||||||||||||
| q1 | ,R, | ,R, | ,R, | ,R, | ,R, | ,R, | ,R, | ,R, | ,R, | ,R, | ,L,q2 | под последнюю цифру | |
| q2 | 1,,! | 2,,! | 3,,! | 4,,! | 5,,! | 6,,! | 7,,! | 8,,! | 9,,! | 0,L, | 1,,! | видимая цифра + 1 | |
Пример 2 (анализ символов)
А ={ a, b, c }.Перенести первый символ непустого слова Р в его конец, как показано в таблице:
| a | b | c | b | → | b | c | b | a |
Решение
Для решения этой задачи предлагается выполнить следующие действия:
1. Запомнить первый символ слова P, а затем стереть этот символ.
2. Перегнать автомат вправо под первую пустую клетку за P и записать в неё запомненный символ.
Как «бегать» вправо, мы уже знаем из предыдущего примера. А вот как запомнить первый символ? Ведь в МТ нет другого запоминающего устройства, кроме ленты, а запоминать символ в какой-то клетке на ленте бессмысленно: как только автомат сдвинется влево или вправо от этой клетки, он тут же забудет данный символ. Что делать?
Выход здесь таков – надо использовать разные состояния автомата. Если первый символ – это a, то надо перейти в состояние q2, в котором автомат бежит вправо и записывает в конце a. Если же первым был символ b, тогда надо перейти в состояние q3, где делается всё то же самое, только в конце запи-сывается символ b. Если же первым был символ c, тогда переходим в состояние q4, в котором автомат дописывает за входным словом символ c. Следовательно, то, каким был первый символ, мы фиксируем переводом автомата в разные состояния. Это типичный приём при программировании на МТ.
Рассмотрим поведение этой программы на входных словах, содержащих не более одного символа. При пустом слове, которое является «плохим» для задачи, программа зациклится – автомат, находясь в состоянии q1 и попадая всё время на пустые клетки, будет бесконечно перемещаться вправо. (Конечно, в этом случае программу можно было бы остановить, но мы специально сделали зацикливание, чтобы продемонстрировать такую возможность.)
Если же во входном слове ровно один символ, тогда автомат сотрёт этот символ, сдвинется на одну клетку вправо и запишет в неё данный символ:
| c | → | → | c | ||||||||||
| ↑ | ↑ | ↑ | |||||||||||
| q1 | q4 | ! |
Таким образом, слово из одного символа попросту сдвинется на клетку вправо. Это допустимо. Ведь клетки ленты не нумерованы, поэтому местоположение слова на ленте никак не фиксируется и перемещение слова влево или вправо заметить нельзя. В связи с этим не требуется, чтобы выходное слово обязательно находилось в том же месте, где было входное слово, результат может оказаться и левее, и правее этого места.
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
1. Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Глава 8. Введение в теорию машин Тьюринга // Введение в теорию автоматов, языков и вычислений. — М.: «Вильямс»,
2002. — С. 528.
2. Фалевич Б.Я. Теория алгоритмов. – М.: ИНФРА-М, 2006. – с.324.
3. https://ru.wikipedia.org/Машина_Тьюринга - 15.01.2013
4. https://inf.1september.ru/articlef.php?ID=200600802 – 15.01.2013
[1] Примечание: длина слова и последовательность символов значения не имеют. На рисунке приводится пример последовательности выполнения команд для конкретного случая. Если на ленте будет другое слово, то и последовательность выполнения команд будет другой. Несмотря на это, данная программа для машины Тьюринга (на рисунке – таблица слева) применима к любым словам описанного внешнего алфавита (соблюдается свойство применимости алгоритма ко всем однотипным задачам – массовость).