Машина Поста

Размещено на http://www.allbest.ru/

ДАГЕСТАНСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ НАРОДНОГО ХОЗЯЙСТВА

Факультет: ПвКС

Реферат

По дисциплине: ”Теория Алгоритмов”

На тему: “Машина Поста”

Абдурашидов Арсен

Махачкала 2013 г.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ОПИСАНИЕ РАБОТЫ МАШИНЫ ПОСТА

ОПИСАНИЕ АЛГОРИТМА

ОПИСАНИЕ ПРОГРАММЫ

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ВВЕДЕНИЕ

Абстрактная вычислительная машина - теоретическое построение, с помощью которого вводится строгое, математическое определение алгоритма. Абстрактные машины являются частным случаем управляющих систем. Возникновение их связано с анализом понятия алгоритма, начавшегося в середине 30-х гг. 20 в., с развитием ЭВМ и с построением математических моделей биологических систем. Наибольшее распространение получили машины, перерабатывающие дискретную информацию, типичными представителями которых являются конечный автомат и машина Поста. Абстрактные машины обладают большой наглядностью, возможностью легко осуществлять различные композиции, элементарностью шагов работы. Изучение машин проводится в рамках теории алгоритмов, математической кибернетики и преследует цели анализа и формализации понятия алгоритма, математического моделирования реальных устройств и процессов. Существует плодотворная связь между абстрактными машинами и реально существующими ЭВМ.

Автомат - разновидность абстрактной вычислительной машины, которая определяется:

* множеством входных и выходных сигналов;

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

* функцией, задающей переходы из одних состояний в другие;

* функцией, определяющей выходные сигналы в зависимости от входного сигнала и текущего состояния.

Автомат предназначен для формальной переработки последовательностей символов.

Конечный автомат - математическая модель устройства с конечной памятью. Конечный автомат перерабатывает множество входных дискретных сигналов во множество выходных сигналов. Различают синхронные и асинхронные конечные автоматы. Эмиль Пост предложил абстрактную вычислительную машину - машину Поста. Она проста и «эквивалентна» и была создана для уточнения понятия «алгоритм». Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции ленты, считающейся условно бесконечной в обе стороны. В каждой клетке может быть записан символ из фиксированного алфавита. В любой конкретный момент головка обозревает одну клетку и способна работать только с ней. Работа машины Поста определяется программой с конечным числом строк. Программа состоит из команд, имеющих по 3 поля, в которых записываются: № команды, операция и отсылка.

Для машины Поста определены операции 6 видов:

1. Движение головки на 1 клетку вправо.

2. Движение головки на 1 клетку влево.

3. Запись метки.

4. Удаление метки.

5. Условный переход по метке.

6. STOP - остановка (завершение работы машины Поста);

Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки). После запуска возможны варианты:

* работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);

* работа может закончиться командой Stop;

* работа никогда не закончится.

ОПИСАНИЕ РАБОТЫ МАШИНЫ ПОСТА

абстрактный вычислительный машина автомат

Абстрактная (т.е. существующая не реально, а лишь в воображении) машина Поста, предназначена для доказательств различных утверждений о свойствах программ. Данная машина представляет собой универсальный исполнитель, являющийся полностью детерминированным, позволяющим «вводить» начальные данные, и после выполнения программ «читать» результат. Машина Поста менее популярна, чем машина Тьюринга, хотя она значительно проще неё. С её помощью можно вести обучение первым навыкам составления программ для ЭВМ. Машина Поста представляет собой бесконечную ленту, разделенную на одинаковые клетки, каждая из которых может быть либо пустой, либо заполненной меткой «V», и головки, которая может перемещаться вдоль ленты на одну клетку вправо или влево, наносить в клетку ленты метку, если этой метки там ранее не было, стирать метку, если она была, или проверять наличие в клетке метки. Информация о заполненных метками клетках ленты характеризует состояние ленты, которое может меняться в процессе работы машины. В каждый момент времени головка («-») находится над одной из клеток ленты. Информация о местоположения головки вместе с состоянием ленты характеризует состояние машины Поста.

Ситуации, в которых головка должна наносить метку там, где она уже имеется, или, наоборот, стирать метку там, где ее нет, являются аварийными (недопустимыми) и вызывают останов.

Программой для машины Поста называется непустой список команд, такой что:

1) на п-м месте команда с номером n;

2) номер т каждой команды совпадает с номером какой-либо команды списка.

Останов машины Поста может быть вызван несколькими причинами:

