Система моделирования работы машины Тьюринга

Министерство  образования и науки РФ

Государственное образовательное учреждение  
высшего профессионального образования 
«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ  
АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ  
имени академика С.П. КОРОЛЕВА»

(национальный исследовательский университет)

Кафедра программных систем

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА 
к курсовому проекту по дисциплине 
"Программная инженерия" на тему 
" Система моделирования работы машины Тьюринга"

Выполнили:  
студенты гр.6312

Запольская М.М.

Ивлиева Л.В.

Лукьянова Е.С. 

Руководитель проекта: 
доцент каф. ПС Зеленко Л.С. 
 
Дата сдачи: 
Оценка:

Самара, 2011 г.

СОДЕРЖАНИЕ

РЕФЕРАТ

Пояснительная записка 42 с., 22 рисунков, 3 таблицы, 17 источников, 2 приложения.

МАШИНА ТЬЮРИНГА, АЛГОРИТМ, ЛЕНТА, ТРАССА, АЛФАВИТ, ОПЕРАНД.

В курсовом проекте разработана и написана программа «Машина Тьюринга», дающая возможность изучать на примерах принципы работы машины Тьюринга, создавать, отлаживать, исполнять, полноценные программы машины Тьюринга, проверять их формальную корректность.

Программа написана на языке C# в среде Visual Studio 2008 и функционирует в операционной системе Windows XP и выше.

ВВЕДЕНИЕ

В 1936 г. английский математик Алан Тьюринг опубликовал в трудах Лондонского математического общества статью «О вычислимых числах в приложении к проблеме разрешения», которая наравне с работами Поста и Черча лежит в основе современной теории алгоритмов. Тьюрингом в качестве математической модели для описания алгоритмов было предложено абстрактное вычислительное устройство, которое впоследствии было названо машина Тьюринга (МТ).

Первоначально концепция МТ развивалась  с целью ответа на вопрос: можно  ли для любого математического утверждения  указать конечную последовательность инструкций, которые могли бы выполняться  механически одна за другой человеком или вычислительным устройством, и в итоге выяснить, истинно это утверждение или ложно. При этом машина Тьюринга дискретное вычислительное устройство, изменяющее свои характеристики в определенные моменты времени. Хотя и доказано, что поставленная проблема в общем случае неразрешима, применение машины Тьюринга вышло далеко за пределы первоначальной постановки задачи. По существу, именно работы Тьюринга положили начало математической теории вычислений. Хотя МТ не стала реально действующим устройством, она до настоящего времени постоянно используется в качестве основной модели для выяснения сущности таких понятий, как «вычислительный процесс», «алгоритм», а также для выяснения связи между алгоритмом и вычислительными машинами [1].

Аналогом МТ является машина Поста. Она устроена проще, чем машина Тьюринга, в том отношении, что ее элементарные действия проще, чем элементарные действия машины Тьюринга, и способы записи менее разнообразны, однако по этим причинам запись и переработка информации на машине Поста требует, вообще говоря, большего объема «памяти» и большего числа шагов, чем на машине Тьюринга [2].

Так как процесс составления  алгоритма на бумаге не очень удобен, то предпочтительно автоматизировать этот процесс. Поэтому перед авторами поставлена задача – разработать компьютерный аналог МТ. Разработка системы будет вестись по технологии быстрой разработки приложения RAD (Rapid Application Development) и объектно-ориентированного программирования (ООП).

RAD – это жизненный цикл процесса проектирования, созданный для достижения более высоких скорости разработки и качества программного обеспечения (ПО), чем это возможно при традиционном подходе к проектированию. RAD предполагает, что разработка ПО осуществляется небольшой командой разработчиков за срок порядка трех-четырех месяцев [3].

Основными преимуществами данной технологии являются:

• высокая скорость разработки;
• низкая стоимость;
• высокое качество.

1 СИСТЕМОТЕХНИЧЕСКАЯ ЧАСТЬ

1.1 Описание и анализ предметной области

1.1.1 Описание предметной области

Машина Тьюринга — абстрактная вычислительная машина.

МТ является расширением конечного  автомата и, согласно тезису Черча-Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен [4].

МТ состоит из устройства управления, которое с помощью головки связано с лентой ввода/вывода. Лента – это длинная полоска, разделенная на ячейки, каждая из которых может содержать одну литеру; лента простирается вправо до бесконечности. Головка указывает на какую-то одну ячейку ленты и может читать содержимое ячейки, записывать и перемещаться вправо или влево (см. рисунок 1). В начале работы исходные данные всегда заполняют левую часть ленты, а головка читает самую левую ячейку ленты. Когда головка, двигаясь вправо, достигает ячейки, которая не является частью исходных данных и никогда ранее не обозревалась головкой, считается, что в этой ячейке записан пробел, обозначаемый b.

