Машина поста что это

Машина Поста

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

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

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

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

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

i K j,

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

У команды «стоп» отсылки нет.

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

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

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

Источник

Программирование на машине Поста

Недавно на хабре появилось сразу два материала, посвященных языкам из «большой четверки тьюринговых трясин»: про алгоритм Маркова и Brainfuck. Думаю, для полноты картины будет интересно сравнить эти эзотерические системы с еще одним важным алгоритмическим примитивом — машиной Поста, которой я как раз занимаюсь.

Машина Поста (wiki; для простоты оттуда же взят вариант синтаксиса) похожа на всем известную машину Тьюринга, однако обладает интересными особенностями. Она содержит лишь 6 команд, кроме того, в ячейки-биты памяти могут записываться лишь 2 символа (двоичное кодирование информации). «Естественно», никакой дополнительной памяти, не зря же эзотерикой зовется!

Таким образом, при программировании на машине Поста помимо необходимости совладать с оккамовским синтаксисом надо думать о том, как записать на ленте все промежуточные результаты, не потеряв по пути обратную тропинку к остаткам входных данных. Почему «остаткам»? Зачастую ввиду отсутствия дополнительной памяти приходится обрабатывать входные данные итеративно (а иногда и рекурсивно). Надеюсь, вышеизложенное убедительно доказывает, что написание привычных алгоритмов на машине Поста — неплохая разминка для мозгов и весьма увлекательное занятие.

Пример

Рассмотрим одну из кратчайших реализаций умножения двух натуральных чисел. Числа n и m записываются на ленте в единичной системе счисления, разделяются одной пустой ячейкой. Вход/выход алгоритма может быть таким (отмечено начальное положение каретки):

Идея алгоритма — краткое сложение. В каждом проходе цикла машина «откусывает» один бит от левого множителя и «копирует» самый правый имеющийся блок (сперва это второй множитель, затем — его последняя копия). Когда левый множитель «закончится», на ленте остается n блоков по m единиц. Их слияние дает искомое число n*m.

Проверить корректность алгоритма можно в уме, на листочке, либо с помощью этой программы.

Это самая короткая известная мне реализация умножения. Однако, потенциально ее можно ужать еще сильнее, если придумать, как экономно объединить процессы создания копий и их слияния в единый массив.

P. S. «Большой четверкой» называю машину Тьюрига, Поста, систему Маркова и Brainfuck — самые изучаемые тьюринговые трясины.

Источник

Изучение машины Поста в школьном курсе информатики

Онлайн-конференция

«Современная профориентация педагогов
и родителей, перспективы рынка труда
и особенности личности подростка»

Свидетельство и скидка на обучение каждому участнику

Выбранный для просмотра документ Изучение машины Поста в школьном курсе информатики.docx

Изучение машины Поста в школьном курсе информатики

Одним из центральных понятий информатики является понятие алгоритма. В 1936 году американский математик и логик Эмиль Леон Пост (1897–1954) предложил абстрактную вычислительную конструкцию, позволяющую формально определить алгоритм и названную впоследствии машиной Поста. При разработке вычислительной конструкции Пост руководствовался принципом создания максимально простой абстракции: минимумом операций при обработке информации, входная информация должна быть закодирована с использованием минимального набора символов.

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

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

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

Теоретическая часть. Состав машины Поста

Машина Поста состоит из ленты и каретки (называемой также считывающей и записывающей головкой). Лента бесконечна и разделена на секции одинакового размера — ячейки.

Рис. 1. В каждый момент времени каретка указывает на одну из ячеек

В каждой ячейке ленты может быть либо ничего не записано, либо стоять метка V. Информация о том, какие ячейки пусты, а какие содержат метки, образует состояние ленты. Иными словами, состояние ленты — это распределение меток по ячейкам. Состояние ленты меняется в процессе работы машины. Заметим, что наличие метки в ячейке можно интерпретировать как “1”, а отсутствие — “0”. Такое двоичное представление информации подобно представлению, используемому практически во всех современных ЭВМ.

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

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

1. записать 1 (метку), перейти к i-й строке программы;

2. записать 0 (стереть метку), перейти к i-й строке программы;

3. сдвиг влево, перейти к i-й строке программы;

4. сдвиг вправо, перейти к i-й строке программы;

6. если 0, то перейти к i, иначе перейти к j.

Приведем список недопустимых действий, ведущих к аварийной остановке машины:

попытка записать 1 (метку) в заполненную ячейку;

попытка стереть метку в пустой ячейке;

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

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

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

Пример программы, которая не применима ни к одному состоянию машины Поста:

Рассмотрим задачу для машины Поста и ее решение.

Задача. На ленте проставлена метка в одной-единственной ячейке. Каретка стоит на некотором расстоянии левее этой ячейки. Необходимо подвести каретку к ячейке, стереть метку и остановить каретку слева от этой ячейки.

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

Программа для машины Поста:

Начинать знакомство с машиной Поста рекомендуется с первой темы “Применимость программ. Определение результата выполнения программ”.

Пояснения к условиям задач

1) В задачах под массивом понимается последовательность подряд идущих меток, ограниченная пустыми ячейками.

2) Если в задаче говорится, что на ленте задано число в унарной системе, то имеется в виду, что натуральное число n закодировано с помощью массива длины n.

