Начальная

Windows Commander

Far
WinNavigator
Frigate
Norton Commander
WinNC
Dos Navigator
Servant Salamander
Turbo Browser

Winamp, Skins, Plugins
Необходимые Утилиты
Текстовые редакторы
Юмор

File managers and best utilites

Лекция: Описание программы-эмулятора машины Поста. Эмулятор машины поста


Учебная модель компьютера «Машина Поста»: сайт Константина Полякова

Тренажер «Машина Поста»

Машина Поста

Что это такое?

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

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

Программа состоит из пронумерованных строк. В каждой строке записывается одна из следующих команд:    > N    переместить каретку вправо на 1 ячейку и перейти к строке с номером N;    < N    переместить каретку влево на 1 ячейку и перейти к строке с номером N    0 N    записать в текущую ячейку «0» (стереть метку) и перейти к строке с номером N    1 N    записать в текущую ячейку «1» (поставить метку) и перейти к строке с номером N    ? N, M   если текущая ячейка содержит «0» (не отмечена), то перейти к строке с номером N, иначе перейти к строке M    .   остановить программу

Номер строки перехода в командах >, <, 0 и 1 можно не указывать, при этом происходит переход к следующей строке.

Для завершения работы программы достаточно сделать переход на строку 0, например, так:    ? 25, 0    остановить программу, если текущая ячейка содержит «1», иначе перейти к строке 25.

Троичная машина Поста

В троичной машине Поста используется расширенный алфавит, состоящий из трех символов: пробел, «0» и «1». Это позволяет программировать задачи, в которых числа записаны в двоичной системе счисления. Команды, отличающиеся от классического (двоичного) варианта машины Поста:    X N    записать в текущую ячейку пробел (стереть метку) и перейти к строке с номером N    0 N    записать в текущую ячейку «0» и перейти к строке с номером N    1 N    записать в текущую ячейку «1»" и перейти к строке с номером N

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

Команда ветвления содержит три метки, разделенные запятыми:    ? N,M,L    если текущая ячейка пустая, то перейти к строке с номером N, иначе если текущая ячейка содержит «0», то перейти к строке с номером M, иначе (если текущая ячейка содержит «1») перейти к строке L

Где почитать ещё?

  1. Успенский В.А. Машина Поста, М: Наука, 1988.
  2. Майер Р.В. Машины Поста и Тьюринга (komp-model.narod.ru).
  3. Бекман И.Н. Компьютерные науки. Лекция 7. Алгоритмы (profbeckman.narod.ru)
  4. Фалина И.Н., Радченко Е.Л. Изучение машины Поста в школьном курсе информатики (inf.1september.ru)
  5. Соловьев А. Дискретная математика без формул (lib.rus.ec)
  6. Ершов С.С. Элементы теории алгоритмов, Челябинск, Издательский центр ЮУрГУ, 2009.
  7. Программирование на машине Поста (habrahabr.ru)

Что с этим делать?

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

Лента перемещается влево и вправо с помощью кнопок, расположенных слева и справа от нее. Двойным щелчком по ячейке ленты можно изменить ее содержимое (в «классическом» варианте заменяется «0» на «1» или наоборот, в троичной машине Поста символы «пробел», «0» и «1» при последовательных двойных щелчках меняются циклически).

С помощью меню Лента можно запомнить состояние ленты во внутреннем буфере и восстановить ленту из буфера.

С помощью меню Алфавит можно переключать режим работы машины (двоичный или троичный алфавит). В классическом режиме меню Вид позволяет настроить вид ленты (точки, отметки-галочки, двоичный код).

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

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

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

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

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

Технические требования

Программа работает под управлением операционных систем линейки Windows на любых современных компьютерах.

Лицензия

Программа является бесплатной для некоммерческого использования. Исходные тексты программы не распространяются.

Программа поставляется «as is», то есть, автор не несет никакой ответственности за всевозможные последствия ее использования, включая моральные и материальные потери, вывод оборудования из строя, физические и душевные травмы.

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

Без письменного согласия автора ЗАПРЕЩАЕТСЯ:
  1. 1) публикация материалов в любой форме, в том числе размещение материалов на других Web-сайтах;
  2. 2) распространение неполных или измененных материалов;
  3. 3) включение материалов в сборники на любых носителях информации;
  4. 4) получение коммерческой выгоды от продажи или другого использования материалов.

Скачивание материалов означает, что вы приняли условия этого лицензионного соглашения.

Скачать

Пароль к архиву — kpolyakov.spb.ru

В архив включены следующие файлы:

post.exe   основная программа — учебная модель «Машины Поста»
EXAMPLES   подкаталог с примерами программ для тренажера «Машина Поста«

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

kpolyakov.spb.ru

Описание программы-эмулятора машины Поста