Устройство управления выполняет  программу, подчиняясь строгим правилам. В любой момент времени устройство управления находится в некотором  состоянии, которое записано в регистре текущее состояние. Состояния обозначаются положительными целыми числами. Каждая команда представляет собой пятерку, составленную из состояния, литеры, еще одного состояния, еще одной литеры и направления движения ленты. Цикл выполнения команды начинается с того, что устройство управления сравнивает текущее состояние и литеру на ленте под головкой с первыми двумя компонентами всех команд. По правилам программирования для МТ в программе может быть не более одной пятерки с какой-либо определенной начальной парой состояние-литера (но может и не быть ни одной). Когда совпадение найдено, устройство управления выполняет три действия: в ячейку ленты под головкой записывается литера, являющаяся четвертой компонентой пятерки; головка передвигается на одну ячейку влево или вправо или остается на месте, как указано в пятой компоненте пятерки; текущее состояние заменяется на третью компоненту. После этого машина готова к следующему циклу. По соглашению, работа начинается в состоянии 1 при описанном выше состоянии ленты. Машина останавливается, если в цикле выполнения не удается найти совпадения с текущей парой состояние-литера или если головка выходит за левый край ленты; при этом результатом работы считается все, что остается на ленте после остановки. Отметим, что программа может содержать лишь конечное число команд, так что для любой программы осмысленно только конечное число состояний и литер.

Формально МТ может быть описана как пятерка объектов (A, S, n, z, d) [5],

где:

A = {a₀, a₁, . . ., a_n} – конечный алфавит символов;

S = {s₀, s₁, . . ., s_r} – конечное множество внутренних состояний;

n - функция перехода S × A → S;

z - функция выхода S × A → A;

d  - функция управления S × A → {П, Л, Н}.

Для пояснения изложения приведем пример программы для машины Тьюринга, которая будет строить сумму двух целых чисел. Целое число n будет изображаться на ленте n последовательными 1, два исходных числа будут разделены *, и если исходные данные представляют n+m, то результатом должны быть n+m единиц. Так, чтобы вычислить 3+2, следует записать в качестве исходных данных  111*11 результатом должно быть 11111.

Структура программы: сначала головка движется вправо в поисках *. Звездочка заменяется единицей, и головка продолжает движение, отыскивая пробел, ограничивающий справа исходные данные. Головка возвращается на одну ячейку назад и записывает пробел на место находящейся там звездочки, после чего программа завершается. Программа приведена в таблице 1.

         Таблица 1 –  Программа для машины Тьюринга

На рисунке 2 показана последовательность моментальных снимков (трасса) для всего вычисления. Подчеркиванием обозначим рассматриваемый символ.

 
Рисунок 2 – Трасса выполнения программы

1.1.2 Описание систем-аналогов

В настоящее время существует много  программ, которые позволяют изучить  свойства МТ и проверить вычислимость алгоритмов различной сложности.

Рассмотрим две программы, являющиеся аналогами МТ.

Программа Машина Тьюринга 1.1 [6]

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

Отличительные черты данной программы:

• возможность быстрого и эффективного редактирования алгоритма, его сохранения в файл или загрузки в любой момент времени;
• быстрое добавление повторяющихся данных на ленту;
• возможность проверки условной корректности написанных программ;
• исполнение и отладка в трех режимах, ведение статистики переходов и применяемых правил;
• удобный в использовании оконный интерфейс приложения;
• наличие расширенной справочной системы.

На рисунке 3 представлен интерфейс Машины Тьюринга 1.1.

Программа “Algo2000” [7]

“Algo2000” – интерпретатор машины Поста и машины Тьюринга. Проверка правильности составления алгоритма вычисления функции с помощью компьютера полностью исключает возможность ошибки при работе по программе на ленте. При этом пользователь имеет возможность регулировать скорость выполнения программы и видеть каждый шаг машины при обработке числа, что позволяет своевременно вносить изменения в программу при обнаружении ошибки. Программа имеет удобный интерфейс, предусмотрена возможность сохранения составленных программ, поддерживаются различные внешние алфавиты машины Тьюринга, а также имеется справочник пользователя.

 Программа имеет умеренные требования: компьютер IBM PC AT 486 и выше, наличие операционной системы Windows'95/98/NT.

Главное окно программы представлено на рисунке 4.

1.1.3 Диаграмма объектов предметной области

При использовании технологии ООП решение представляется в  виде результата взаимодействия отдельных функциональных элементов некоторой системы, имитирующей процессы, происходящие в предметной области поставленной задачи. В такой системе каждый функциональный элемент, получив некоторое входное воздействие в процессе решения задачи, выполняет заранее определенные действия. Процессом решения задачи управляет последовательность сообщений. Передавая эти сообщения от элемента к элементу, система выполняет необходимые действия [8].

Функциональные элементы системы, обладающие самостоятельным поведением (т.е. выполняющие некоторые действия, зависящие от полученных сообщений и состояния элемента), получили название объектов.

Процесс представления  предметной области задачи в виде совокупности 
объектов, обменивающихся сообщениями, называется объектной декомпозицией.

Диаграмма объектов предметной области машины Тьюринга изображена на  
рисунке 5.

Основным объектом данной  предметной области является объект «Алгоритм», представленный в виде таблицы, состоящей из «Ячеек», которые в свою очередь состоят из «Символа», «Команды управления», «Состояния» (см. таблица 1). «Алгоритм» управляет «Лентой»,  начальное состояние которой задается пользователем. В ходе выполнения «Алгоритма» формируется «Трасса», которую пользователь может сохранять в файл. Множество «Символов» составляет  «Алфавит», который может редактировать пользователь. Пользователь может составлять и редактировать «Алгоритм» и сохранять (загружать) в файл (из файла).

1.2 Постановка задачи

В рамках курсового проекта перед авторами поставлена задача – разработать программную систему (ПС) «Машина Тьюринга», которая должна реализовывать процесс составления и выполнения алгоритма в соответствии с правилами, описанными в  
пункте 1.1.1.

Для решения поставленной задачи необходимо:

1. Предоставить пользователю возможность составления произвольного вычислительного алгоритма (все алгоритмы должны быть двухоперандовые). Алгоритм будет представлен в виде таблицы  
   (см. таблица 1), где количество строк должно быть фиксировано, а количество столбцов определяется алфавитом, на котором работает МТ. Структура алфавита также должна быть фиксирована (первый символ – единица числа, второй – разделитель между числами, третий – пробел), но пользователь должен иметь возможность его редактировать. При составлении алгоритма пользователь может добавлять, удалять строки таблицы, редактировать ячейки. Команды управления считывающим устройством должны иметь фиксированную структуру: R – вправо на одну позицию, S – на месте, L – влево на одну позицию. При необходимости пользователь должен иметь возможность сохранять алгоритм в файл или загружать его из файла с целью исследования его возможностей. Кроме того, в системе должна быть реализована возможность выбора базового алгоритма (сложение, вычитание) для демонстрации работы МТ.
2. Обеспечить возможность задать значения операндов в выбранном формате (числовой или символьный на ленте) для проверки работы МТ.
3. Обеспечить возможность запуска МТ на исполнение. Для наглядности изучения работы МТ в системе должна быть реализована возможность выполнения алгоритмов в различных режимах: пошаговый, автоматический (с задержкой), вывод конечного результата, а так же осуществляться визуализация в виде подсветки на ленте и в таблице. В системе должен быть реализован семантический анализ алгоритма с выдачей сообщений. В ходе работы МТ должна формироваться трасса (см. рисунок 2), которую пользователь может сохранить в файл.

Таким образом, система должна реализовывать  следующие функции:

1. задание значений операндов в выбранном формате;
2. выбор базового алгоритма;
3. ручное составление алгоритма:
4. сохранение алгоритма в файл;
5. загрузка алгоритма из файла;
6. работа с алфавитом:
7. семантический анализ алгоритма с выдачей сообщений;
8. демонстрация работы машины Тьюринга в заданном режиме;
9. визуализация процессов работы машины Тьюринга;
10. возможность формирования трассы; 
11. сохранение трассы в файл;
12. организация информационной поддержки системы.

1.3 Построение структурной схемы

В основе структурного подхода  к разработке ПС лежит алгоритмическая декомпозиция, когда система разбивается на функциональные подсистемы, которые, в свою очередь, делятся на подфункции, подразделяемые на задачи и так далее. Процесс разбиения продолжается вплоть до конкретных процедур (алгоритмов). При этом автоматизируемая система сохраняет целостное представление, в котором все составляющие компоненты взаимоувязаны. Разработка  системы идет по принципу «сверху-вниз» [9].

Структурная схема «Машины Тьюринга» представлена на рисунке  6.

Рисунок  6 – Структурная схема программной системы

Автоматизированную систему «Машины Тьюринга» можно представить в виде следующих подсистем:

- управления, которая представляет собой иерархическое меню и позволяет организовать связь с другими подсистемами;

