Машина Поста — различия между версиями
м |
|||
(не показано 8 промежуточных версий 2 участников) | |||
Строка 1: | Строка 1: | ||
'''Машина Поста''' (МП) — это абстрактная вычислительная машина для выполнения программ, предложенная американским математиком Эмилем Леоном Постом в 1936 году. | '''Машина Поста''' (МП) — это абстрактная вычислительная машина для выполнения программ, предложенная американским математиком Эмилем Леоном Постом в 1936 году. | ||
+ | = Машина Поста = | ||
== Состав МП == | == Состав МП == | ||
МП состоит из каретки (или считывающей и записывающей головки) и ленты, разбитой на секции (ячейки) и бесконечной в обе стороны. | МП состоит из каретки (или считывающей и записывающей головки) и ленты, разбитой на секции (ячейки) и бесконечной в обе стороны. | ||
Строка 5: | Строка 6: | ||
Работа МП определяется программой, состоящей из конечного числа командных строк. | Работа МП определяется программой, состоящей из конечного числа командных строк. | ||
== Виды команд: == | == Виды команд: == | ||
− | * сдвиг вправо | + | *сдвиг вправо |
− | * сдвиг влево | + | *сдвиг влево |
− | * запись 1 | + | *запись 1 |
− | * запись 0 | + | *запись 0 |
− | * переход (безусловный) | + | *переход (безусловный) |
− | * условный переход | + | *условный переход |
− | * стоп | + | *стоп |
Введём обозначения: | Введём обозначения: | ||
Строка 59: | Строка 60: | ||
После запуска программы на МП возможны следующие варианты: | После запуска программы на МП возможны следующие варианты: | ||
− | * работа может закончиться командой '''S'''; | + | *работа может закончиться командой '''S'''; |
− | * работа никогда не закончится (т.е.программа составлена не корректно). | + | *работа никогда не закончится (т.е.программа составлена не корректно). |
== Пример задачи == | == Пример задачи == | ||
[[файл:МП11.JPG]], где '''x''', '''y''' - неотрицательные целые числа. | [[файл:МП11.JPG]], где '''x''', '''y''' - неотрицательные целые числа. | ||
Строка 101: | Строка 102: | ||
Выходные данные: | Выходные данные: | ||
'''11110<sub>14</sub>00'''. | '''11110<sub>14</sub>00'''. | ||
− | * Заметим, что [[машина Тьюринга]] во многом аналогична машине Поста. | + | *Заметим, что [[машина Тьюринга]] во многом аналогична машине Поста. |
− | == Другие алгоритмы: == | + | == [[Алгоритм|Другие алгоритмы:]] == |
− | + | {{Список Алг}} | |
− | + | = [[Разделы математики|Другие разделы]] = | |
− | + | = Ссылки = | |
− | + | *Википедия. Машина Поста. | |
− | + | *[[Участник:Logic-samara]] | |
− | + | [[Категория:Математика]][[Категория:Дискретная математика]][[Категория:Алгоритмы]] | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | * Википедия | + | |
− | * [[Участник:Logic-samara]] | + | |
− | [[Категория:Дискретная математика]][[Категория:Алгоритмы]] | + |
Текущая версия на 13:02, 14 января 2024
Машина Поста (МП) — это абстрактная вычислительная машина для выполнения программ, предложенная американским математиком Эмилем Леоном Постом в 1936 году.
Содержание
Машина Поста
Состав МП
МП состоит из каретки (или считывающей и записывающей головки) и ленты, разбитой на секции (ячейки) и бесконечной в обе стороны. В каждой ячейке ленты может быть либо 0, либо 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать или записать символ (1 или 0, т.е. стереть 1) в том месте, где она стоит. Работа МП определяется программой, состоящей из конечного числа командных строк.
Виды команд:
- сдвиг вправо
- сдвиг влево
- запись 1
- запись 0
- переход (безусловный)
- условный переход
- стоп
Введём обозначения:
n — номер командной строки в программе;
n1 — номер командной строки, которой передаётся управление;
n2 — номер альтернативной командной строки, которой передаётся управление;
R — сдвиг вправо;
L — сдвиг влево;
1 — запись 1;
0 — запись 0;
? — проверка условия;
S — стоп.
Виды командных строк:
nR — сдвиг на 1 ячейку вправо и переход к следующей строке;
nRn1 — сдвиг на 1 ячейку вправо и переход к строке n1;
nL — сдвиг на 1 ячейку влево и переход к следующей строке;
nLn1 — сдвиг на 1 ячейку влево и переход к строке n1;
n1 — запись 1 и переход к следующей строке;
n1n1 — запись 1 и переход к строке n1;
n0 — запись 0 (стирание 1, если она была) и переход к следующей строке;
n0n1 — запись 0 и переход к строке n1;
n?n1,n2 — если в ячейке 1, то переход к строке n1, иначе — переход к строке n2;
n?n1 — если в ячейке 1, то переход к строке n1, иначе — переход к следующей строке;
n?,n2 — если в ячейке 1, то переход к следующей строке, иначе — переход к строке n2;
nS — остановка работы.
Для работы машины Поста нужно задать программу и её начальное состояние (т. е. состояние ленты и позицию каретки). Предполагается, что неопределённая часть ленты заполнена символами 0, т.е. она чистая.
После запуска программы на МП возможны следующие варианты:
- работа может закончиться командой S;
- работа никогда не закончится (т.е.программа составлена не корректно).
Пример задачи
, где x, y - неотрицательные целые числа.
Программа для МП
Таблица для программы
Примеры работы МП:
Введём обозначения:
1 — число 0;
11 — число 1;
111 — число 2;
1x+1 — неотрицательное целое число x;
1y+1 — неотрицательное целое число y;
1x+101y+1 — набор значений аргументов (x,y).
Пример 1
Входные данные: 11011.
Выходные данные: 014011.
Пример 2
Входные данные: 111101.
Выходные данные: 11101400.
Пример 3
Входные данные: 1110111.
Выходные данные: 111101400.
- Заметим, что машина Тьюринга во многом аналогична машине Поста.
Другие алгоритмы:
- алгоритм метода математической индукции;
- алгоритмы в арифметике;
- алгоритмы перевода чисел;
- комбинаторные алгоритмы;
- алгоритм сортировки;
- алгоритм определения мест;
- логистические алгоритмы;
- алгоритмы решения транспортных задач;
- алгоритмы численных методов;
- алгоритмы построенные с помощью машины Поста;
- алгоритмы построенные с помощью машины Тьюринга;
- алгоритм синтеза автомата Мили;
- алгоритм синтеза автомата Мура.
Другие разделы
Ссылки
- Википедия. Машина Поста.
- Участник:Logic-samara