1) останов по команде «стоп»; такой останов называется результативным и указывает на корректность алгоритма (программы);

2) останов при выполнении недопустимой команды; в этом случае останов называется безрезультативным;

3) машина не останавливается никогда; в таком случае мы имеем дело с некорректным алгоритмом (программой).

Число k представляется на ленте машины Поста идущими подряд k + 1 метками, одна метка означает число «0». Между двумя числами делается интервал как минимум из одной пустой секции на ленте.

ОПИСАНИЕ АЛГОРИТМА

Разработанная в результате выполнения курсового проекта программа должна будет представлять собой модель машины Поста на ЭВМ. Программа будет разрабатываться на языке Турбо Паскаль и будет реализовывать шесть команд машины Поста. Начальное состояние ленты, место головки и последовательность выполнения команд будут считываться программой из текстового файла. Первая строка текстового файла содержит последовательность нулей и единиц и задает тем самым состояние ленты, вторая строка содержит число, указывающее номер позиции головки на ленте, а начиная с третьей строки, через пробел, указываются номера команд (на каждой строке одна команда).

Для команды, реализующей условный переход, необходимо записать в текстовый файл еще два значения (номер строки следующей команды, если условие выполнится, и номер строки в противном случае). Следовательно, в текстовом файле, на строке, содержащей номер команды условного оператора, будет располагаться три цифры: первая содержит информацию о номере команды, вторая указывает номер строки, на которую необходимо перейти если условие истинно и третья указывает номер строки перехода если условие ложно. Так как текстовый файл считывается сверху вниз и строка не может считаться дважды, в программе будет реализован двумерный массив размера Nx3, в который переписывается текст программы машины Поста из файла.

Дальнейшую обработку записанной программы Паскаль реализует, считывая её из массива. Лента в программе будет описана строковым типом, а номер позиции головки храниться в переменной целочисленного типа. Выполнение недопустимой команды (запись в ячейку с меткой и стирание пустой ячейки) приведет к аварийному выходу из программы. Для наглядности хода выполнения программы реализованы задержки.

Для проверки работоспособности программы выполняется алгоритм сложения двух целых неотрицательных чисел A и B на машине Поста, когда головка находится над числом A, а число B находится правее числа A на некоторое число клеток. Программа реализует следующий алгоритм: первое число постепенно придвигается ко второму до их слияния, а потом стирается одна метка (иначе результат оказался бы на единицу больше верного).

ОПИСАНИЕ ПРОГРАММЫ

Информация о последовательности выполнения команд машины Поста хранится в двумерном массиве Mass типа array[1..N, 1..M] of Integer размера M*N, где константы N=100 и M=3. В первом столбце массива хранится информация о номере выполняемой команды, второй и третий столбцы содержат информацию о том, на какую ячейку массива необходимо перейти при выполнении условия условного оператора и невыполнении, следовательно, они заполняются только при наличии в первом столбце числа 5 (команда машины Поста «переход по условию»). Значение ленты Поста хранится в переменной Lenta типа String. Переменная Pos служит для хранения номера позиции головки на ленте, I - хранит номер строки массива при записи из файла, L - используется в качестве индекса при работе с лентой, X и Y - служат в качестве координат при выводе на экран строки и курсора, имитирующего головку. Файловая переменная F типа Text, используется при чтении информации из файла. Переменная Flag типа Boolean используется в команде останова программы. В программе написаны две процедуры Result и ReadFile. Процедура Result, описывает алгоритм работы команды условного перехода машины Поста.

Входные переменным I1, L1, Lenta1 передается значение из основной программы, а после завершения работы процедура возвращает глобальным переменным измененное значение. Локальным переменным A, B присваивается из массива значение номеров строк, на которые необходимо перейти при выполнении условия A и B, если это не так, то присваивается значение B. Перед завершением работы, процедура Result уменьшает значение I1.

Это связано с тем, что в главной программе организован цикл считывания номера команды из массива и увеличение значения I на 1, а процедура выдает значение ячейки, из которой необходимо считать номер. Следовательно, процедура уменьшает номер, а программа увеличивает, тем самым происходит компенсация их работы.