Тренажёр «Машина Поста» – это учебная модель универсального исполнителя (абстрактной вычислительной машины), основанного на работах Э.Л. Постапо уточнению понятия алгоритма.

  1. Модель машины Поста

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

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

 > N переместить каретку вправо на 1 ячейку и перейти к строке с номером N;

 < N переместить каретку влево на 1 ячейку и перейти к строке с номером N;

 0 N записать в текущую ячейку «0» (стереть метку) и перейти к строке с номером N;

 1 N записать в текущую ячейку «1» (поставить метку) и перейти к строке с номером N;

 ? N, Mесли текущая ячейка содержит «0» (не отмечена), то перейти к строке с номером N, иначе перейти к строке M;

 .остановить программу

Номер строки перехода в командах >, <, 0 и 1 можно не указывать, при этом происходит переход к следующей строке.

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

 ? 25, 0 остановить программу, если текущая ячейка содержит «1», иначе перейти к строке 25.

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

Лента перемещается влево и вправо с помощью кнопок, расположенных слева и справа от нее. Двойным щелчком по ячейке ленты можно изменить ее содержимое (в «классическом» варианте заменяется «0» на «1» или, наоборот, в троичной машине Поста символы «пробел», «0» и «1» при последовательных двойных щелчках меняются циклически).

С помощью меню Лентаможно запомнить состояние ленты во внутреннем буфере и восстановить ленту из буфера.

С помощью меню Алфавитможно переключать режим работы машины (двоичный или троичный алфавит). В классическом режиме менюВидпозволяет настроить вид ленты (точки, отметки-галочки, двоичный код).

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

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

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

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

studfiles.net

1.5 Машина поста

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

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

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

Состав машины Поста.

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

Рис. 9. Состав машины Поста

В каждой ячейке ленты может стоять метка V либо ничего не записано.. Состояние ленты — это распределение меток по ячейкам. Состояние ленты меняется в процессе работы машины.

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

Команды машины Поста:

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

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

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

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

5. останов;

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

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

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

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

  • бесконечное выполнение (зацикливание).

Команды машины обозначают следующим образом (рис.10):

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

Рассмотрим несколько арифметических задач для машины Поста и их решение.[12]

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

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

Решение:

1. ? 2; 3 (команды 1 и 2 — передвигаем каретку к массиву)

2. → 1

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

4. ? 5; 3

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

6. → 7

7. V 8

8. !

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

Решение.

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

Решение.

4. На ленте заданы два массива — m и n, m > n. Вычислить разность этих массивов. Каретка располагается над левой ячейкой правого массива.

Решение:

1. → 2 (команды 1–3: ищем левую метку массива m)

2. ? 3; 1

3. ← 4

4. X 5 (стираем левую метку массива m)

5. ? 6; 7

6. → 5

7. X 8 (стираем левую метку массива n)

8. → 9

9. ? 12; 10 (стерли последнюю метку в массиве n?)

10. ←11 (ищем левый край массива m)

11. ? 10; 4

12. !

5. На ленте задан массив. Удвоить массив в два раза. Каретка располагается над первой ячейкой массива.

Решение.

В результате работы программы справа от исходного массива будет сформирован новый массив удвоенной длины, исходный массив будет стерт.

studfiles.net

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

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

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

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

Пример
Рассмотрим одну из кратчайших реализаций умножения двух натуральных чисел. Числа n и m записываются на ленте в единичной системе счисления, разделяются одной пустой ячейкой. Вход/выход алгоритма может быть таким (отмечено начальное положение каретки): v ..01110110.. → ..01111110.. 3 * 2 = 6

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

Код
0. ! - команда остановки, выполнение начинается со строки №1 1. 0 - главный цикл 2. → 3. ? 29, 4 - 29:левый множитель закончился 4. → 5. ? 6, 4 6. → 7. ? 8, 4 8. ← 9. ← 10. 0 - копирование правого блока 11. → 12. ? 13, 11 13. → 14. ? 15, 13 15. 1 16. ← 17. ? 18, 16 18. ← 19. ? 20, 18 20. 1 21. ← 22. ? 23, 10 - конец блока копирования 23. ← 24. ? 25, 23 25. ← 26. ? 27, 23 27. → 28. → 1 29. → - слияние копий второго множителя 30. 0 31. → 32. ? 33, 31 33. 1 34. → 35. ? 0, 36 - выход из программы 36. ← 37. ? 29, 36

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

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

Если вас заинтересовала тема, предлагаю подумать над следующими задачами:

  • Вывод i-го числа Фибоначчи
  • Деление двух натуральных чисел c остатком
  • «Сборщик мусора». На ленте неизвестным образом распределено конечное количество (n) отмеченных ячеек. Необходимо «сгрести» их в одну кучу, т. е. машина должна оставить на ленте только блок в n отметок подряд.

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

habr.com

Эмулятор машины Поста - Машина Поста - УТОЧНЕНИЕ ПОНЯТИЯ АЛГОРИТМА - Каталог файлов

 Классическая машина Поста

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

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

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

> N    переместить каретку вправо на 1 ячейку и перейти к строке с номером N

< N    переместить каретку влево на 1 ячейку и перейти к строке с номером N

0 N    записать в текущую ячейку «0» (стереть метку) и перейти к строке с номером N

1 N    записать в текущую ячейку «1» (поставить метку) и перейти к строке с номером N

? N, M      если текущая ячейка содержит «0» (не отмечена), то перейти к строке с номером N, иначе перейти к строке M

