Формально определение машины Тьюринга

КУРСОВОЙ ПРОЕКТ

по дисциплине «Дискретные структуры»

на тему:

__________________________________________________________

(наименование темы)

 

 

Проект разработал студент

__________________________

Группы

_______________________

Руководитель проекта

__________________________

 

Оценка________________

 

2012г.

 

РЕФЕРАТ

Пояснительная записка курсовой работы:

24 страниц, 3 рисунка, 0 таблиц.

Целью данной курсовой работы является формирование формального определения и написание программы, реализующей работу машины Тьюринга. В рамках курсовой работы предусмотрено изучение методик языка Javascript по формализации и решению поставленной задачи, технологических приемов разработки программ на языке Javascript, HTML, CSS.

Результатом курсовой работы является html страница, которая демонстрирует работу поставленной задачи в полном объёме.

 

МАШИНА ТЬЮРИНГА, ВРЕМЕННАЯ СЛОЖНОСТЬ, АЛФАВИТ, ЛЕНТА, ЯЗЫК, РАСПОЗНАВАНИЕ, ПРОТОКОЛ, ПРИНАДЛЕЖНОСТЬ

 

СОДЕРЖАНИЕ

ВВЕДЕНИЕ………………………………………………………………..4

2.ПОСТАНОВКА ЗАДАЧИ………………………………………............5

3.ФОРМАЛЬНО ОПРЕДЕЛЕНИЕ МАШИНЫ ТЬЮРИНГА………......6

4.ПРОГРАММНАЯ МОДЕЛЬ МАШИНЫ ТЬЮРИНГА………............7

5.ПРОТОКОЛЫ РАБОТЫ МАШИНЫ ТЬЮРИНГА……......................20

ВЫВОД…………………………………………………………………… 21

СПИСОК ЛИТЕРАТУРЫ……………………………………………….. 22

Приложение А……………………………………………………..............23

Техническое задание……………………………………………………....23

Приложение Б……………………………………………………………...24

Экранные формы программы……………………………… …………….24

 

 

ВВЕДЕНИЕ

 

Алгоритм можно определить как точное предписание о выполнении каких–либо действий. Существует множество способов формального представления алгоритма. Например, машины Тьюринга, машины Поста, цепи Маркова.

Машина Тьюринга в качестве формального представления алгоритма была предложена английским математиком Аланом Тьюрингом в 1937 году. Машина Тьюринга это простой точный объект который может являться объектом математического исследования. Любой алгоритм (были выработаны различные определения алгоритмов и в итоге все они эквивалентны между собой) может быть реализован машиной Тьюринга.

Существует множество разновидностей машин Тьюринга: распознающие, считающие, с накапливающими состояниями и т.д. В общем говоря машина Тьюринга это совокупность шести объектов: T=(K, å, G, d, F, q₀), где K, å, G - конечные множества, множество состояния, входной алфавит (записываются слова подлежащие распознанию), ленточный алфавит. F – конечное состояние головки машины Тьюринга.

Представленная курсовая работа посвящена распознающим машинам Тьюринга, как наиболее часто используемому классу машин Тьюринга.

 

ПОСТАНОВКА ЗАДАЧИ

Необходимо формально определить машину Тьюринга, распознающую язык

L = {wÎ{0, 1}^* │w не содержит 3-х идущих подряд единиц}

Проверить правильность составления машины Тьюринга на протоколах. Реализовать программную модель машины Тьюринга.

ФОРМАЛЬНО ОПРЕДЕЛЕНИЕ МАШИНЫ ТЬЮРИНГА

 

1q1->1q2R

1q2->1q3R

1q3->1q4

1q4->BSTOP

0q1->0q1R

0q2->0q2R

0q3->0q3R

Bq4->BSTOP

K – множество состояний;

K={q₂, q₃, }.

S – входной алфавит; S={0, 1}.

Г – ленточный алфавит; Г = {0, 1}.

Q₁ – начальное состояние.

В ­– пустое множество.

STOP- состояние полной остановки машины;