- создания алгоритма, включающую в себя подсистемы ручного составления алгоритма или загрузки базового;

- семантического анализа, которая отвечает за проведение семантического анализа и выдачу сообщений в случае нахождения ошибок;

- визуализации, отвечающей за отображение процесса выполнения алгоритма;

- файловой, позволяющей сохранять (загружать) алгоритм, сохранять трассу;

- справочной, выдающей информацию о разработчиках и сведения о системе.

1.4 Спецификация системы

Требования (спецификации) – свойства, которыми должно обладать ПО для адекватного определения функций, условий и ограничений выполнения ПО, а также объемов данных технического обеспечения и среды функционирования [10].

Различают требования к  продукту и к процессу, а также  функциональные и нефункциональные и системные требования.

Функциональные требования определяют назначения и функции ПО.

Нефункциональные требования определяют условия выполнения ПО и доступа к данным.

Системные требования включают в свой состав требования по аппаратному и программному обеспечению, с помощью которого будет разрабатываться и функционировать ПО.

1.4.1 Функциональная спецификация

Функциональная спецификация –  перечень всех функций, которые выполняет  пользователь, и наиболее важных функций  системы с привязкой к информационной  
среде [10].

Перечень функций, выполняемых  системой, представлен в таблице  2.

1.4.2 Спецификация качества

Основные требования по показателям качества к программной  системе [9]:

1. Корректность. В первую очередь программа должна правильно работать.
2. Надёжность – способность ПС выполнять возложенные на нее функции при поступлении требований на их выполнение в течение заданного интервала времени, включающая в себя отказоустойчивость, безопасность, защищённость от случайных или преднамеренных воздействий.
3. Эффективность – отношение уровня услуг, предоставленных программной системой пользователю при заданных условиях к объёму использованных ресурсов, оценивающееся временем выполнения кода, загруженностью процессора, объёмом требуемой памяти, временем отклика.
4. Удобство использования. ПС должна быть легкой в использовании, причем именно тем типом пользователей, на которых она рассчитана. Это включает в себя интерфейс пользователя и адекватную документацию. Причем, пользовательский интерфейс должен быть не интуитивно, а профессионально понятным пользователю.
5. Полезность. Данная программа позволяет моделировать работу машины Тьюринга– универсального вычислительного устройства, на котором, в теории, могут быть реализованы любые алгоритмы.

1.4.3 Перечень исключительных ситуаций

Составной частью функциональной спецификации является описание исключительных ситуаций.

 Исключительная ситуация –  это ситуация, при которой система  не может выполнить те функции,  которые ожидает пользователь, или  ситуация, которая приводит к  денормализации работы всей системы [10].

Перечень исключительных ситуаций представлен в таблице 3.

Таблица 3 – Перечень функций, выполняемых системой

1.5 UML-проект

UML ( Unified Modeling Language — унифицированный язык моделирования) — язык графического описания для объектного моделирования в области разработки программного обеспечения. UML является языком широкого профиля, это открытый стандарт, использующий графические обозначения для создания абстрактной модели системы, называемой UML-моделью. UML был создан для определения, визуализации, проектирования и документирования в основном программных систем. UML не является языком программирования, но в средствах выполнения UML-моделей как интерпретируемого кода возможна кодогенерация. [11].

Использование UML не ограничивается моделированием программного обеспечения. Его также используют для моделирования бизнес-процессов, системного проектирования и отображения организационных структур.

UML позволяет также  разработчикам программного обеспечения  достигнуть соглашения в графических обозначениях для представления общих понятий (таких как класс, компонент, обобщение (generalization), объединение (aggregation) и поведение), и больше сконцентрироваться на проектировании и архитектуре.

UML содержит стандартный набор  диаграмм и нотаций для моделирования самых разнообразных видов систем: систем программного обеспечения, технических средств и организационно-экономических систем [12]:

