Автор работы: Пользователь скрыл имя, 15 Марта 2015 в 16:45, курсовая работа
Слово «алгоритм» происходит от algorithmi – латинского написания имени узбекского математика и астронома, жившего в VIII–IX веках (783-850 гг.), Мухаммеда бен Мусы аль-Хорезми. Под этим именем в Средневековой Европе знали величайшего математика из Хорезма (город в современном Узбекистане). В своей книге «Об индийском счете» он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними. Затем понятие алгоритма стало использоваться в более широком смысле и не только в математике. Как для математиков, так и для практиков понятие алгоритма имеет важное значение.
Например, если в начальный момент на ленте записано слово a1Λa2a1a1, то начальная конфигурация будет иметь вид:
a1 a2 Λ a1 a1
q1
(под клеткой, над которой находится головка, указывается внутреннее состояние машины).
Работа машины Тьюринга состоит в последовательном применении команд, причем, применение той или команды определяется текущей конфигурацией. Так в приведенном выше примере должна применится команда с левой частью q1a1.
Итак, зная программу и задав начальную конфигурацию, полностью определяем работу машины над словом в начальной конфигурации.
Если в работе машины Тьюринга в некоторый момент t выполняется команда, правая часть которой содержит q0, то в такой момент работа машины считается законченной, и говорят, что машина применима к слову на ленте в начальной конфигурации. В самом деле, q0 не встречается в левой части ни одной команды – этим и объясняется название q0 «заключительное состояние». Результатом работы машины в таком случае считается слово, которое будет записано на ленте в заключительной конфигурации, т. е. в конфигурации, в которой внутреннее состояние машины есть q0. Если же в работе машины ни в один из моментов не реализуется команда с заключительным состоянием, то процесс вычисления будет бесконечным. В этом случае говорят, что машина не применима к слову на ленте в начальной конфигурации.
Программы в виде таблиц
Перенос нуля: 0s 01x => 0s01x0
Реализация:
Начальное состояние
Промежуточное состояние
Конечное состояние
Правый сдвиг (Б+): 0s 1x0 => 01x0s0
Реализация:
Начальное
состояние
Конечное состояние
Последним действием будет переход каретки вправо и выход из алгоритма
Левый сдвиг (Б ) : 01x0 s => 0s01x0
Реализация:
Начальное
состояние
Конечное состояние
Последним действием будет переход каретки влево и выход из алгоритма
Транспозиция (Т) : 01x0s 1y0 => 01y0s01x0
Реализация:
Начальное
состояние
Промежуточное состояние
Конечное состояние
Последним действием будет переход каретки влево и выход из алгоритма
Копирование (Kn) : 0s
1x101x201x30…01xn =>
0s11x101x201x30…01xn 01x101x20
Реализация:
Начальное
состояние
Промежуточное состояние
Конечное состояние
Последним действием будет переход каретки влево и выход из алгоритма
Удаление единиц слева: 01x101x20…0s
1xn0 =>
0…0s01xn0
Реализация:
Начальное
состояние
Промежуточное
состояние
Конечное
состояние
Сложение: q101y+10=> q101x+y+1000
Реализация:
Начальное
состояние
Конечное состояние
Умножение: q01x+101y+1=>q001x*y+10
Реализация:
Начальное
состояние
Конечное состояние
Программа умножения ход выполнения
Программа выполняет операцию (x*y)
Шаг 1
Шаг 20
Шаг 40
Шаг 60
Шаг 80
Шаг 101
Шаг 150
Шаг 202
Конечный шаг
Извините я не успел доделать! К следущей дате все сделаю!