- Машина Поста
- Принцип работы
- Пример
- Литература
- тренажер для изучения универсального исполнителя
- Что это такое?
- Скачать
- Машина Поста
- Содержание
- Принцип работы
- Пример: вычитание натуральных чисел P — Q
- См. также
- Другие абстрактные исполнители и формальные системы вычислений
- Литература
- Смотреть что такое "Машина Поста" в других словарях:
- Машина Поста (устройство, команды и принцип работы)
- Содержимое разработки
Машина Поста
Маши́на По́ста — абстрактная вычислительная машина, предложенная Эмилем Постом в 1936 году, создана независимо от машины Тьюринга, но сообщение о машине Поста опубликовано на несколько месяцев позднее. Отличается от машины Тьюринга большей простотой, при том обе машины алгоритмически «эквивалентны» и обе разработаны для формализации понятия алгоритма и решения задач об алгоритмической разрешимости, то есть, демонстрации алгоритмического решения задач в форме последовательности команд для машины Поста.
Принцип работы
Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на ячейки бесконечной в обе стороны ленты. Каждая ячейка ленты может находиться в 2 состояниях — быть либо пустой — 0 , либо помеченной меткой 1 . За такт работы машины каретка может сдвинуться на одну позицию влево или вправо, считать, изменить символ в своей текущей позиции.
Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и её начальное состояние (то есть состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из пронумерованных не обязательно упорядоченных строк команд, если в каждой команде указана строка, на которую нужно перейти. Обычно принимается, что если в команде переход не указан, то переход происходит на следующую строку. Каждая команда имеет следующий синтаксис:
где i — номер команды, K — действие каретки, j — номер следующей команды (отсылка).
Всего для машины Поста существует шесть типов команд:
- V j — поставить метку, перейти к j -й строке программы;
- X j — стереть метку, перейти к j -й строке;
- ← j — сдвинуться влево, перейти к j -й строке;
- → j — сдвинуться вправо, перейти к j -й строке;
- ? j1; j2 — если в ячейке нет метки, то перейти к j1 -й строке программы, иначе перейти к j2 -й строке;
- ! — конец программы («стоп», останов).
В команде «стоп» переход на следующую строку не указывается.
После программы запуска возможны варианты:
- работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);
- работа может закончиться командой «стоп»;
- работа никогда не закончится.
Пример
Для сложения и вычитания натуральных (целых неотрицательных) чисел P и Q их можно представить на ленте набором из P единиц и Q , отделённых друг от друга одним нулём; пусть исходное положение каретки находится на крайней левой «1» группы единиц Q (помечено символом « ⇓ »):
⇓ …00111110111000… ╚═══╝ ╚═╝ P Q
Сложение двух чисел тривиально — достаточно поставить « 1 » между числами и стереть одно крайнее правое « 1 » у представления Q .
Программа вычитания таких чисел состоит из последовательного изменения крайних левых « 1 » у представления Q и правых « 1 » у представления P . В начале программы каретка установлена на крайнюю левую «1» у Q :
1. ← — шаг влево 2. ? 1; 3 — если в ячейке пусто, перейти к 1 -шагу, если нет — к 3 3. X — удалить метку 4. → — шаг вправо 5. ? 4; 6 — если в ячейке пусто, перейти к 4 -шагу, если нет — к 6 6. X — удалить метку 7. → — шаг вправо 8. ? 9; 1 — если в ячейке пусто, перейти к 9 шагу, если нет — к 1 9. ! — конец
В 5-й строке возможно зацикливание, если P>»> Q > P <\displaystyle Q>P> 
P>»/> .
Литература
- Успенский Владимир Андреевич.Машина Поста / Гл. ред. физ.-мат. лит.. — 2-е изд., испр.. — М. : Наука, 1988. — 96 с. — (Популярные лекции по математике). — ISBN 5-02-013735-9.
Что такое wiki2.info Вики является главным информационным ресурсом в интернете. Она открыта для любого пользователя. Вики это библиотека, которая является общественной и многоязычной.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License.
Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. wiki2.info является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).
тренажер для изучения универсального исполнителя
Что это такое?
Тренажёр «Машина Поста» — это учебная модель универсального исполнителя (абстрактной вычислительной машины), основанного на работах Э.Л. Поста по уточнению понятия алгоритма. Согласно тезису Поста, любой алгоритм может быть записан в виде программы для машины Поста. Доказано, что машина Поста по своим возможностям эквивалентна машине Тьюринга и нормальным алгорифмам Маркова.
Машина Поста состоит из каретки (считывающей и записывающей головки) и бесконечной ленты, разбитой на ячейки. Каждая ячейка ленты может быть либо пустой («0»), или содержать метку («1»).
Программа состоит из пронумерованных строк. В каждой строке записывается одна из следующих команд:
> N переместить каретку вправо на 1 ячейку и перейти к строке с номером N;
, ЗАПРЕЩАЕТСЯ:
- 1) публикация материалов в любой форме, в том числе размещение материалов на других Web-сайтах;
- 2) распространение неполных или измененных материалов;
- 3) включение материалов в сборники на любых носителях информации;
- 4) получение коммерческой выгоды от продажи или другого использования материалов.
Использование и скачивание материалов означает, что вы приняли условия этого лицензионного соглашения.
Скачать
Пароль к архиву — kpolyakov.spb.ru
В архив включены следующие файлы:
| post.exe | основная программа — учебная модель «Машины Поста» |
| EXAMPLES | подкаталог с примерами программ для тренажера «Машина Поста« |
После распаковки архива программа находится в работоспособном состоянии и не требует никаких дополнительных установок.
Машина Поста
Машина Поста (МП) — абстрактная вычислительная машина, предложенная Эмилем Леоном Постом (Emil L. Post), которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».
Содержание
Принцип работы
Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты (см. пример ниже). Каждая секция ленты может быть либо пустой — 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит. Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис:
где i - номер команды, K – действие каретки, j - номер следующей команды (отсылка).
Всего для машины Поста существует шесть типов команд:
У команды «стоп» отсылки нет. После запуска возможны варианты:
- работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);
- работа может закончиться командой Stop;
- работа никогда не закончится.
Пример: вычитание натуральных чисел P — Q
Будем представлять натуральное (целое неотрицательное) число P набором из P+1 единиц и разделять числа нулём. Исходное положение каретки помечено символом «v»
Сложение двух чисел тривиально — достаточно поставить 1 между ними и стереть крайний правый символ у Q. Программа вычитания состоит из последовательного затирания крайних левых меток у Q и правых у P:
Отметим, что номер команды перехода не указывается, если переход происходит на следующую по порядку строку (для наглядности текста). В 6-ой строке возможно зацикливание, если Q > P (вы можете добавить проверку сами)
См. также
Другие абстрактные исполнители и формальные системы вычислений
- Нормальный алгоритм Маркова (продукционное программирование)
- Машина Тьюринга (автоматное программирование)
- Рекурсивная функция (теория вычислимости)
- Лямбда-исчисление (функциональное программирование)
- Brainfuck (императивное программирование)
Литература
 | Это заготовка статьи о компьютерах. Вы можете помочь проекту, исправив и дополнив её. Это примечание по возможности следует заменить более точным. |
