Машина Тьюринга

Результат обсуждения. Машина Тьюринга должна “понимать”, по цепочке каких букв она идет, т.е. у нее должно быть как минимум два состояния. Пусть состояние q₁ — движение по цепочке из букв “a”, а q₂ — состояние движения по цепочке из букв “b”. Заметим, что цепочка может состоять и из одной буквы. Если мы дошли до конца строки в состоянии q₁ или q₂, т.е. встретили a₀, машина должна остановиться, мы обработали всю строку.

Рассмотрим следующие  варианты входных слов:

bba —> abb

bbbaab —> aabbbb

aabbbaab —> aaaabbbb

Результат обсуждения. Первый вариант входного слова можно последовательно обработать следующим образом: bba —> bbb —> вернуться к левому концу цепочки из букв “b” —> abb (заменить первую букву в этой цепочке на “a”). Для выполнения этих действий нам потребуется ввести два новых состояния и, кроме того, уточнить состояние q₂. Таким образом, для решения этой задачи нам нужно построить машину Тьюринга со следующими состояниями:

q₁ — идем вправо по цепочке букв “a”. Если цепочка заканчивается a₀, то переходим в q₀; если заканчивается буквой “b”, то переходим в q₂;

q₂ — идем вправо по цепочке букв “b”, если цепочка заканчивается a₀, то переходим в q₀; если заканчивается “a”, то заменяем букву “a” на “b”, переходим в состояние q₃ (цепочку вида заменили на цепочку вида );

q₃ — идем влево по цепочке букв “b” до ее левого конца. Если встретили a₀ или “a”, то переходим в q₄;

q₄ — заменяем “b” на “a” и переходим в q₁ (цепочку вида заменяем на цепочку вида .

Задача 7

состояние q₁ — поиск правой (младшей) цифры числа;

состояние q₂ — умножение очередной цифры числа на 2 без прибавления 1 переноса;

состояние q₃ — умножение очередной цифры числа на 2 с прибавлением 1 переноса.

Задача 8

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

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

В этом случае их программа  выглядит следующим образом:

состояние q₁ — поиск разделителя;

состояние q₂ — передвинули штрих;

состояние q₃ — проверка на конец (все ли штрихи передвинули).

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

Задача 9

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

Идея решения (условие останова). На ленте есть два исходных массива штрихов.

Штрихи начинаем стирать  с левого конца массива m. И поочередно стираем самый левый штрих в массиве m и самый правый штрих в массиве n. Но прежде чем стереть правый штрих в массиве n, проверяем, единственный он (т.е. последний, который надо стереть) или нет.

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

Состояние q₁ — поиск разделителя между массивами штрихов при движении справа налево;

состояние q₂ — поиск левого штриха в массиве m;

состояние q₃ — удаление левого штриха в массиве m;

состояние q₄ — поиск разделителя при движении слева направо;

состояние q₅ — поиск правого штриха в массиве n;

состояние q₆ — проверка единственности этого штриха в массиве n, т.е. определяем, был ли он последним;

состояние q₇ — если он был последним, то останов, иначе переход на новый цикл выполнения алгоритма.

Задача 10

При решении этой задачи следует обратить внимание на правильное выписывание алфавита:

A = {a₀, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, Д, А, Н, Е, Т}.

Состояние q₁ — поиск правого конца числа;

состояние q₂ — анализ младшей цифры числа; если она равна “0” или “5”, т.е. число делится на 5, то переход в состояние q₃, иначе переход в состояние q₅;

состояние q₃ — запись буквы “Д” справа от слова на ленте;

состояние q₄ — запись буквы “А” справа от слова и останов машины;

состояние q₅ — запись буквы “Н” справа от слова;

состояние q₆ — запись буквы “Е” справа от слова;

состояние q₇ — запись буквы “Т” справа от слова и останов машины.

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

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

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

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

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

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

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

Список литературы

1. ГСТУ 3008-95. Документация. Отчёты в  сфере науки и техники. Структура  и правила оформления. - Киев: Изд-во стандартов, 1995. – 38 с.

2. Единая система программной  документации / Схемы алгоритмов, программ, данных и систем. Условные обозначения  и правила выполнения. ГОСТ 19.701-90. – М.: Госкомитет СССР по управлению  качеством продукции и стандартизации, 1990. –25 с.

3. Методические указания к курсовому  и дипломному проектированию  для студентов специальности  7.080403: Организация и выполнение  курсовых и дипломных работ  / Сост. В.И. Давыдов,  А.Б. Кунгурцев. – Одесса: ОГПУ, 1994. – 18 с.

4. Методические указания  и задачи  к практическим занятиям по  курсу "Теория алгоритмов и  вычислительных процессов" для  студентов специальности 7.080403  и  7.091501: Часть 1 / О.Н. Паулин, В.М. Рувинская, Е.С. Осадчук – Одесса: ОГПУ, 1996. – 54 с.

5. Гудман С., Хидетниеми С. Введение в разработку и анализ алго-ритмов. -М.: Мир, 1981.- 368 с.

6. Вирт Н. Алгоритмы + структуры  данных = программы.- М.: Мир, 1985. - 406 с.