Задача № 2: система Тьюринга
КУРСОВАЯ РАБОТА
по дисциплине: «Математическая логика и теория алгоритмов»
Проверил,
Ершов С.С.
2012 г.
Автор работы
студент группы
ПС
2012 г.
Курсовая защищена
с оценкой
2012 г.
Челябинск, 2012 г.
Оглавление
1 Задача № 1: Машина Поста
1.1. Контрольный пример ……………………………………………………………….….3
1.2. Идея решения задачи……………………………………………………………………3
1.3. Схема алгоритма
1.3.1. Крупная схема алгоритма…………………………………………………….....4
1.3.2. Детализированная схема алгоритма………………………………………….....5
1.4. Текст программы………………………………………………………………………..6
1.5. Анализ результатов……………………………………………………………………..6
2 Задача № 2: Машина Тьюринга
2.1. Контрольный пример……………………………………………………………….…..7
2.2. Идея решения задачи………………………………………………….………………...7
2.3. Граф состояний переходов...…………………………………………………………...8
2.4. Таблица состояний переходов………………………………………………………....9
2.5. Анализ результатов…………………………………………………………………..…9
Библиографический список……………………………………………………………..….….10
Задача № 1: Машина Поста
Для машины Поста составить программу, выполняющую умножение цифр «3» и «2».
1.1 Контрольный пример
Рисунок 1 отражает начальную конфигурацию. Рисунок 2 стандартную конечную конфигурацию.
Рис. 1. Стандартная начальная конфигурация
Рис. 2. Стандартная конечная конфигурация
1.2 Идея решения задачи
Идея решения состоит в том, что после нахождения конца группы меток, головка возвращается обратно, ставя метку в пустую ячейку между двумя группами меток. На каждом шаге, ячейка проверяется на наличие метки. При условии наличия метки в ячейке выполняется дальнейшее перемещение каретки вправо. В случае отсутствия метки, выполняется перемещение каретки на одну ячейку вправо. Если в следующей ячейке отсутствует метка, головка начинает движение в обратном направлении. В завершении работы алгоритма, на ленте, ставится метка между двумя, найденными, группами меток.
1.3. Схема алгоритма
1.3.1. Крупная схема алгоритма
Рис. 3. Крупная схема алгоритма
1.3.2. Детализированная схема алгоритма
|
|
Рис. 4. Детализированная схема алгоритма
1.4 Текст программы
В детализированной схеме алгоритма 17 блоков, а значит, в программе будет 17 команд.
Сложение трёх целых чисел Таблица 1
| Адрес | Операция | Адрес перехода (по 0 или безусловный) | Адрес перехода (по 1) |
| Условный переход | |||
| Шаг влево | |||
| Шаг вправо | |||
| Условный переход | |||
| Шаг вправо | |||
| Шаг вправо | |||
| Шаг вправо | |||
| Шаг вправо | |||
| Шаг вправо | |||
| Шаг влево | |||
| Шаг влево | |||
| Шаг влево | |||
| Шаг влево | |||
| Поставить метку | |||
| Шаг влево | |||
| Шаг влево | |||
| Стоп |
1.5 Анализ результатов
Разработанная программа весьма универсальна, так как она учитывает начальное положение головки не только над меткой, но и над пустой ячейкой. Размер программы получился сравнительно небольшой (16 команд).
Программа была написана, проверена и отлажена в системе POST 2002. Результаты тестов показывают правильность ее работы.
Задача № 2: система Тьюринга
Для машины Тьюринга составить программу, выполняющую вычитание чисел в троичной системе счисления.
1.
2.
2.1. Контрольный пример
В качестве примера возьмём цифры девять и пять, записанные в троичной системе счисления: 100 и 12.
Рис. 5. Стандартная начальная конфигурация
Рис. 6. Стандартная конечная конфигурация
2.2. Идея решения задачи
Идея решения состоит в том, что на ленте расположены числа, записанные в троичной системе счисления. Головка двигается до последней метки, со значением «2», обозначающей то, что чисел больше не будет (последняя метка), а затем возвращается, удаляя и перезаписывая метки, реализуя, вычитание в троичной системе счисления.
2.3. Граф состояний и переходов
Рис. 6. Граф состояний и переходов программы
2.4. Таблица состояний и переходов
Вычитание чисел в троичной системе счисления Таблица 2
| Состояние | * | |||
| q1 | q2 R | q2 R | q2 R | q7 ^L |
| q2 | q3 R | q3 R | q3 R | q7 ^L |
| q3 | q4 R | q4 R | q4 R | q7 ^L |
| q4 | q5 R | q5 R | q5 R | q7 ^L |
| q5 | q6 R | q6 R | q6 R | q7 ^L |
| q6 | q7 R | q7 R | q7 R | q7 ^L |
| q7 | q8 ^L | q8 ^L | q8 ^L | q8 ^L |
| q8 | q9 ^L | q9 ^L | q9 ^L | q9 ^L |
| q9 | q10 ^L | q10 ^L | q10 ^L | q10 ^L |
| q10 | q11 1L | q11 L | q11 ^L | q11 ^L |
| q11 | qz 1L | qz L | qz 1L | qz 1L |
1.5. Анализ результатов
Разработанная программа работает, вычитая числа в троичной системе счисления. Эта программа работает на практике. Она всегда дает точный и правильный результат. Размер программы получился достаточно небольшой ( операции).
Программа была написана, проверена и отлажена в системе MT. Результаты тестов показывают правильность её работы.
Библиографический список
1. Ершов С.С., Надточий И.Л., Самохвалов В.А. Прикладная математика: Учебное пособие по практическим занятиям.- Челябинск: ЧГТУ, 1992.
2. Успенский В.А. Машина Поста.- М.: Наука, 1979.
3. Ершов С.С. Элементы теории алгоритмов: Учебное пособие. Челябинск: Издательский центр ЮУрГУ, 2009.