3) В задачах при описании начального состояния ленты будем указывать то, что записано начиная с самой левой непустой ячейки и заканчивая самой правой непустой ячейкой. При этом будем использовать следующие обозначения: n подряд идущих меток будем обозначать 1n, а m пустых ячеек — 0m. При обозначении одной заполненной или пустой ячейки будем писать просто 1 или 0, соответственно.

К примеру, запись “12012” будет соответствовать записи “11011” на ленте.

4) Если не сказано ничего о местонахождении каретки в начальный момент времени, то будем считать, что каретка обозревает ячейку с самой левой меткой.

1. Применимость программ. Определение результата выполнения программ

1. Выяснить, применимы ли программы к заданным состояниям машины Поста, указать результат работы машины Поста для каждого состояния.

c) 1) зацикливание (…111)

2) зацикливание (…1111001)

3) зацикливание (1010111…)

2. Определить состояние, в котором окажется машина Поста в результате выполнения программы при заданном начальном состоянии ленты.

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

Решение. Выделенная цифра показывает, на какой ячейке остановится машина.

3. Написать программы для машины Поста, которые обладают следующими свойствами:

программа применима к любому состоянию машины Поста;

программа не применима ни к какому состоянию машины Поста, и зона работы для любого начального состояния — бесконечная;

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

программа, применимая к любому состоянию машины Поста:

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

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

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

2. Арифметические задачи

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

4. На ленте задан массив меток. Увеличить длину массива на 2 метки. Каретка находится либо слева от массива, либо над одной из ячеек самого массива.

3. –> 4 (команды 3 и 4 — передвигаем каретку к концу массива)

5. V 6 (команды 5–7 — ставим 2 метки в конце массива)

5. Даны два массива меток, которые находятся на некотором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива.

Выбранный для просмотра документ изучение машины Поста.pptx

Источник

Задачи по Python с решениями

Свежие записи

Машина Поста

На этом шаге мы рассмотрим машину Поста.

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

Рис.1. Состояние машины Поста

Команда машины Поста имеет следующую структуру:

Существует всего шесть команд машины Поста, рис.2.

Рис.2. Команды машины Поста

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

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

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

Будем понимать под начальным состояние головки ее положение против пустой клетки левее самой левой метки на ленте.

Рассмотрим реализацию некоторых типичных элементов программ машины Поста.

Рис.3. Пример фрагмента программы машины Поста

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

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

Программа будет иметь следующий вид:

Рис.4. Программа машины Поста

Команда условного перехода является одним из основных средств организации циклических процессов, например, для нахождения первой метки справа (или слева) от головки, расположенной над пустой клеткой; нахождение слева (или справа) от головки пустой клетки, если она расположена над меткой и т.д.

3. Остановимся на представлении чисел на ленте машины Поста и выполнении операций над ними.

Число k представляется на ленте машины Поста идущими подряд k+1 метками (одна метка означает число «0»). Между двумя числами делается интервал как минимум из одной пустой секции на ленте. Например, запись чисел 3 и 5 на ленте машины Поста будет выглядеть так:

Рис.5. Запись чисел 3 и 5 на ленте машины Поста

Обратим внимание, что используемая в машине Поста система записи чисел является непозиционной.

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

Рис.6. Увеличение числа на единицу

Для решения задачи можно переместить головку влево (или вправо) до первой пустой клетки, а затем нанести метку.

Программа, добавляющая к числу метку справа, имеет вид:

Рис.7. Текст программы, добавляющей метку справа

Программа, добавляющая к числу метку слева, имеет вид:

Рис.8. Текст программы, добавляющей метку слева

Отличие только в направлении движения головки в первой команде. Проверьте работоспособность этих программ на каких-либо частных примерах.

Рис.9. Блок поиска числа

Рис.10. Тексты программ

В первом случае не нужно перемещать головку к крайней левой метке числа.

Машину Поста можно рассматривать как упрощенную модель ЭВМ. В самом деле, как ЭВМ, так и машина Поста имеют:

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

На следующем шаге мы рассмотрим машину Тьюринга.

Источник

Машина Поста (устройство, команды и принцип работы)

Содержимое разработки

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

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

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

Структура машины Поста:

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

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

Алгоритм работы машины Поста задается не в виде таблицы, а как программа для универсального исполнителя.

Программа состоит из конечного числа строк и использует всего 6 команд.

где N. — номер строки, J — строка на которую переходит управление далее.

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

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

После запуска возможны варианты:

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

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

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

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

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

После команд «←”, «→”, «0” и «1” можно указать номер строки, на которую нужно перейти сразу после выполнения этой команды. Например, команда ← 3 означает «переместить каретку влево и перейти на строку 3”.

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

1. Напишите программу для машины Поста, которая увеличивает (уменьшает) число в единичной системе счисления на единицу. Каретка расположена слева от числа.

2. Напишите программу для машины Поста, которая складывает два числа в единичной системе счисления. Каретка расположена над пробелом, разделяющим эти числа на ленте.

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

Задача: увеличить число 3 на единицу (изменить значение в памяти с 3 на 4).

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

Допустим, точно известно, что каретка стоит где-то слева от меток и обозревает пустую ячейку. Тогда программа увеличения числа на единицу может выглядеть так:

Источник