математический анализ

Задание 1

Машина Поста :
В последовательности 10…1 удвоить внутренние 0.

Решение

Машина Поста - это универсальный исполнитель (абстрактная вычислительная машина), основанный на идеях работы американского математика Э.Л. Поста, целью которой было уточнение понятия алгоритма. Согласно тезису Поста, любой алгоритм может быть записан в виде программы для машины Поста.
Машина Поста состоит из каретки (считывающей и записывающей головки) и бесконечной ленты, разбитой на ячейки. Каждая ячейка ленты может быть либо пустой или содержать метку («1») или («0»).
На рис.1 приведено условное изображение машины Поста.


Рис. 1. Условное изображение машины Поста

Текущее состояние машины Поста описывается состоянием ленты и положением каретки. Состояние ленты – информация о том, какие секции пусты, а какие отмечены. Шаг – это движение каретки на одну ячейку влево или вправо. Состояние ленты может изменяться в процессе выполнения программы.
Кареткой управляет программа, состоящая из строк команд.
Всего для машины Поста существует шесть типов команд:
0,1,j - поставить метку, перейти к j-й строке программы.
X j - стереть метку, перейти к j-й строке программы.
- j - сдвинуться влево, перейти к j-й строке программы.
- j - сдвинуться вправо, перейти к j-й строке программы.
? j1; j2; j3 - если в ячейке нет метки, то перейти к j1-й строке программы, если в ячейке «0», перейти к j2-й строке программы, если «1» - к ячейке j3.
! – конец программы (стоп).

Варианты окончания выполнения программы на машине Поста:
• Команда "стоп" - корректная остановка. Возникает в результате выполнения правильно написанного алгоритма.
• Выполнение недопустимой команды – нерезультативная остановка. Случаи, когда головка должна записать метку там, где она уже есть, или стереть метку там, где ее нет, являются аварийными (недопустимыми).
• Уход в бесконечность, зацикливание. Машина Поста в результате работы алгоритма может вообще не остановиться (никогда не дойти до команды «стоп» и никогда не завершиться аварийной ситуацией).

Для правильного выполнения программы важно правильно указать начальное положение каретки.

По условию задачи предполагается, что каретка установлена в позиции над крайней левой единицей. Количество нулей внутри последовательности не ограничено. Требуется создать на ленте новую последовательность, в которой нулей внутри последовательности будет вдвое больше.



Идея алгоритма заключается в следующем.

1. Каретка сдвигается вправо и проверяет, есть ли «0».
2. «0» обнаружен.
3. «0» заменяется на «1». Предыдущая «1» стирается.
4. Ищется правый край последовательности.
5. В соседние ячейки записываются 2 «0».
6. Каретка возвращается в крайнюю левую позицию.
7. Вновь проверяется предыдущая ячейка.
8. Если «0», повторяем с пункта 3.
9. Если «1», стираем предыдущую метку.
10. Ищем правый край последовательности.
11. Устанавливаем конечную «1». Конец программы.

Обобщенная схема алгоритма приведена на рис. 2.


Рис.2. Обобщенная схема алгоритма


Укрупненная схема алгоритма приведена на рис. 3.



Рис. 3. Схема алгоритма
Проверку работы алгоритма проверим с помощью эмулятора машины Поста.