• диаграммы вариантов использования (use case diagrams);
• диаграммы классов (class diagrams);
• диаграммы поведения системы (behavior diagrams):
• диаграммы состояний (statechart diagrams);
• диаграммы деятельностей (activity diagrams;
• диаграммы взаимодействия (interaction diagrams):
• диаграммы последовательности (sequence diagrams);
• кооперативные диаграммы (collaboration diagrams);
• диаграммы реализации (implementation diagrams):
• диаграммы компонентов (component diagrams);
• диаграммы размещения (deployment diagrams).

1.5.1 Диаграмма вариантов использования

Диаграмма вариантов использования  описывает функциональное назначение системы, т.е. то, что система будет делать в процессе своего функционирования. Диаграмма вариантов использования является исходным концептуальным представлением или концептуальной моделью системы в процессе ее проектирования и разработки [12].

Суть данной диаграммы состоит  в следующем: проектируемая система  представляется в виде множества  сущностей или актантов, взаимодействующих  с системой с помощью так называемых вариантов использования. При этом актантом или действующим лицом  называется любая сущность, взаимодействующая с системой извне. Это может быть человек, техническое устройство, программа или любая другая система, которая может служить источником воздействия на моделируемую систему так, как определит сам разработчик. В свою очередь вариант использования служит для описания сервисов, которые система предоставляет актанту.

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

Каждый вариант использования  должен быть задокументирован как некий  сценарий работы с системой. Сценарий - определенная последовательность действий, которая описывает действия актеров и поведение моделируемой системы в форме обычного текста. Ниже приведены примеры оформления сценариев.

Вариант использования: Задать дополнительный символ алфавита.

Краткое описание.  Дает возможность пользователю добавить символ в алфавит, если это необходимо для реализации алгоритма. Пользователь щелчком мыши по кнопке «+», расположенной рядом с таблицей алгоритма, открывает окно для ввода нового символа.

Актант. Пользователь.

Предусловия. Компьютер пользователя включён, на экране – главное окно программы «Машина Тьюринга».

Основной поток событий.

1. На экране появляется форма ввода имени символа с полем ввода «Введите символ» и с кнопкой «Оk».
2. Пользователь вводит символ и нажимает кнопку «Оk».

А1: Введен символ, уже имеющийся в алфавите.

А2: Введено более одного символа.

А3: Символ не введен и нажата кнопка «Ok»

Альтернативы.

А1: Введен символ, уже имеющийся  в алфавите.

Система выводит сообщение «Данный  символ уже присутствует!» и отображает главное окно приложения.

А2: Введено более одного символа.

Система выводит сообщение «Введите ОДИН символ!» и ожидает повторного ввода символа.

А3: Символ не введен и нажата кнопка «Ok»

Рисунок  7 – Диаграмма вариантов  использования

А3.1 Система закрывает форму для ввода символа и выводит на экран главную форму приложения.

Постусловия. При успешном завершении на экране – главное окно приложения с обновленным алфавитом и новым столбцом в таблице алгоритма.

Вариант использования: Загрузить алгоритм из файла.

Краткое описание.  Дает возможность пользователю загрузить сохраненный ранее алгоритм. Пользователь открывает окно загрузки нажатием кнопки «Загрузить алгоритм» на главной форме приложения или выбрав команду «Загрузить алгоритм» в меню «Файл».

Актант. Пользователь.

Предусловия. Компьютер пользователя включён, на экране – главное окно программы «Машина Тьюринга».

Основной поток событий.

1. На экране появляется окно загрузки.
2. Пользователь выбирает нужный файл или вводит имя файла вручную и нажимает кнопку «Открыть».

А1: Нажата кнопка «Отмена»

3. Система заполняет таблицу в соответствии с загруженным (выбранным) алгоритмом

А2: Загрузка алгоритма неверной структуры.

А3: Имя файла не существует.

Альтернативы.

А1: Нажата кнопка «Отмена»

А1.1: Система закрывает окно загрузки и выводит на экран главную форму приложения.

А2: Загрузка алгоритма неверной структуры.

А2.1: Система выводит сообщение  «Неверная структура файла». На экране отображается главное окно приложения.

А3: Имя файла не существует.

А3.1: Система выводит сообщение  «Файл не найден…». На экране отображается окно загрузки.

Постусловия. При успешном завершении на экране – главное окно приложения с таблицей, заполненной в соответствии с выбранным алгоритмом.

Вариант использования: Задать операнд в десятичной форме.

Краткое описание.  Дает возможность пользователю заполнить ленту, задав операнды в десятичной форме. Пользователь выбирает данный способ задания операндов. Система активизирует текстовые поля, в которых пользователь задает значения операндов.

Актант. Пользователь.

Предусловия. Компьютер пользователя включён, на экране – главное окно программы «Машина Тьюринга».

Основной поток событий.

1. Пользователь ставит галочку в поле «Задать в десятичной форме»
2. Система активизирует два текстовых поля для ввода значений операндов.
3. Пользователь вводит значения и нажимает кнопку « >> ».
4. Система заполняет ленту операндами в символьной форме

А1: Не заданы значения операндов.

А2: Введено не числовое значение.

А3: Введены значения, превышающие  размерность ленты.

Альтернативы.

А1: Не заданы значения операндов.

А1.1: Система выводит сообщение  «Введите число!».

А2: Введено не числовое значение.