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