Тема- Машина Поста МП Основные понятия и определения рассматриваемые на данном занятии Машина Пос

Работа добавлена на сайт samzan.net:

Практическое занятие №6

Тема: Машина Поста (МП)

Основные понятия и определения, рассматриваемые на данном занятии

1.  Машина Поста
2.  Работа МП
3.  Команда МП
4.  Программа МП

Описание машины Поста

Машина Поста (МП), также как и машина. Тьюринга, относится к классу гипотетических (абстрактных) машин, и создана Постом практически одновременно с МТ.

МП состоит из бесконечной ленты, вдоль которой в обоих направлениях перемещается каретка с головкой чтения-записи. Ячейки ленты пронумерованы следующим образом: (-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

З. стоп

В качестве упражнения можно рассмотреть более сложные случаи:

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

Пример 2

Даны два массива меток, которые находятся на некотором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива.

Решение:

1.с (удалить) 2

2.=>(вправо) 3

3.? (4,2)

4.м (метка) 5

5.=> 6

6? (7,10)

7.<=(влево) 8

8.? (9,7)

9.=> 1

10.стоп

Задания для выполнения на практическом занятии

1.  Найти массив и встать на его начало. Каретка располагается в любом месте, но не над массивом.
2.  Составить программу нахождения разности двух целых неотрицательных чисел a и b. Если a меньше b, то перед разностью через одну пустую ячейку поставить метку. Каретка находится над крайней левой меткой левого числа.
3.  Дан массив из N Меток. Сделать из него массив, в котором будет 2N+1 меток. Если полученный массив делится нацело на 3, то справа от него, через одну пустую ячейку, поставить две метки; если нет - то три метки. Каретка находится над крайней левой меткой.

Задания для самостоятельной работы

1.  Произвести умножение двух чисел. Каретка располагается над пустой ячейкой, которая разделяет данные массивы.
2.  Даны два целых положительных числа. Найти их разность по модулю.

1. круглым столом посвященным теме вынесенной в заголовок данного материала отчасти были уж не столь категор.html
2. правовом поле Из этих актов реализации правовых предписаний в повседневной жизни людей складывается тот
3. тема інверсної населеності.html
4. Петрушевская Уроки музыки Драма в двух действиях ДЕЙСТВУЮЩИЕ ЛИЦА Г р а н я 38 лет - Н и н
5. тема гражданского права как правовой отрасли
6.  6 ldquo;Определение энтальпии нейтрализацииrdquo; З
7. Чинники процесу антропогенезу на території України
8. а Обычный дозвуковой профиль с тупой передней кромкой не годится
9. Искусство как категория эстетики
10. Общие данные 2 Географическое положение 3
11.  Ключи-раркиИтак
12. а о которых заявлено в орган по рассмотрению индивидуальных трудовых споров ~ ст
13. АТиСО
14. На тему- СТАНОВЛЕННЯ АДВОКАТУРИ В УКРАЇНІ 1917 1921 рр
15. Тема 7-Облік виробничих запасів
16. Управленческий учет в рыночной экономике
17.  Частота випорожнень у здорової дитини яка знаходиться на грудному вигодовуванні може становити- А
18.  Спите меньше Это поможет вам сделать вашу жизнь более полной и продуктивной
19. ОРЛОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ПЕДАГОГИКИ И ПСИХОЛОГИИ КАФЕДРА технологий психолог
20. История Беларуси 2012 Первобытное общество на территории Беларуси

Материалы собраны группой SamZan и находятся в свободном доступе