Эмиль пост и машина поста доклад

Обновлено: 30.06.2024

Содержание

Принцип работы

Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты (см. пример ниже). Каждая секция ленты может быть либо пустой — 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит. Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис:

где i - номер команды, K – действие каретки, j - номер следующей команды (отсылка).

Всего для машины Поста существует шесть типов команд:

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

Пример: вычитание натуральных чисел P — Q

Сложение двух чисел тривиально — достаточно поставить 1 между ними и стереть крайний правый символ у Q. Программа вычитания состоит из последовательного затирания крайних левых меток у Q и правых у P:

Отметим, что номер команды перехода не указывается, если переход происходит на следующую по порядку строку (для наглядности текста). В 6-ой строке возможно зацикливание, если Q > P (вы можете добавить проверку сами)

См. также

Другие абстрактные исполнители и формальные системы вычислений

Литература

Это заготовка статьи о компьютерах. Вы можете помочь проекту, исправив и дополнив её.
Это примечание по возможности следует заменить более точным.

  • Теория алгоритмов
  • Модели вычислений

Wikimedia Foundation . 2010 .

Полезное

Смотреть что такое "Машина Поста" в других словарях:

Машина Поста — математическое построение, предназначенное для уточнения понятия алгоритма. Машина Поста состоит: из неограниченной в обе стороны ленты, разделенной на ячейки; из головка чтения/записи, которая может перемещаться вдоль ленты и управляется… … Финансовый словарь

Машина Тьюринга для умножения чисел — Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча… … Википедия

Машина тьюринга — (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча Тьюринга, способна … Википедия

Машина Тьюринга — Художественное представление машины Тьюринга Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма … Википедия

поста́в — а, мн. постава, м. 1. только ед. ч. Манера держать в каком л. положении какую л. часть тела; постановка (чаще о голове). Был он строен, кряжист, с упругими мускулами и упрямым поставом головы. Гладков, Цемент. В них [оленях] все легко и прелестно … Малый академический словарь

ПОСТА МАШИНА — один из вариантов Тьюринга машины … Математическая энциклопедия

Детерминированная машина Тьюринга — Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча… … Википедия

Тьюринга машина — Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча… … Википедия

Недетерминированная машина Тьюринга — Машина Тьюринга Варианты машин Универсальная машина Тьюринга Квантовая машина Тьюринга en:Read only Turing machine en:Read only right moving Turing Machines Вероятностная машина Тьюринга Недетер … Википедия

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

В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.

Машина Поста состоит из …

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

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

Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис:

i K j,

где i - номер команды, K – действие каретки, j - номер следующей команды (отсылка).

Всего для машины Поста существует шесть типов команд:

  • V j - поставить метку, перейти к j-й строке программы.
  • X j - стереть метку, перейти к j-й строке программы.
  • j - сдвинуться вправо, перейти к j-й строке программы.
  • ? j1; j2 - если в ячейке нет метки, то перейти к j1-й строке программы, иначе перейти к j2-й строке программы.
  • ! – конец программы (стоп).

Варианты окончания выполнения программы на машине Поста:

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

Пример работы машины Поста:

Задача: увеличить число 3 на единицу (изменить значение в памяти с 3 на 4).
Целое положительное число на ленте машины Поста представимо идущими подряд метками, которых на одну больше, чем кодируемое число. Это связано с тем, что одна метка обозначает ноль, а уже две – единицу, и т.д.
Допустим, точно известно, что каретка стоит где-то слева от меток и обозревает пустую ячейку. Тогда программа увеличения числа на единицу может выглядеть так:
1 -> 2
2 ? 1;3
3

В его машине тоже имеется бесконечная лента и головка. Лента разделена на ячейки. В каждой ячейке записан один символ из фиксированного алфавита. В любой момент времени машина обрабатывает ровно одну ячейку.

Машина Поста работает под управлением программы. Программа состоит из команд. Команды отличаются от команд машины Тьюринга. Если у Тьюринга все команды одного типа и похожи на функции переходов-выходов автомата, то у Поста команды больше напоминают машинные команды современных ЭВМ. Команды машины Поста состоят из трёх частей (полей) [7]:

1. Номер команды.

3. Отсылка (номер следующей команды).

Команды нумеруются с 1. Первой выполняется команда 1.

1. → – движение на одну клетку вправо (R).

2. ← – движение на одну клетке влево (L).

3. S – запись в обозреваемую ячейку, при этом предыдущее значение ячейки теряется (S – произвольный символ алфавита).

Si – символ в ячейке, М – номер следующей команды.

При ветвлении символы Si должны быть различны, но не обязательно использовать весь алфавит. Если Si есть в ячейке, то выполняется команда Mi, при этом головка не перемещается и в клетку ничего не записывается. Если ни один символ не совпадает – происходит так называемая безрезультатная остановка.

Пример 1. Алфавит А: , где λ – пустой символ, как и в машинах Тьюринга.

Это программа заполнения ленты символами 1, т.е. пустой ленты, в которой во всех ячейках – λ.

Пример 2. Прибавление символа 1 к числу 11. 1, А=.

Если же после прибавления двигаться влево к началу числа, как это обычно требуется, то:

Если работа алгоритма никогда не закончится над некоторыми исходными данными, то алгоритм неприменим к ним (хотя в примере 1 это и не так).

Алгоритм А над исходными данными X обозначим А(Х) – это результат работы алгоритма. Результат не определен, если А неприменим к Х.

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

Постовые алгоритмы – это алгоритмы, работающие со словами. В принципе, все математические объекты можно закодировать в виде слов.

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

Рубрика Программирование, компьютеры и кибернетика
Вид реферат
Язык русский
Дата добавления 20.10.2013
Размер файла 24,6 K

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

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

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

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

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

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

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

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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подобные документы

Общая схема D-триггера и цифрового автомата Мили. Построение входных и выходных преобразователей в соответствии с таблицами кодирования входных и выходных сигналов. Составление таблиц переходов и выхода состояния автомата Мили. Выбор серии микросхем.

курсовая работа [525,4 K], добавлен 04.11.2012

Содержание и особенности этапов синтеза дискретного автомата. Граф переходов-выходов автомата Мура, кодирование входных и выходных сигналов. Построение функциональной схемы автомата Мура на RS–триггерах и элементах И-НЕ в программе Electronic WorkBench.

курсовая работа [964,2 K], добавлен 20.07.2015

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

реферат [62,2 K], добавлен 16.03.2011

Синтез автомата для преобразования двоично-десятичного кода. Кодировка алфавитов и состояний. Построение булевых функций, минимизация. Разметка вход-выходных слов для автомата Мили и автомата Мура. Реализация на элементах малой степени интеграции.

контрольная работа [141,5 K], добавлен 14.10.2012

Создание Бэббиджем "разностной" машины, которая должна была не просто выполнять арифметические действия, а проводить вычисления по программе, задающей определённую функцию. Этапы развития ЭВМ. Создание компьютеров на основе процессоров семейства Intel.

реферат [38,3 K], добавлен 17.09.2013

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

курсовая работа [60,9 K], добавлен 15.02.2011

Первый автор идеи создания вычислительной машины, которая в наши дни называется компьютером. Главные изобретения Бэббиджа. Малая разностная машина и разностная машина Чарльза Бэббиджа. Архитектура аналитической машины. Изобретение тахометра и спидометра.

Читайте также: