Программой машины Поста называют конечный непустой (т.е. содержащий хотя бы одну команду) список команд машины Поста, обладающий следующими двумя свойствами:
1) на первом месте в этом списке стоит команда с номером 1, на втором месте (если оно есть) – команда с номером 2 и т.д. Вообще на n-м месте стоит команда с номером n;
2) отсылка любой из команд списка совпадает с номером некоторой команды списка.
Число команд программы называется длиной программы.
Наибольший интерес представляют причины останова машины при выполнении программы:
— останов по команде «стоп». Такой останов называется результатным и указывает на корректность программы (алгоритма);
— останов при выполнении недопустимой команды. В этом случае останов называют безрезультатным;
— машина не останавливается никогда. В этом случае, как и в предыдущем, имеем дело с некорректной программой.
Примеры типичных программ.
1. Задано начальное положение каретки. На пустой ленте записать две метки: одну в секцию над кареткой, вторую справа от нее.
Информатика. Машина Поста.
| 1 V 2 |
| 2 ® 3 |
| 3 V 4 |
| 4 стоп 4 |
2. Организация циклического процесса. На ленте имеется запись нескольких меток подряд, и каретка находится под самой крайней меткой справа. Перевести каретку влево до первой пустой позиции.
| 1 2 3 стоп 3 |
3. Представление чисел в машине Поста. Число K представляется на ленте машины Поста идущими подряд K+1 метками (одна метка означает число нуль). Между двумя числами делается интервал как минимум из одной пустой секции на ленте.
Например, запись чисел 3 и 5 выглядит на ленте следующим образом и не является позиционной:
4. Увеличить записанное число на 1. Для решения можно переместить каретку влево (или вправо) до первой пустой секции, а затем записать в нее метку.
4. Предположим, что каретка расположена на расстоянии нескольких клеток слева от числа, к которому нужно прибавит 1. Программа усложнится, за счет появления «блока поиска числа» (первая и вторая строка).
| 1 ® 2 3 4 4 V 5 5 стоп 5 |
Сложение натуральных чисел.
Осуществить на машине Поста сложение чисел – значит составить такую программу, которая, будучи применена к ленте, содержащей записи чисел m1, m2,…,mk (k ≥ 2), приводила бы к результативной остановке, причем после этой остановки на ленте оказалась бы запись числа m1 + m2 +…+ mk.
Сделаем ряд уточнений:
— в начале на ленте не записано ничего, кроме чисел m1, m2,…,mk, и в конце не было записано ничего, кроме их суммы;
— не будем налагать никаких ограничений на положение каретки в конце, что же касается ее положения в начале, то для простоты будем считать, что в начальном состоянии каретка стоит против самой левой из отмеченных секций;
— можно сделать различные предположения о расстоянии между массивами, служащими для записи чисел. В наиболее простом случае расстояние между соседними массивами равно 1;
Как программировать машину Поста? Душкин объяснит
— можно накладывать те или иные ограничения на количество слагаемых, считая это количество заранее заданным или произвольным.
Задача 1. Составить программу сложения двух чисел, записанных на расстоянии 1 друг от друга.
В силу сделанных предположений начальное состояние для задачи имеет вид:
Проще всего решить задачу, «заполнив» отметкой пустую секцию между массивами. Тогда, если слагаемыми были числа m1 и m2, на ленте возникнет m1+ m2 +3 отмеченных секций, в то время как их должно быть m1+ m2 +1. Поэтому нужно стереть две лишние метки. Программа реализует описанные выше действия.
| 1 ® 2 | 4 ® 5 | 7 C 8 |
| 8 9 9 С 10 | ||
| 3 V 4 | 6 7 | 10 стоп 10 |
Написать для машины Поста программу сложения двух чисел, записанных на ленте и расположенных через одну пустую клетку друг от друга.
Как быстро выучить стихотворение наизусть? Запоминание стихов является стандартным заданием во многих школах.
Как научится читать по диагонали? Скорость чтения зависит от скорости восприятия каждого отдельного слова в тексте.
Как быстро и эффективно исправить почерк? Люди часто предполагают, что каллиграфия и почерк являются синонимами, но это не так.
Как научится говорить грамотно и правильно? Общение на хорошем, уверенном и естественном русском языке является достижимой целью.
- Обратная связь
- Правила сайта
Источник: www.soloby.ru
Абстрактная машина Поста
Машина Поста состоит из ленты и каретки [считывающая и записывающая головка]. Лента бесконечна и разделена на секции одинакового размера.
В каждую секцию ленты заносится один символ двоичного информации, который подлежит обработке. Один из символов двоичного алфавита — метка «V», другой — пустота.
Если в секцию занесена «V» — секция отмеченная, если в секции «V» нет — секция пустая или неотмеченная.
Каретка может передвигаться вдоль ленты влево и вправо. Когда она неподвижна, она стоит против ровно одной секции ленты; говорят, что каретка обозревает эту секцию. А такая секция называется текущей или обозреваемой.
За единицу времени, которая называется шагом, каретка может сдвинуться на одну секцию влево или вправо. Кроме того, каретка может также распознать стоит или нет метка в обозреваемой ею секции, может заносить метку в пустую секцию и может удалять метку из отмеченной ячейки.
Команды, по которым каретка должна занести метку в отмеченную секцию или удалить метку из пустой секции являются недопустимыми.
Система команд машины Поста
Формат команды: nKm, где:
n — номер текущей команды;
K — команда из системы команд машины Поста [см. табл.];
m — ссылка — номер команды, которая будет выполняться следующей.
Последовательность команд из системы команд — программа, если:
1) на n — ом месте этой программы будет стоять команда с номером n.
2) ссылке m соответствует реальная команда в программе.
| a→b | Сдвиг каретки вправо, содержимое ленты не меняется. |
| a←b | Сдвиг каретки влево, содержимое ленты не меняется. |
| aVb | В обозреваемую секцию ставится метка «V». Выполнение этой команды возможно только в том случае, если обозреваемая секция пустая, в противном случае команда считается невыполнимой. |
| a↕b | Каретка стирает метку в обозреваемой секции. Выполнение этой команды возможно только в том случае, если обозреваемыя секция содержит метку, в противном случае команда считается невыполнимой. |
| a?b1,b2 | Команда передачи. Проверяется содержимое текущей секции, если метки нет, то происходит передача управления команде с номером b1, иначе, если метка есть — команде с номером b2. Содержимое ленты не меняется. |
| a![b] | Команда останова машины. Содержимое ленты не меняется. У команды остановки ссылка не обязательна. |
Пример программы сложения двух чисел для машины Поста
| 1 | ← | 2 | поиск начала первого числа: сдвигаемся влево | |
| 2 | ? | 3 | 1 | до тех пор, пока не встретим неотмеченную ячейку |
| 3 | → | 4 | сдвигаемся вправо, на 1-ую метку первого числа | |
| 4 | ↕ | 5 | удаляем ее | |
| 5 | → | 6 | ищем конец первого числа: сдвигаемся вправо, | |
| 6 | ? | 7 | 5 | пока каретка не встанет на неотмеченную ячейку |
| 7 | v | 8 | ставим метку | |
| 8 | → | 9 | проверяем заполнился ли промежуток между числами | |
| 9 | ? | 1 | 10 | если не заполнился- на первую строку, иначе — переход на конец |
| 10 | ! | конец |
Источник: akak-ich.ru