Урок 33
Уточнение понятие алгоритма. Универсальные исполнители
§34. Уточнение понятия алгоритма
Содержание урока
Машина Поста
Машина Поста
Практически одновременно с Тьюрингом (в том же 1936 г.) и независимо от него американский математик Э. Л. Пост предложил ещё более простую систему обработки данных, на основе которой позднее была построена так называемая машина Поста.
Лента в машине Поста (так же как и в машине Тьюринга) бесконечна и разбита на ячейки. Каждая ячейка может содержать метку (быть отмечена) или не содержать её (пустая ячейка) (рис. 5.6).
Таким образом, Пост сократил алфавит всего до двух цифр. Это допустимо, потому что любые данные можно перекодировать в двоичный код, сопоставив каждой букве исходного алфавита уникальную последовательность нулей и единиц.
Кроме того, алгоритм работы машины Поста задаётся не в виде таблицы, а как программа, состоящая из отдельных команд. Система команд машины Поста содержит только 6 команд:
← — переместить каретку на 1 ячейку влево;
→ — переместить каретку на 1 ячейку вправо;
0 — стереть метку в рабочей ячейке (записать 0);
1 — поставить метку в рабочей ячейке (записать 1);
? n0, n1 — если в рабочей ячейке нет метки, перейти к строке n0, иначе перейти к строке n1;
стоп — остановить машину.
Попытка стереть метку там, где её нет, или поставить метку повторно считается ошибкой, и машина аварийно останавливается.
Все строки в программе нумеруются по порядку, это необходимо для работы команды ветвления (? n0, n1). С помощью этой команды можно также строить циклы как с предусловием, так и с постусловием. Например, следующая программа перемещает каретку влево до первой отмеченной ячейки:
Если после выполнения команды ←, →, 0 или 1 требуется перейти не на следующую строку, а на какую-то другую, то номер этой строки можно записать в конце команды. Например, команда
означает «переместить каретку влево и перейти на строку 3».
При работе с машиной Поста числа обычно записывают в унарной (единичной) системе счисления, в виде непрерывной цепочки меток нужной длины (вспомните счётные палочки в младшей школе). Например, на ленте, показанной на рис. 5.6, записано число 4.
Пост предположил, что любой алгоритм может быть записан как программа для предложенного им исполнителя. В теории алгоритмов доказано, что машины Поста и Тьюринга одинаковы по своим возможностям. Это значит, что круг задач, который они решают, тоже одинаков.
Следующая страница 
Нормальные алгорифмы Маркова
Cкачать материалы урока
Машина Поста
Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы.
В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.
Машина Поста состоит из …
Текущее состояние машины Поста описывается состоянием ленты и положением каретки. Состояние ленты – информация о том, какие секции пусты, а какие отмечены. Шаг – это движение каретки на одну ячейку влево или вправо. Состояние ленты может изменяться в процессе выполнения программы.
Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис:
i K j,
Всего для машины Поста существует шесть типов команд:
У команды «стоп» отсылки нет.
Варианты окончания выполнения программы на машине Поста:
Элементарные действия (команды) машина Поста проще команд машины Тьюринга. Поэтому программы для машины Поста имеют большее число команд, чем аналогичные программы для машины Тьюринга.
Почему достаточно лишь два различных символа (есть метка, нет метки)? Дело в том, что любой алфавит может быть закодирован двумя знаками; в зависимости от алфавита возрастать может только количество двоичных символов в букве алфавита.
Пример работы машины Поста:
Машина Поста
Практически одновременно с Тьюрингом (тоже в 1936 году) и независимо от него, американский математик Эмиль Пост предлагает еще более простого исполнителя, названного позже машиной Поста. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».
Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на ячейки бесконечной в обе стороны ленты (также как у машины Тьюринга). Каждая ячейка ленты может быть либо пустой — 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит.
Т.о., Пост сократил алфавит всего до двух цифр. Это допустимо, потому что любые данные можно перекодировать в двоичный код, сопоставив каждой букве исходного алфавита уникальную последовательность нулей и единиц.
Алгоритм работы машины Поста задается не в виде таблицы, а как программа для универсального исполнителя.
Программа состоит из конечного числа строк и использует всего 6 команд.
где N. — номер строки, J — строка на которую переходит управление далее.
Попытка стереть метку там, где ее нет, или поставить метку повторно считается ошибкой, и машина аварийно останавливается
Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки).
После запуска возможны варианты:
— работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);
— работа может закончиться командой Stop;
— работа никогда не закончится.
Все строки в программе нумеруются по порядку, это необходимо для работы команды ветвления (? n0,n1). С помощью этой команды можно также
строить циклы, как с предусловием, так и с постусловием.
После команд «←”, «→”, «0” и «1” можно указать номер строки, на которую нужно перейти сразу после выполнения этой команды. Например, команда ← 3 означает «переместить каретку влево и перейти на строку 3”.
При работе с машиной Поста числа обычно записывают в унарной (единичной) системе счисления, в виде непрерывной цепочки меток нужной длины (вспомните счетные палочки в младшей школе).
Пример работы машины Поста : прибавление к числу единицы.
Пост предположил, что любой алгоритм может быть записан как программа для машины Поста.
В теории алгоритмов доказано, что машины Поста и Тьюринга одинаковы по своим возможностям. Это значит, что круг задач, который они решают, тоже одинаков.
_________________________________________________________________________________________________
Вопросы:
1. Сравните машины Тьюринга и Поста.
2. Зачем нумеруются строки в программе для машины Поста?
Задачи:
1. Напишите программу для машины Поста, которая увеличивает (уменьшает) число в единичной системе счисления на единицу. Каретка расположена слева от числа.
2. Напишите программу для машины Поста, которая складывает два числа в единичной системе счисления. Каретка расположена над пробелом, разделяющим эти числа на ленте.
Как будет работать каждая из программ при различных начальных состояниях ленты?
Компьютерный практикум:
(Методические материалы И.Г. Семакина)
1. На информационной ленте либо справа, либо слева от головки, стоящей под пустой клеткой, находится массив меток. Требуется присоединить к этому массиву одну метку. Составить универсальную программу. Реализуйте программу на учебной модели машины Поста. Протестируйте программу.
2. На ленте расположен массив из 2n-1 меток. Составить программу отыскания средней метки и стирания ее. Реализуйте программу на учебной модели машины Поста. Протестируйте программу.
3. На ленте расположен массив из 2n меток. Составить программу, по которой машина раздвинет на расстояние в одну клетку две половины данного массива. Реализуйте программу на учебной модели машины Поста. Протестируйте программу.
Машина Поста программа (К.Поляков)
Дополнительные источники:
1. К.Ю. Поляков, Е.А. Еремин «Элементы теории алгоритмов». Журнал «Информатика» №1, 2012 г.
Программирование на машине Поста
Недавно на хабре появилось сразу два материала, посвященных языкам из «большой четверки тьюринговых трясин»: про алгоритм Маркова и Brainfuck. Думаю, для полноты картины будет интересно сравнить эти эзотерические системы с еще одним важным алгоритмическим примитивом — машиной Поста, которой я как раз занимаюсь.
Машина Поста (wiki; для простоты оттуда же взят вариант синтаксиса) похожа на всем известную машину Тьюринга, однако обладает интересными особенностями. Она содержит лишь 6 команд, кроме того, в ячейки-биты памяти могут записываться лишь 2 символа (двоичное кодирование информации). «Естественно», никакой дополнительной памяти, не зря же эзотерикой зовется!
Таким образом, при программировании на машине Поста помимо необходимости совладать с оккамовским синтаксисом надо думать о том, как записать на ленте все промежуточные результаты, не потеряв по пути обратную тропинку к остаткам входных данных. Почему «остаткам»? Зачастую ввиду отсутствия дополнительной памяти приходится обрабатывать входные данные итеративно (а иногда и рекурсивно). Надеюсь, вышеизложенное убедительно доказывает, что написание привычных алгоритмов на машине Поста — неплохая разминка для мозгов и весьма увлекательное занятие.
Пример
Рассмотрим одну из кратчайших реализаций умножения двух натуральных чисел. Числа n и m записываются на ленте в единичной системе счисления, разделяются одной пустой ячейкой. Вход/выход алгоритма может быть таким (отмечено начальное положение каретки):
Идея алгоритма — краткое сложение. В каждом проходе цикла машина «откусывает» один бит от левого множителя и «копирует» самый правый имеющийся блок (сперва это второй множитель, затем — его последняя копия). Когда левый множитель «закончится», на ленте остается n блоков по m единиц. Их слияние дает искомое число n*m.
Проверить корректность алгоритма можно в уме, на листочке, либо с помощью этой программы.
Это самая короткая известная мне реализация умножения. Однако, потенциально ее можно ужать еще сильнее, если придумать, как экономно объединить процессы создания копий и их слияния в единый массив.
P. S. «Большой четверкой» называю машину Тьюрига, Поста, систему Маркова и Brainfuck — самые изучаемые тьюринговые трясины.
Машина Поста (устройство, команды и принцип работы)
Содержимое разработки
Практически одновременно с Тьюрингом (тоже в 1936 году) и независимо от него, американский математик Эмиль Пост предлагает еще более простого исполнителя, названного позже машиной Поста. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».
Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы.
В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.
Структура машины Поста:
Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на ячейки бесконечной в обе стороны ленты (также как у машины Тьюринга). Каждая ячейка ленты может быть либо пустой — 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит.
Т.о., Пост сократил алфавит всего до двух цифр. Это допустимо, потому что любые данные можно перекодировать в двоичный код, сопоставив каждой букве исходного алфавита уникальную последовательность нулей и единиц.
Алгоритм работы машины Поста задается не в виде таблицы, а как программа для универсального исполнителя.
Программа состоит из конечного числа строк и использует всего 6 команд.
где N. — номер строки, J — строка на которую переходит управление далее.
Попытка стереть метку там, где ее нет, или поставить метку повторно считается ошибкой, и машина аварийно останавливается.
Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки).
После запуска возможны варианты:
— работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);
— работа может закончиться командой Stop;
— работа никогда не закончится.
Все строки в программе нумеруются по порядку, это необходимо для работы команды ветвления (? n0,n1). С помощью этой команды можно также строить циклы, как с предусловием, так и с постусловием.
Пост предположил, что любой алгоритм может быть записан как программа для машины Поста.
В теории алгоритмов доказано, что машины Поста и Тьюринга одинаковы по своим возможностям. Это значит, что круг задач, который они решают, тоже одинаков.
После команд «←”, «→”, «0” и «1” можно указать номер строки, на которую нужно перейти сразу после выполнения этой команды. Например, команда ← 3 означает «переместить каретку влево и перейти на строку 3”.
При работе с машиной Поста числа обычно записывают в унарной (единичной) системе счисления, в виде непрерывной цепочки меток нужной длины (вспомните счетные палочки в младшей школе).
1. Напишите программу для машины Поста, которая увеличивает (уменьшает) число в единичной системе счисления на единицу. Каретка расположена слева от числа.
2. Напишите программу для машины Поста, которая складывает два числа в единичной системе счисления. Каретка расположена над пробелом, разделяющим эти числа на ленте.
Пример работы машины Поста:
Задача: увеличить число 3 на единицу (изменить значение в памяти с 3 на 4).
Целое положительное число на ленте машины Поста представимо идущими подряд метками, которых на одну больше, чем кодируемое число. Это связано с тем, что одна метка обозначает ноль, а уже две – единицу, и т.д.
Допустим, точно известно, что каретка стоит где-то слева от меток и обозревает пустую ячейку. Тогда программа увеличения числа на единицу может выглядеть так: