лекция 2 ОАиП Машина Поста ИС для эор. Лекция 2 тема Машина Поста. Литература

• Название: Лекция 2 тема Машина Поста. Литература
• Дата: 07.04.2022
• Размер: 34.59 Kb.
• Имя файла: лекция 2 ОАиП Машина Поста ИС для эор.docx
• Тип: Лекция; #452506

09.02.07 – Основы алгоритмизации и программирования – Лекция 2

ТЕМА: Машина Поста.

Литература: 1. http://inf1.info/algorithmterm – Лекции по теории алгоритмов.

2. Ильиных А.П. Теория алгоритмов: учебное пособие
Всякий алгоритм представим в форме машины Поста.

Машина Поста (МП) – абстрактная вычислительная машина, предложенная Эмилем Леоном Постом (Emil L. Post), которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».

Принцип работы

Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты. Каждая секция ленты может быть либо пустой – 0, либо помеченной меткой 1. За один шаг каретка может:

• 
  сдвинуться на одну позицию влево или вправо;
  
• 
  считать символ в том месте, где она стоит;
  
• 
  поставить символ в том месте, где она стоит;
  
• 
  стереть символ в том месте, где она стоит.
  

Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из строк команд.
Каждая команда имеет следующий синтаксис:

i K j,

где i – номер команды;

К – действие каретки;

j – номер следующей команды (отсылка).
Всего для машины Поста существует шесть типов команд:

V j – поставить метку, перейти к j-й строке программы;

X j – стереть метку, перейти к j-й строке программы;

 j – сдвинуться влево, перейти к j-й строке программы;

 j – сдвинуться вправо, перейти к j-й строке программы;

? j_l; j₂ – если в ячейке нет метки, то перейти к j_l-й строке программы, иначе перейти к j₂-йстроке программы;

! – конец программы (стоп).

У команды «стоп» отсылки нет.

После запуска возможны варианты:

• 
  работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);
  
• 
  работа может закончиться командой Stop;
  
• 
  работа никогда не закончится.
  

Пример. На ленте проставлена отметка в одной ячейке. Каретка стоит на некотором расстоянии левее этой ячейки. Необходимо перевести каретку к ячейке, стереть отметку и оставить каретку слева от ячейки.

▼

0

0

0

0

0

0

0

1

0

0

1. 

2. ? 1;3

3. X

4. 

5. !
Пример. Вычитание натуральных чисел: Р – Q.

Целое положительное число на ленте машины Поста представимо идущими подряд метками, которых на одну больше, чем кодируемое число. Это связано с тем, что одна метка обозначает ноль, а уже две – единицу, и т.д. Будем разделять числа нулём. Исходное положение каретки помечено символом «▼».

▼

0

0

1

1

1

1

1

0

1

1

1

0

0

0

Р Q

Программа вычитания состоит из последовательного затирания крайних левых меток у Q и правых у Р:
1. Х – стираем левый символ у Q

2.   проверяем, не закончилось ли еще Q

3. ? 4;5

4. !  стоп, если затерли все метки числа Q

5 . 

6. ? 5; 7  цикл поиска Р

7. Х  стираем правый символ у Р

8. 

9. ? 8; 1  цикл поиска Q

Если переход происходит на следующую по порядку строку, то номер команды перехода не указывается (для наглядности текста). В 6-ой строке возможно зацикливание, если Q > Р.

Решение задач

Задача 1: увеличить число 3 на единицу (изменить значение в памяти с 3 на 4). Каретка стоит где-то слева от меток и обозревает пустую ячейку.

Решение:

1. 

2. ? 1; 3

3. 

4. V

5. !

Исходное состояние: ▼

0

0

0

0

1

1

1

1

0

0

Результат: ▼

0

0

0

1

1

1

1

1

0

0

Задача 2: пусть задано исходное состояние головки и требуется на пустой ленте написать две метки: одну в секцию под головкой, вторую справа от нее.

Решение:

1. 
   V
   
2. 
   →
   
3. 
   V
   
4. 
   !
   

Исходное состояние: ▼

0

0

0

0

0

0

1: ▼

0

0

1

0

0

0

2: ▼

0

0

1

0

0

0

3: ▼

0

0

1

1

0

0

Задача 3: на ленте имеется некоторое множество меток (общее количество меток не менее 1). Между метками множества могут быть пропуски, длина которых составляет одну ячейку. Заполнить все пропуски метками.

Решение:

1. 
   → 2
   
2. 
   ? 3, 1
   
3. 
   → 4
   
4. 
   ? 5, 6
   
5. 
   !
   
6. 
   ← 7
   
7. 
   v 1
   

Контрольные вопросы:

1. 
   Дайте определение машины Поста.
   
2. 
   Какие действия может выполнять каретка машины Поста?
   
3. 
   Что необходимо задать для работы машины Поста?
   
4. 
   Как записываются команды для машины Поста? Какие команды способна выполнять машина Поста?
   
5. 
   Как может развиваться процесс выполнения программы машиной Поста?
   

Д/з: составить программу для машины Поста, которая складывает числа P и Q (достаточно поставить 1 между ними и стереть два крайних правых символа у Q).