Формирование формального определения и написание программы, реализующей работу машины Тьюринга (Javascript)
КУРСОВОЙ
ПРОЕКТ
по дисциплине
«Дискретные структуры»
на
тему:
Формирование
формального определения и написание программы, реализующей работу машины
Тьюринга (Javascript)
Целью данной курсовой работы является формирование формального определения и
написание программы, реализующей работу машины Тьюринга.
В рамках курсовой работы предусмотрено изучение методик языка Javascript по формализации и
решению поставленной задачи, технологических приемов разработки программ на
языке Javascript, HTML, CSS.
Результатом курсовой работы является html страница, которая
демонстрирует работу поставленной задачи в полном объёме.
МАШИНА ТЬЮРИНГА, ВРЕМЕННАЯ СЛОЖНОСТЬ, АЛФАВИТ, ЛЕНТА, ЯЗЫК,
РАСПОЗНАВАНИЕ, ПРОТОКОЛ, ПРИНАДЛЕЖНОСТЬ
Содержание
Введение
1. Постановка
задачи
2. Формально
определение машины Тьюринга
3. Программная
модель машины Тьюринга
4. Протоколы
работы машины Тьюринга
Вывод
Список
литературы
Приложения
Введение
Алгоритм можно определить как точное предписание о выполнении каких-либо
действий. Существует множество способов формального представления алгоритма.
Например, машины Тьюринга, машины Поста, цепи Маркова. машина
тьюринг программа язык
Машина Тьюринга в качестве формального представления алгоритма была
предложена английским математиком Аланом Тьюрингом в 1937 году. Машина Тьюринга
это простой точный объект, который может являться объектом математического
исследования. Любой алгоритм (были выработаны различные определения алгоритмов
и в итоге все они эквивалентны между собой) может быть реализован машиной
Тьюринга.
Существует множество разновидностей машин Тьюринга: распознающие,
считающие, с накапливающими состояниями и т.д. В общем говоря машина Тьюринга
это совокупность шести объектов:
T=(K, å, G, d, F, q0),
F -
конечное состояние головки машины Тьюринга.
Представленная курсовая работа посвящена распознающим машинам Тьюринга,
как наиболее часто используемому классу машин Тьюринга.
1.
Постановка задачи
Необходимо формально определить машину Тьюринга, распознающую язык
= {wÎ{0, 1}*
іw не содержит 3-х идущих подряд
единиц}
Проверить правильность составления машины Тьюринга на протоколах.
Реализовать программную модель машины Тьюринга.
2. Формально определение машины Тьюринга
q1->1q2R
1q2->1q3R
q3->1q4
q4->BSTOP
q1->0q1R
q2->0q2R
q3->0q3R->BSTOP
K -
множество состояний;
K={q2, q3, }.
S - входной алфавит; S={0, 1}.
Г - ленточный алфавит; Г = {0, 1}.
Q1 - начальное состояние.
В - пустое множество.
STOP-
состояние полной остановки машины;
Файл содержит основные функции, реализующие работу программы.
<p style="line-height: 100%"><font
size="6"><!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01
Transitional//EN" "#"786805.files/image001.gif">
Рис.1 - Окно программы
Рис.2 - Окно команд
Рис.3 - Окно при завершении работы машины Тьюринга