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

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

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

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

 

 

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

 

 

 

 

 

 

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

 

 

 

 

 

Выполнили:  
студенты гр.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 –  Программа для машины Тьюринга

	1	_	*

 

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

11*111 11*111 11*111 111111 111111 111111 111111 111111_ 11111_

 
Рисунок 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. организация информационной поддержки системы.