Машина Поста и алгорифмы Маркова
Ещё два строгих ответа на вопрос «что такое алгоритм». 11 класс,
углублённый уровень — пара тринадцатая.
Уроки 25–26 поурочного плана: «Машина Поста» и «Нормальные алгорифмы Маркова».
На прошлой паре была машина Тьюринга. Сегодня — машина, у которой на ленте всего
два знака, и исполнитель вовсе без ленты: он переписывает слово по формулам.
Ещё два уточнения понятия алгоритма
Эмиль Пост, 1936
В том же году, что и Тьюринг, и независимо от него описал машину ещё проще:
клетка ленты либо пуста, либо отмечена. Программа — нумерованный список
команд.
А. А. Марков, конец 1940-х — начало 1950-х
Нормальные алгорифмы: ни ленты, ни каретки. Есть слово и список формул
«что на что заменить». Алгорифм переписывает слово, пока не остановится.
Все эти модели равносильны: что вычисляет одна,
вычисляют и другие — машина Тьюринга, машина Поста, алгорифмы Маркова. Поэтому
любую из них можно брать за строгое определение алгоритма.
«Алгорифм» — не опечатка: так писал сам Марков, и так это слово осталось в
названии модели.
Машина Поста: лента, каретка, команды
Метка в уже отмеченную клетку и стирание
пустой — аварийная остановка: результата нет. Переход к номеру,
которого нет в программе, — тоже ошибка программы.
Единственная команда-развилка — 
. Порядок: сначала куда
идти, если пусто, потом — если отмечено.
Как выполнять вручную: столбиком
программа
Каретка — над самой левой меткой ряда из трёх меток (клетки 3–5), начинаем
с команды 1.
Пиши столбиком: номер команды, клетка под кареткой, пуста она или
отмечена. Шаг — одна выполненная команда, «!» тоже считается. Ленту
перерисовывай после каждого V и X.
Каретка идёт вправо по ряду меток до первой пустой клетки
и ставит в неё метку: ряд стал на одну метку длиннее — машина прибавила
единицу к числу, записанному рядом меток.
Стёртая команда: подставь и прогони
Задача: машина должна делать известное (например, «стереть ряд» или «удвоить
ряд»), но одна команда в программе стёрта. Какую поставить?
- Подставь вариант на место ★.
- Прогони машину на коротком ряду: одна-две метки. Ошибка вылезает уже
там.
- Сверь ленту после остановки с тем, что должно получиться.
Неверный вариант выдаёт себя одним из четырёх способов:
авария (метка в отмеченную, стирание пустой), зацикливание,
переход к несуществующей команде или просто не та лента после
остановки.
Верный вариант должен подойти на всех рядах, а не на одном. На уроке
хватает короткого ряда: неверные варианты ломаются сразу.
Нормальный алгорифм Маркова
Работает со словом — строкой символов. Схема — упорядоченный
список формул:
— заменить P на Q;
— заменить и остановиться (заключительная).
λ — пустое слово: «ничего».
Один шаг
- Просмотреть формулы сверху вниз и взять первую, левая часть
которой входит в слово.
- Заменить её самое левое вхождение на правую часть.
- Формула заключительная — стоп, иначе снова к пункту 1.
Ни одна формула не подходит —
тоже стоп. Это второй
способ остановки. А бывает, что алгорифм не останавливается никогда: схема
на слове
.
Порядок формул — часть алгорифма: переставь их — получишь другой алгорифм.
Пример: одна формула сортирует
схема
Слово 
. Каждый шаг — самое левое 
заменяется на 
.
Пока в слове есть «b перед a», формула их меняет. Стоп —
когда все a впереди: алгорифм сортирует буквы.
Что делает алгорифм: прогони и сравни
Задача: дана схема и четыре описания («удваивает слово», «стирает последнюю
букву»…). Какое верно?
- Возьми короткое слово, на котором все четыре описания дают разное.
- Прогони схему по шагам.
- Сравни итог с каждым описанием — совпадёт ровно одно.
Слово из одной буквы часто не различает варианты:
«развернуть» и «оставить как есть» на
дают одно и то же. Бери три-
четыре знака.
Свой алгорифм: приём бегунка
меняет a на b и b на a
По одной формуле в строке, по порядку; заключительная — с точкой после
стрелки; пустое слово — λ.
ставит служебную метку
в начало; формулы
проводят её по слову,
меняя буквы; заключительная стирает
в конце.
Формула с пустой левой частью подходит к любому
слову — поэтому её пишут последней. Поставь её первой — алгорифм будет
бесконечно приписывать звёздочки.
Что верно о двух моделях
Верно
- Каретка Поста за шаг сдвигается не больше чем на клетку.
- За шаг Марков заменяет одно, самое левое вхождение.
- Заключительную формулу отмечает «·», а не место в списке.
Неверно
- «Машина Поста слабее Тьюринга — у неё всего два знака». Равносильны:
любой символ кодируется группой меток.
- «Алгорифм всегда останавливается». Подстановка может удлинять слово.
- «Стоп стирает ленту». Нет, только останавливает.
Что делаем дальше
- Обзорный практикум — шесть задач, все сразу на странице, в любом
порядке: понятия, выполнить программу Поста, выполнить алгорифм Маркова,
стёртая команда, что делает алгорифм и свой алгорифм.
- Шаги машины и подстановки — столбиком на черновике, как на слайдах.
- Свой алгорифм страница выполняет на всех коротких словах и показывает,
где он ошибся.
Отметка: закрыто 6 из 6 — «5», 5 — «4», 3 или 4 — «3». Исправленная задача не
засчитывается — за ошибку приходит новая, добирать можно до пятёрки. В своём
алгорифме ошибкой считается только первая неудачная проверка: дальше это
отладка.
За работу
Практикум «Машина Поста и алгорифмы Маркова» — в общей папке и на
сайте. Не успел на уроке — пройди дома: вариант будет другой, сдаётся тем же
кодом.
Карточку в тетрадь можно взять с собой: на ней команды машины Поста, шаг
алгорифма Маркова и приём бегунка.
/ 
