Орядок выполнения задания.

ашина Тюринга.

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

2 Краткие методические указания. Описание математической модели МТ дано в [1]. МТ действует в соответствии с программой, которая представляет собой совокупность строк, соответствующих внутренним состояниям управляющего автомата, а столбцы входным состояниям управляющего автомата. Каждая клетка этой таблицы описывает состояние выхода и функцию перехода в следующее состояние q. Функция выхода определяет символ S, записываемый на ленту и движение головки к следующему такту (L,N,R). Эта математическая модель очень похожа на модель дискретного автомата, которую Вы будете изучать в курсе Дискретная математика.

Каждая строка программы МТ соответствует состоянию МТ. Эта часть программы МТ описывает действие МТ для символа, считываемого с ленты в данном такте. Например, передвинем каретку под последний правый символ слова. В состоянии q₀ MT двигает головку вправо, до тех пор, пока не достигнет пустой клетки. После чего возвращается на одну позицию назад и останавливается. Этот алгоритм можно описать следующим образом:

П1 Запуск

П2 До тех пор пока на ленте не пустой символ сдвигать головку вправо.

П3 Сдвинуть головку влево на одну позицию.

П4 Завершить выполнение.

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

Этому алгоритму будет соответствовать такая программа МТ для слов алфавита А={a,b,c}:

a b c _

0 ,R, ,R, ,R, _,L,!

И схема алгоритма, которая изображена на рисунке 1.

Рис 1. Перемещение каретки к правому концу слова.

Программа МТ и эта схема описана с учетом обозначений для эмулятора МТ, который описан в [2]. В этом эмуляторе пустой символ представляется символом подчеркивание «_», состояние их номерами, а заключительное состояние МТ обозначено символом !. В заключительном состоянии МТ должна прекратить движение головки вдоль ленты, однако этот эмулятор не останавливает головку, а переводит ее в левый конец слова. В этом можно убедиться, если скопировать, описанную выше программу в эмулятор и выполнить ее.

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

Алгоритм перемещения головки до правого конца слов может использоваться и в задаче преобразования слова. Пусть, например, двоичное число представлено словом в алфавите А={0,1,_}, где символы 0 и 1 цифры двоичного числа, а символ «_» соответствует пустому символу. Опишем алгоритм увеличения этого числа на единицу для чисел, в которых младшие разряды размещаются в правой части слова. Так как младшие разряды размещаются справа, а головка МТ при запуске размещается слева, то ее надо переместить вправо до последнего символа. Затем можно перейти к состоянию, в котором будет увеличиваться двоичное число на единицу. Тогда словесное описание алгоритма может быть таким:

П1 Запуск

П2 До тех пор, пока на ленте не пустой символ сдвигать головку вправо.

П3 Переместить головку на одну клетку влево.

П4 Повторять

4.1 Если на ленте 0, то записать 1 и выполнить П5;

4. 2 Если на ленте 1, то записать 0 переместить головку влево;

4.3 Если на ленте пустой символ, то записать 1 и выполнить П5;

П5 Завершить выполнение.

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

Рис 2. Схема алгоритма увеличения двоичного числа на единицу.

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

1 000 0,R,0

­

2 000 0,R,0

­

3 000 0,R,0

­

4 000 _,L,1

­

5 000 1,N,!

­

6 001 МТ остановлена

7 ­

Такое описание работы МТ будем называть трассой работы (трассировкой).

Рассмотрим порядок разработки программы для более сложной постановки задачи. Перевод унарного числа в двоичную систему.

Рассматривается число в унарной (единичной) системе счисления. Требуется получить его представление в двоичной системе.

Для решения этой задачи потребуется алфавит A={|,0,1,=}. Символ | будет использоваться для представления цифр унарного числа, символ 0 будет использоваться для представления цифр двоичного числа, символ 1 будет использоваться для представления цифр двоичного числа и для представления использованных (вычеркнутых) цифр унарного числа, символ = будет использоваться как разделитель между унарным и двоичным числом.

Вначале разместим разделитель = в конце унарного числа. Для этого в состоянии q0 будем двигать головку вправо до конца слова и когда оно закончится то запишем в пустую ячейку символ = и остановиться. Для решения этой задачи может использоваться программа показанная на рисунке 1.

Рис 1 Установка разделителя в конце слова.

После установки разделителя = в конце слова в состоянии q1 передвинем головку в начало слова. Для этого вместо остановки в состоянии q0 запишем команды сдвига головки влево и перейдем в состояние q1. Программа сдвига головки в начало слова показана на рис 2. В программе, которая показана на рисунке 2 реализуется композиция двух алгоритмов. Алгоритма М1, который преобразует слово

