Машина Поста
Машина Поста (МП) – абстрактная вычислительная машина, предложенная Эмилем Леоном Постом, которая отличается от машины Тьюринга большей простотой.
Обе машины эквиваленты
Эмиль Леон Пост (11.02.1897 (Польша) -21.04.1954) – американский математик и логик
Машина Поста состоит из каретки (считывающей и записывающей головки) и ленты, разбитой на ячейки (лента условно бесконечна)
Каждая ячейка ленты может быть пустой (0) или содержать метку (1)
За один такт машина Поста может:
- сдвинуть каретку на одну позицию влево или вправо
- поставить или стереть метку в ячейке, обозреваемую машиной
- проверить наличие метки в обозреваемой ячейке и перейти к команде с заданным номером
Работа машины Поста определяется программой, состоящей из конечного числа строк
Всего шесть команд:
N. , J - сдвиг вправо
N. , J - сдвиг влево
N. 1, J - запись метки
N. 0, J - удаление метки
N. ?, J1, J0 - если в ячейке метка, то перейти к команде J1, если ячейка пуста –
к ячейке J0
N. Stop - остановка
При этом: N – порядковый номер команды
J – номер следующей команды
Для работы машины Поста нужно задать программу и ее начальное состояние (состояние ленты и позицию каретки)
В ходе работы машины Поста может произойти следующее:
1) Будет выполнена команда Stop и получен результат работы алгоритма
2) Встречается невыполнимая команда (стирание несуществующей метки или запись в ячейку с меткой)
3) Машина будет работать бесконечно
Замечание
Определяя машину Поста и машину Тьюринга авторы пытались задать исполнителя и алгоритмический процесс как можно проще – так, чтобы можно было показать несуществование алгоритма для решения какой-нибудь задачи
Исходя из этого определялись элементы и принципы работы машин Поста и Тьюринга
Пример
Составить машину Поста для вычисления функции S(x, y) = x + y
Решение
Пример
Составить машину Поста для вычисления функции S(x, y) = x + y
Применить программу:
1 = 01110110; 2 = 01100; 3 = 00110;
Пример
Составить машину Поста для вычисления частичной функции f(x, y) = x – y
Литература
ВикипедиЯ. Свободная энциклопедия. http://ru.wikipedia.org
Великие силы – только для великих целей