close

Вход

Забыли?

вход по аккаунту

?

Презентация

код для вставкиСкачать
Курсовая работа
на тему: «Реализация машины Тьринга
на функциональном языке».
по дисциплине «Интеллектуальные
информационные системы»
студент Богданова М.М.
группа 41-ИТ
Орёл, 2012
Цели и задачи
Цель:
создание программы на языке функционального
программирования Haskell, реализующей машину
Тьюринга.
Задачи:
• изучить принцип работы машины Тьюринга;
• выбрать структуры данных для реализации компонентов и
действий машины;
• сформулировать алгоритм решения задачи;
•продемонстрировать работу программы;
•подвести итоги работы.
2
Машина Тьюринга
3
Алгоритм умножения десятичного
числа на 2
4
Описание состояний машины
А
_
0
1
2
3
4
5
6
7
8
9
Q1
_rq2
-
-
-
-
-
-
-
-
-
-
Q2
_sq0
0rq2
2rq2
4rq2
6rq2
8rq2
0rq3
2rq3
4rq3
6rq3
8rq3
Q3
1sq0
1rq2
3rq2
5rq2
7rq2
9rq2
1rq3
3rq3
5rq3
7rq3
9rq3
Q
Q0 – конечное состояние.
5
Структура констант
На языке Haskell множество состояний можно задать в виде
констант, имеющих следующую структуру:
machine(qi, aj, aj1, dk, qi1),
где qi – состояние в котором находится машина,
aj – символ, записанный в указанной ячейке,
aj1 – символ, который будет записан в указанную ячейку,
dk – направление движение указателя (или команда
остановиться),
qi1 – состояние, в которое должна перейти машина.
6
Функции
• Функция start, она «запускает» работу функции turing, задавая стартовые
значения;
• функция get_next получает номер следующего элемента;
• функция get_direction получает необходимое направление движения
считывающей головки;
• функция get_new_symbol получает символ, который нужно записать;
• функция get_new_state получает новое состояние машины;
• функция rewrite_symbol вставляет новый символ на нужную позицию заменяя
старый;
• функция get_structure находит в списке machine нужный кортеж по заданным
первым 2 его элементам;
• функция get_n_elem находит в списке n-ый элемент;
• функции get_first_elem и get_second_elem возвращают соответственно
первый и второй элемент кортежа;
• функция turing «запускает» машину Тьюринга и если передаваемое как
параметр состояние не является конечным, то вызывает рекурсивно сама
себя.
7
Константы
(Q1,'_','_',Right_,Q2), (Q2,'_','_',Stop_,Q0), (Q2,'0','0',Right_,Q2),
(Q2,'1','2',Right_,Q2), (Q2,'2','4',Right_,Q2), (Q2,'3','6',Right_,Q2),
(Q2,'4','8',Right_,Q2), (Q2,'5','0',Right_,Q3), (Q2,'6','2',Right_,Q3),
(Q2,'7','4',Right_,Q3), (Q2,'8','6',Right_,Q3), (Q2,'9','8',Right_,Q3),
(Q3,'_','1',Stop_,Q0), (Q3,'0','1',Right_,Q2), (Q3,'1','3',Right_,Q2),
(Q3,'2','5',Right_,Q2), (Q3,'3','7',Right_,Q2), (Q3,'4','9',Right_,Q2),
(Q3,'5','1',Right_,Q3), (Q3,'6','3',Right_,Q3), (Q3,'7','5',Right_,Q3),
(Q3,'8','7',Right_,Q3), (Q3,'9','9',Right_,Q3)
8
Пример работы программы
9
Заключение
В данной курсовой работе была реализована машина Тьюринга на языке
функционального программирования Haskell. Решенная задача имеет
довольно простой алгоритм, несложную структуру данных, но её
реализация в императивных и событийных языках программирования,
как Pascal, C делает её трудоёмкой и неудобной по сравнению с
реализацией на функциональном языке Haskell.
10
Документ
Категория
Презентации
Просмотров
21
Размер файла
510 Кб
Теги
презентация
1/--страниц
Пожаловаться на содержимое документа