8
Машина Поста
Вообщше-то, надо сказать, это во все нижкая не машина. Это, если угодно, чертеж машины. А еще правильнее сказать — рассказ о машине. Но уже если рассказывать, то рассказывать сначала **).
Тридцать пять лет назад в двух математических журналах (в издавемом в США международном «Журнале символьческой логики» и в «Трудах Лондонского математического общества») почти одновременно появились двух выдающихся учены: американца Эмиля Л. Поста и английина Алена М. Тыоринена,
*) Школой руководит Валентин Николаевич Касаткин, автор популярных книг «Азбука кибернетики» и «Секрет кибернетики». В конце статьи мы приводим несколько присланных им задач.
**) Данное здесь описание «машины Поста» принадлежит Ю. А. Гастеву.
посвященные уточнению издавна употребляемого в математике (да и не только в математике) понятия алгоритма (или алгоритма *)). Алгоритм — это единый общий метод, предназначный для решения целой серии одномплиных задач. Единый — в том смысле, что, зная соответствующий алгоритм, мы можем каждую задачу из данной серии решить без всяких дополнительных разумений, как говорят, «чисто механические», «форматное».
«Формально», «безумно», «механические» — в эти слова часто включается довольно обидный смысл. И почти всегда напрасно! Посудите сами: допуматься до способа сложения любых многозначных чисел «столбиком» в первый раз было, конечно,
*) Способ написания определяется лишь традициями и привлечений. Сохранить в русском языке буква θ («фита» — то же, что греческая «тэта»), то и продолжали бы все писать «алгориθм»!
10
ни даже Гауссу не было нужны в общем понятии алгорифма. Но понять — и, тем более, доказать, что бывают неразрешимые массовые проблемы (то есть классы задач, не допускающие никакого решения, единого для всего класса*)), без такого общего определения уже, конечно, не удостся.
Не менее существена и чисто «положительная» ценность общего понятия алгорифма: понимание общих закономерностей, которые подчиняются самые различные алгорифмы, играет первостепенно роль для «машинной» математики. Как известно, универсальная электронная вычислительная машина «способна воспринять» программы самых разнообразных математических (да и далеко не только математических) задач**). Машинная же программа это и есть алгорифм, только вдобавок приспособленный к особенностям данной конкретной машины (или записанный на специальном «языке программирования», допускаем «трасляцию», то есть попросту перевод, на языки команд разных машин).
Уже первые работы Тыорига и Поста, посвященные уччению понятия алгорифма, давали возможность существенного продвижения в обихах указанных направлениях. Неосредственным побудительным мотивом к таким уччению в обихах случах послужило желание установить алгорифмческую неразрешимость некоторых математических массовых проблем (и именно Посту принадлежат первые результаты в этом направлении). Любопытно, что оба учченных пошли, по существу, по одному и тому же пути (вскоре выяснилось, что этот путь—не единственно
*) Об алгорифмических неразрешимых проблемах см., например, статью Ф. Л. Варраховского и А. Н. Колмогорова «О решении десятий проблем Гильберта» («Квант», № 7, 1970).
**) См., например, статью Р. С. Гутера «Что умел машины» («Квант», № 5, 1970) и «Язык человека и язык машины» («Квант», № 10, 1971).
но возможный): вместе интуитивно понятных, но абсолотно непригодных для извлечения точных математических следствий, разговоров о «едином общеmentе, приготовном для решения целой серии однотипных задач» (см. начало этой заметки), Тыориг и Пост вывинули представление об алгорифме как о некоей абстрактной (мысленной) «машине», описанной в точных математических терминах и в то же время соответствующей нашим представлениям о вычислительной процессе, протекающем по правильам-командам определению стандартного вида.
Какое именно определение алгорифма принимает — Тыорига, Поста или принадлежшее кому-либо еще (наболее известны определения К. Гёделя, А. Чёрча, С. К. Клини, А. А. Маркова, А. Н. Колмогорова)—несущественно: вскоре выяснились, что все эти определения в определении смысле эквивалентны. Поэтому выбор какого-либо одного из этих уччений в качестве исходного определения не математической стороны дела, а удобством изложения.
«Машина Тыорига» описана и в сервисных, и в популярных книгах*).
«Машина Поста» в этом отношении повезло меняше, быть может, потому что «машина» эта, будучи проще «машины Тыорига», именно по этой причине требует, вообще говоря, более громоздкой системы команды для выполнения конкретной задачи. Кроме единственной статьи самого Поста, это уччение понятия алгорифма описано, по сути дела, лишь в одном месте: в серии из четырех статей В. А. Успенского в журнале «Matematika в школе» за 1967 год. Отсылая читатель к этим очень интересным (и ясно написанным) статьям, рассакjem теперь о «машине Поста» лишь самые первоначальные сведения, необходимые для понимания дальнейшего.
*) Из них числа в первую очередь рекомендуем читателю книгу Б. А. Трахтенброта «Алгоритмы и машинное решение задач», Физматиз, 1960, 2-е изд.
12
- машина doit do невыполнимой команды (печатание метки в отменной секции или стирание метки из пустой секции) — так называемая безрезультатная остановка;
- машина doit do команды остановки — результатом результатная остановки;
- ни один из первых двух случая не осуществится — машина будет работать бесконечно.
Пример 1. В программе
- ⇒2
- ξ 3
- стоп,
применной к пустой лente, безрезультатная остановка наступит уже на втором шагу. (так что до предписьваемой третьей команды результатной остановки дело так и не doit).
Пример 2. Программа - ⇒2
- ⇒3
- стоп,
применная к пустой лente, будет выполнять следующим образом: каретка передвиется на две секции вправо от обозреваемой, после чего машина остановится.
Пример 3. Если программа - ∨ 2
- ⇒3
- ⇒1
применить к пустой лente, то машина будет печатать, начиная с обозреваемой секции, метки через одну и никака не остановится.
Дальнейшие примеры читатель найдет в уже упомянутых статых В. А. Успенского.
Мы же сейчас предоставим слова участникам шкOLS юных кибернетиков «Малой академии наук», ученицам 9-го класса Бахчисарайской шкOLS № 2 Наташе Кудрявской, Ире Ломакиной и Светлане Приз, которые расскажут вам о своем опите обучения программированию с помощью машин Поста (работа которой в сильно упрощенном виде воспроизведут работу любой современной универсальной вычислительной машины). Девочки испытывали свои программы на изготовленный сотрудник Выши-
слительного центра Симферопольского педагогического института металлической модели, сабженной клавиши, тумблерами, штекерами и прочими непреемными атрибутами «кибернетическая машин». «Лента» в этой «действующей модели» состоит из электронических лампочки (40 штук; выход за пределы ленты квалифицирован как безрезультатная остановка машины), причем отмечаемые секции загораются, а страемые — гаснуть *).
Очень интересно программировать и видеть, как, подчиняясь воей программе, машина решает задачи. Счетчик команд позволяет видеть, какая команда выполняется в данной момент. Программа сначала записьается на бумаге, а затем с помощью штекеров запосится на наборное поле машин (каждой команде соответствует свой двойный код). Машина работает (в автоматическом режиме) не очень быстро, поэтому все действия хорошо наблюдаются; выполнение программы можно пристановить.
Интересно наблюдать, как машина выступает содержимом человека в различных играх. Мы решаем задачи и по составлению программы, пользоваться которых машина никака не проигрывает **). Вот пример такой программы. Условия игры: на ленте стоит подряд 26 меток, самая лева из которых обозревается картекой. Человек и машина ходят по очереди (начиная игру всегда человека), стирая за свой ход не более четырех меток. Тот, кто стирает последнюю метку, проигрывает. Если условия,
*) Мы специально не остававливались выше на всех этих впечатляющих деталях, дабы не отвлекать читателя от сутки дела; различие между «электронной моделью машины Поста» и описанной выше «спичечно-бумажной» примерного того же рода, что различие между магазинными чеками, отпечатными на электронском или ручном кассовом аппарате и выписанными от руки.
**) То есть всегда выигрывает: все эти игры таковы, что не допускают ничейного исхода.