.         остановить программу

Номер строки перехода в командах >, <, 0 и 1 можно не указывать, при этом происходит переход к следующей строке.

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

? 25, 0    остановить программу, если текущая ячейка содержит «1»  иначе перейти к строке 25

 

Троичная машина Поста

В троичной машине Поста используется расширенный алфавит, состоящий из трех символов: пробел, «0» и «1». Это позволяет программировать задачи, в которых числа записаны в двоичной системе счисления. Команды, отличающиеся от «стандартного» варианта машины Поста:

X N    записать в текущую ячейку пробел (стереть метку) и перейти к строке с номером N

0 N    записать в текущую ячейку «0» и перейти к строке с номером N

1 N    записать в текущую ячейку «1» и перейти к строке с номером N

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

Команда ветвления содержит три метки, разделенные запятыми:

? N,M,L    если текущая ячейка пустая, то перейти к строке с номером N, иначе если текущая ячейка содержит «0», то перейти к строке с номером M, иначе (если текущая ячейка содержит «1») перейти к строке L

 

Как работать с программой?

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

Лента перемещается влево и вправо с помощью кнопок, расположенных слева и справа от нее. Двойным щелчком по ячейке ленты можно изменить ее содержимое (в «классическом» варианте заменяется «0» на «1» или наоборот, в троичной машине Поста символы «пробел», «0» и «1» при последовательных двойных щелчках меняются циклически).

С помощью меню Лента можно запомнить состояние ленты во внутреннем буфере и восстановить ленту из буфера.

С помощью меню Алфавит можно переключать режим работы машины (двоичный или троичный алфавит). В классическом режиме меню Вид позволяет настроить вид ленты (точки, отметки-галочки, двоичный код).

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

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

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

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

bit126.moy.su

Лекция - Описание программы-эмулятора машины Поста

Тренажёр «Машина Поста» – это учебная модель универсального исполнителя (абстрактной вычислительной машины), основанного на работах Э.Л. Поста по уточнению понятия алгоритма.

 

Рис. 12. Модель машины Поста

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

Программа состоит из пронумерованных строк. В каждой строке записывается одна из следующих команд (для расширенной модификации – троичной машины Поста используется дополнительный набор команд[2]):

> N переместить каретку вправо на 1 ячейку и перейти к строке с номером N;

< N переместить каретку влево на 1 ячейку и перейти к строке с номером N;

0 N записать в текущую ячейку «0» (стереть метку) и перейти к строке с номером N;

1 N записать в текущую ячейку «1» (поставить метку) и перейти к строке с номером N;

? N, Mесли текущая ячейка содержит «0» (не отмечена), то перейти к строке с номером N, иначе перейти к строке M;

.остановить программу

Номер строки перехода в командах >, <, 0 и 1 можно не указывать, при этом происходит переход к следующей строке.

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

? 25, 0 остановить программу, если текущая ячейка содержит «1», иначе перейти к строке 25.

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

Лента перемещается влево и вправо с помощью кнопок, расположенных слева и справа от нее. Двойным щелчком по ячейке ленты можно изменить ее содержимое (в «классическом» варианте заменяется «0» на «1» или, наоборот, в троичной машине Поста символы «пробел», «0» и «1» при последовательных двойных щелчках меняются циклически).

С помощью меню Лента можно запомнить состояние ленты во внутреннем буфере и восстановить ленту из буфера.

С помощью меню Алфавит можно переключать режим работы машины (двоичный или троичный алфавит). В классическом режиме меню Вид позволяет настроить вид ленты (точки, отметки-галочки, двоичный код).

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

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

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

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

Содержание работы

Запустить программу-эмулятор машины Поста. Ознакомиться с работой эмулятора и набором команд. Воспроизвести (не сохраняя в файл) предложенные выше примеры. По указанию преподавателя выбрать варианты из папки \..Example программы-эмулятора, а, также вариант из Приложения Е. По завершении работы результаты сохранить в файл.

www.ronl.ru

Машина Поста

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

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

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

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

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

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

i K j,

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

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

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

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

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

  1. Команда "стоп" - корректная остановка. Возникает в результате выполнения правильно написанного алгоритма.
  2. Выполнение недопустимой команды – нерезультативная остановка. Случаи, когда головка должна записать метку там, где она уже есть, или стереть метку там, где ее нет, являются аварийными (недопустимыми).
  3. Уход в бесконечность, зацикливание. Машина Поста в результате работы алгоритма может вообще не остановиться (никогда не дойти до команды «стоп» и никогда не завершиться аварийной ситуацией).

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

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

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

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

 

inf1.info


 

..:::Новинки:::..

Windows Commander 5.11 Свежая версия.

Новая версия
IrfanView 3.75 (рус)

Обновление текстового редактора TextEd, уже 1.75a

System mechanic 3.7f
Новая версия

Обновление плагинов для WC, смотрим :-)

Весь Winamp
Посетите новый сайт.

WinRaR 3.00
Релиз уже здесь

PowerDesk 4.0 free
Просто - напросто сильный upgrade проводника.

..:::Счетчики:::..