Работа процедуры заключается в следующем: если текущее значение ленты равно 1 то в переменную I записывается номер строки массива A, в противном случае номер строки массива B. Процедура ReadFile предназначена для чтения файла и записи его строк в массив и переменные. В данной подпрограмме используются только глобальные переменные. После того как подпрограмма связала файловую переменную F с файлом «Prog.txt» (файл должен находится там же, где и файл программы, в противном случае придется указывать путь к текстовому файлу) и открыла его для чтения Reset(F), она записывает первую строку файла в переменную Lenta, вторую в переменную Pos, а затем организует цикл считывания до конца файла (while not EOF(F) do).

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

Первой запускается процедура ReadFile, которая считывает информацию из файла, затем переменная Flag присваивается значение «ложь», так как значение «истина» является признаком останова программы. Основной частью главной программы является цикл repeat until, который выполняется до тех пор, пока не выполнится условие истинности Flag. Цикл for I:=1 to 256 do выводит значения ленты, соответственно с изменениями, которые вносятся. Когда длина переменной Lenta исчерпана, остальная часть ленты заполняется нулями. Затем идет оператор выбора, который считывает очередное значение массива и в соответствии с ним выполняет одну из 6 команд машины Поста:

1: сдвиг головки вправо, то есть в переменной лента смещается указатель вправо Pos := Pos + 1 ('Сдвиг вправо');

2: сдвиг головки влево, аналогично предыдущей команде, только смещение влево Pos := Pos - 1 и вывод сообщения ('Сдвиг влево');

3: Запись единицы, переменной, описывающей ленту, в ячейку присваивается единица Lenta[Pos]:='1' и выводится сообщение ('Запись 1'). Здесь так же осуществляется проверка условия, чтобы ячейка изначально не содержала 1, иначе выводится сообщение о некорректности алгоритма и выполнение работы программы завершается;

4: Запись нуля: переменной, описывающей ленту, в ячейку присваивается нуль Lenta[Pos]:='0' и выводится сообщение ('Запись 0'). Здесь так же осуществляется проверка на то, что бы ячейка изначально не содержала 0, иначе выводится сообщение о некорректности алгоритма с последующим завершением работы программы;

5: переход по условию, вызывается выше описанная процедура Result(J, Pos, Lenta), которая и осуществляет переход, после чего выводится сообщение ('Переход');

6: остановка выполнения программы, признаком остановки программы является Flag:=True, после чего цикл заканчивает свою работу и выводит сообщение ('Стоп').

В конце программы стоит Readln, ожидающий нажатия клавиши который позволяет пользователю просмотреть результаты работы программы.

ЗАКЛЮЧЕНИЕ

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

В качестве недостатков программы можно отметить ограниченность размеров входной программы, а также режим работы программы, который является «режимом реального времени» и забирает значительные ресурсы ЭВМ. Устранить вышеописанные недостатки можно переписав программу на языке программирования более высокого уровня, например Delphi.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Могилев А.В., Пак Н.И., Хеннер Е.К. Информатика / А.В. Могилев, Н.И. Пак, Е.К. Хеннер - М.: Академия, 2004. - 848 с.

2. Фаронов В.В. Турбо Паскаль 7.0 / В.В. Фаронов - М.: «ОМД Групп», 2003. - 616 с.

3. Математическая энциклопедия. -- М.: Советская энциклопедия И. М. Виноградов 1977--1985

4. Кафедра информационных технологий Курганского Национального Университета 7.0.5-2008.Информатика и программирование. Классические формализации понятия «алгоритм». Машина Поста - М.,2009.-003с. - (Информатика и программирование):

? URL: http://it.kgsu.ru/TI_5/falg_003.html

? URL: http://inf.1september.ru/articlef.php?ID=200700104

5. А.А. Медведев, Н.А. Морева. Язык программирования Паскаль: Учеб. пособие для средних учебных заведений. 2-е издание, исправленное и дополненное.- Курган: Изд-во Курганского ин-та повышения квалификации работников образования,2002-128с.

6. Н.А. Жучкова, А.А. Медведев. Изучение основ программирования в среде Delphi: Учеб.пособие для средних учебных заведений.- Курган: Изд-во Курганского ин-та повышения квалификации работников образования,2007.-124с.

7. Дмитрий Котерев. Самоучитель. БХВ-Петербург,2001г.,7152с.

8. А. Мешков, Ю. Тихомиров «Visual C++ и MFC» - СПб.: БХВ-Петербург. 2002 -- 1017с.

9. Культин Н. «С/С++ в задачах и примерах» - СПб.: БХВ-Петербург, 2002. -- 288 с.

10. Turbo Pascal: практикум. - СПб.: Питер, 2002. - 256 с.: ил.

Размещено на Allbest.ru