в слово

и алгоритма М2, который в слове |= переводит читающую головку в начало слова. Алгоритм М2=М2(М1(Р)) действует на слово |=, полученное алгоритмом М1. Рис 2. Возвращаем головку в начало слова.   Для выполнения деления будем двигать головку влево и каждый четный знак | заменять на 1, а нечетный будем оставлять без изменения. Тогда после достижения конца слова (=) число знаков | будет равно частному от деления. Для этого необходимо ввести два новых состояния q2 и q3. В состоянии q2 будем заменять знаки | на знаки 1 и переходить в состояние q3, а в состоянии q3 никакие знаки менять не будем и если в ячейке знак | будем переходить в состояние q2. После того как головка достигнет разделителя = можно определить значение остатка. Если достигли конца слова в состоянии q2, то число знаков | четное, если в состоянии q3 – то нечетное. На рисунке 3 показана программа, которая выполняет один цикл деления унарного числа на 2. Количество знаков | в результате будет равно частному, а завершающее состояние будет соответствовать остатку. На рисунке 3 показана программа, которая решает эту задачу. Рис 3. Первый цикл деления унарного числа на 2. В этой программе реализуется три алгоритма. Первый алгоритм М1 двигает головку в конец слова и записывает в конце слова символ разделителя =. Второй алгоритм М2 двигает головку в начало слова. Третий алгоритм М3=М3(М2(М1(Р))) двигает головку вправо до разделителя =, определяя частное и остаток. Частное определяется числом символов | в преобразованном слове, а остаток как состояние в котором головка достигла разделителя =. Теперь надо записать значение остатка после разделителя =. Для этого введем состояния q4 и q5. В состоянии q4 будем записывать остаток 0, а в состоянии q5 – 1. Вместо останова в состояниях q4 и q5 передвинем головку вправо и запишем значение остатка. Программа на рисунке 4 реализует композицию 4-х алгоритмов М4=М4(М3(М2(М1(Р)))). Рис 4. Первый цикл деления и запись остатка. Если повторить цикл деления, то очередная цифра остатка, будет записана на место предыдущей цифры остатка.. Поэтому предыдущие цифры остатка надо переписать так как это показано в примере 4 из [1]. После записи значения остатка надо вернуться в начало слова для выполнения следующего деления. Для этого нужно использовать два новых состояния q6 и q7. В состоянии q6 будем двигать головку влево до начала слова, а в состоянии q7 будем завершать выполнение программы, если деление закончено (частичное частное равно 0). Программа перевода числа показана на рисунке 5. Рис 5. В состоянии q6 двигаем каретку влево до тех пор, пока не встретится символ, |. После этого переходим в состояние q1, которое предназначено для перехода к циклу деления в состояниях q3 и q4 после перемещения головки в начало слова. Если в состоянии q6 символ | не встретится, то это значит, что частичное частное равно 0 и процесс перевода надо завершить переход в q7 из q6. Следует обратить внимание, что в состоянии q1 добавлена команда для обработки символов 1, которые записываются в слово на предыдущих циклах деления. После запуска программы показанной на рисунке 5 получим результат, показанный на рисунке 6. Рис 6. Результат перевода унарного числа | в двоичную систему. Программа показанная на рисунке 6 реализует композицию пяти алгоритмов М5=М5(М4(М3(М2(М1(Р))))). На рисунке 7 изображена блок схема реализации этих алгортмов. Рис 7 Схема выполнения алгоритма перевода  

орядок выполнения задания.

3.1Изучить описание, методику программирования [1] и порядок проверки работы программы на эмуляторе МТ. Для каждого из этапов перевода унарного числа в двоичную систему в поле «Комментарии» описать назначение и действие программы.

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

3.4Разработать программу для МТ, которая уменьшает двоичное число на 1.

3.5Разработать и отладить программу 1.(i+2) из [1], где i Ваш номер в классном журнале. В поле комментарии описать действие программы для каждого состояния.

3.6Результаты должны быть задокументированы в Вашем файле с использованием эмулятора [3].

Литература

1 В. Н. Пильщиков, В.Г Абрамов, А.А. Вылиток, И.В. Горячая. Машина Тьюринга и алгоритмы Маркова. Решение задач. (Учебное пособие) М. 2006г (http://cmcmsu.no-ip.info/1course/ электронный ресурс)

2 Эмулятор машины Тьюринга. (электронный ресурс http://cmcmsu.no-ip.info/1course/alg.schema.mt.htm#)

3 Эмулятор МТ Algo2000 – электронный ресурс http://upwap.ru/1184961 .