Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Практическое занятие №6
Тема: Машина Поста (МП)
Основные понятия и определения, рассматриваемые на данном занятии
Описание машины Поста
Машина Поста (МП), также как и машина. Тьюринга, относится к классу гипотетических (абстрактных) машин, и создана Постом практически одновременно с МТ.
МП состоит из бесконечной ленты, вдоль которой в обоих направлениях перемещается каретка с головкой чтения-записи. Ячейки ленты пронумерованы следующим образом: (-3, -2, -1, 0, 1, 2, 3)
|
номер ячейки |
-2 |
-1 |
0 |
1 |
2 |
3 |
В каждой ячейке ленты может быть записан пустой символ ("_") или символ-метка ("I"). Ни каждом шаге каретка перемещается только на одну ячейку.
Состояние МП определяется состоянием ленты (комбинацией пустых и занятых ячеек) и номером ячейки, на которую настроена каретка.
Работа МП состоит в том, что каретка передвигается вдоль ленты и записывает или стирает метки.
Назовем командой МП одну из следующих шести функций:
1) i. =>j . - движение вправо,
2) i. <= j - движение влево,
3) i. М j - запись .метки.
4) i. С j - стирание метки,
5) i. ?(j1, j2) - передача управления.
6) i. стоп - останов,
где i, j, j1, j2 – натуральные числа.
Примеры.
137. => j - движение вправо,
25. ?(35,21) - передача управления,
6386.стоп - останов.
Составлявшее команды МП имеют следующий смысл :
i - номер команды,
j - отсылка к команде с номером.
Программа МП - конечный непустой список команд МП, обладающий следующими свойствами:
1) все команды последовательно пронумерованы, начиная с 1,
2) отсылка любой из команд (за исключением команды стоп) есть номер одной из команд программы (включая номер той жe команды).
Работа МП определяется согласно некоторой программе и начальному состоянию. Будем считать, что в начальном состоянии каретка всегда настроена на ячейку с номером 0, то есть начальное состояние определяется только содержимым ленты.
Уточним действие команд (в порядке, приведенном выше):
|
№ |
Команда |
Комментарий |
|
1 |
i. =>j |
сдвиг каретки вправо на одну ячейку и переход на команду с номером j. |
|
2 |
i. <= j |
сдвиг каретки влево на одну ячейку и переход на команду с номером j |
|
3 |
i. М j |
запись метки в текущую ячейку и переход на команду с номером j (если в ячейке метка уже была, то команда невыполнима) |
|
4 |
i. С j |
стирание метки в текущей ячейке и переход на команду с номером j (если ячейка уме пуста, то команда невыполнима) |
|
5 |
i. ?(j1, j2 |
если обозреваемая ячейка пуста, переход к команде с номером j1 , в противном случае - к j2 |
|
6 |
i. стоп |
МП останавливается |
Выполнение программы может привести к одному из трех случаев:
1) нормальный останов по команде останова,
2) аварийный останов по невыполнимой команде,
3) зацикливание (бесконечная работа).
Пример 1. Пусть натуральное число, записанное на ленте МП, представляется соответствующей последовательностью меток (число n представляется (n+1) меткой). Например, число 3 представляется
следующим образом:
|
… |
_ |
_ |
I |
I |
I |
I |
_ |
_ |
_ |
… |
|
-2 |
-1 |
0 |
1 |
2 |
3 |
4 |
5 |
Программа прибавления к исходному числу единицы может выглядеть следующим образом :
1. <= 2
2. М 3
З. стоп
В качестве упражнения можно рассмотреть более сложные случаи:
Пример 2
Даны два массива меток, которые находятся на некотором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива.
Решение:
1.с (удалить) 2
2.=>(вправо) 3
3.? (4,2)
4.м (метка) 5
5.=> 6
6? (7,10)
7.<=(влево) 8
8.? (9,7)
9.=> 1
10.стоп
Задания для выполнения на практическом занятии
Задания для самостоятельной работы