Wikimedia Foundation . 2010 .
Смотреть что такое "Машина Поста" в других словарях:
Машина Поста — математическое построение, предназначенное для уточнения понятия алгоритма. Машина Поста состоит: из неограниченной в обе стороны ленты, разделенной на ячейки; из головка чтения/записи, которая может перемещаться вдоль ленты и управляется… … Финансовый словарь
Машина поста — (МП) абстрактная вычислительная машина, предложенная Эмилем Леоном Постом (Emil L. Post), которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм». Содержание 1 Принцип… … Википедия
Машина Тьюринга для умножения чисел — Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча… … Википедия
Машина тьюринга — (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча Тьюринга, способна … Википедия
Машина Тьюринга — Художественное представление машины Тьюринга Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма … Википедия
поста́в — а, мн. постава, м. 1. только ед. ч. Манера держать в каком л. положении какую л. часть тела; постановка (чаще о голове). Был он строен, кряжист, с упругими мускулами и упрямым поставом головы. Гладков, Цемент. В них [оленях] все легко и прелестно … Малый академический словарь
ПОСТА МАШИНА — один из вариантов Тьюринга машины … Математическая энциклопедия
Детерминированная машина Тьюринга — Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча… … Википедия
Тьюринга машина — Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча… … Википедия
Недетерминированная машина Тьюринга — Машина Тьюринга Варианты машин Универсальная машина Тьюринга Квантовая машина Тьюринга en:Read only Turing machine en:Read only right moving Turing Machines Вероятностная машина Тьюринга Недетер … Википедия
Машина Поста (устройство, команды и принцип работы)
Содержимое разработки
Практически одновременно с Тьюрингом (тоже в 1936 году) и независимо от него, американский математик Эмиль Пост предлагает еще более простого исполнителя, названного позже машиной Поста. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».
Эмиль Леон Пост - американский математик и логик. Один из основателей многозначной логики (1921); трудился в области математической логики: создал алгебру Поста, классы Поста функций алгебры логики; предложил абстрактную вычислительную машину — машину Поста.
Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы.
В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.
Структура машины Поста:
Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на ячейки бесконечной в обе стороны ленты (также как у машины Тьюринга). Каждая ячейка ленты может быть либо пустой — 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит.
Т.о., Пост сократил алфавит всего до двух цифр. Это допустимо, потому что любые данные можно перекодировать в двоичный код, сопоставив каждой букве исходного алфавита уникальную последовательность нулей и единиц.
Алгоритм работы машины Поста задается не в виде таблицы, а как программа для универсального исполнителя.
Программа состоит из конечного числа строк и использует всего 6 команд.
N. → J - сдвиг вправо
N. ← J - сдвиг влево
N. 1 J - запись метки
N. 0 J -удаление метки
N. ? J1, J0 - если в ячейке есть метка, то перейти к j1 строке программы, иначе перейти к j0 строке программы.
N. Stop - остановка
где N. — номер строки, J — строка на которую переходит управление далее.
Попытка стереть метку там, где ее нет, или поставить метку повторно считается ошибкой, и машина аварийно останавливается.
Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки).
После запуска возможны варианты:
- работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);
- работа может закончиться командой Stop;
- работа никогда не закончится.
Все строки в программе нумеруются по порядку, это необходимо для работы команды ветвления (? n0,n1). С помощью этой команды можно также строить циклы, как с предусловием, так и с постусловием.
Пост предположил, что любой алгоритм может быть записан как программа для машины Поста.
В теории алгоритмов доказано, что машины Поста и Тьюринга одинаковы по своим возможностям. Это значит, что круг задач, который они решают, тоже одинаков.
Например, следующая программа перемещает каретку влево до первой отмеченной ячейки:
1. ←
2. ? 1,3
3. стоп
После команд "←”, "→”, "0” и "1” можно указать номер строки, на которую нужно перейти сразу после выполнения этой команды. Например, команда ← 3 означает "переместить каретку влево и перейти на строку 3”.
При работе с машиной Поста числа обычно записывают в унарной (единичной) системе счисления, в виде непрерывной цепочки меток нужной длины (вспомните счетные палочки в младшей школе).
1. Напишите программу для машины Поста, которая увеличивает (уменьшает) число в единичной системе счисления на единицу. Каретка расположена слева от числа.
2. Напишите программу для машины Поста, которая складывает два числа в единичной системе счисления. Каретка расположена над пробелом, разделяющим эти числа на ленте.
3. Что делают следующие программы для машины Поста:
а) 1 1 б) 1 ← в) 1 ? 2,3
2 → 2 ? 3,4 2 1 4
3 → 1 3 1 1 3 → 1
4 стоп 4 стоп
Пример работы машины Поста:
Задача: увеличить число 3 на единицу (изменить значение в памяти с 3 на 4).
Целое положительное число на ленте машины Поста представимо идущими подряд метками, которых на одну больше, чем кодируемое число. Это связано с тем, что одна метка обозначает ноль, а уже две – единицу, и т.д.
Допустим, точно известно, что каретка стоит где-то слева от меток и обозревает пустую ячейку. Тогда программа увеличения числа на единицу может выглядеть так:
1 → 2
2 ? 1;3
3 ← 4
4 V 5
5 Stop
А процесс выполнения может быть таким (см.рисунок):
