Изменения
'''Машина Поста''' (МП) — это абстрактная вычислительная машина для выполнения программ, предложенная американским математиком Эмилем Леоном Постом в 1936 году.
== Состав МП ==
МП состоит из каретки (или считывающей и записывающей головки) и ленты, разбитой на секции (ячейки) и бесконечной в обе стороны.
В каждой ячейке ленты может быть либо 0, либо 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать или записать символ (1 или 0, т.е. стереть 1) в том месте, где она стоит.
Работа МП определяется программой, состоящей из конечного числа командных строк.
== Виды команд: ==
* сдвиг вправо
* условный переход
* стоп
Введём обозначения:
'''S''' — стоп.
== Виды командных строк: ==
'''nR''' — сдвиг на 1 ячейку вправо и переход к следующей строке;
* работа может закончиться командой '''S''';
* работа никогда не закончится (т.е.программа составлена не корректно).
== Пример задачи ==
[[файл:МП11.JPG]], где '''x''', '''y''' - неотрицательные целые числа.
=== Программа для МП ===
[[файл:МП12.JPG]]
=== Таблица для программы ===
[[файл:МП13.JPG]]
Введём обозначения:
'''1<sup>x+1</sup>01<sup>y+1</sup>''' — набор значений аргументов '''(x,y)'''.
Входные данные: '''1<sub>1</sub>011'''.
Выходные данные:
'''0<sub>14</sub>011'''.
Входные данные: '''1<sub>1</sub>1101'''.
Выходные данные: '''1110<sub>14</sub>00'''.
Входные данные: '''1<sub>1</sub>10111'''.
Выходные данные:
'''11110<sub>14</sub>00'''.
* Заметим, что [[машина Тьюринга]] во многом аналогична машине Поста.
== Ссылки ==
* Википедия
* [[Участник:Logic-samara]]
[[Категория:Дискретная математика]][[Категория:Алгоритмы]]