Машина Поста | Квант 5 1972

Н. Кудрявская, И. Ломакина, С. Приз

Страница переведена на новый сайт https://myeducation.su/ :

страница ФИЗИКО-МАТЕМАТИЧЕСКИЙ ЖУРНАЛ Квант (1972)

Ниже текст для быстрого ознакомления с темой. В нём формулы отображаются некорректно. Смотрите оригинал в формате PDF по ссылке выше.

Каждое лето в Крыму в поселке Фрунзенском (это недалеко от всем
известного Артека) работает «Малая академия наук» школьников Крыма.
В числе прочих отделений и секций этой «академии» (у не^ есгь еще и более
короткое название: «Искатель») имеется школа юных кибернетиков.
Работая под руководством сотрудников Симферопольского педагогического
института и его Вычислительного центра *), ребята не только усваивают
необходимый минимум теоретических сведений по математической логике
и теории релейно-контактных схем, составляющий «Азбуку кибернетики»,
но и учатся конструировать простейшие автоматы и на практике осваивают
первые шаги программирования. Правда, они не программируют на электронных
вычислительных машинах, да их и нет в «Искателе». Но не беда —
у юных кибернетиков есть

Вообще-то, надо сказать, это вовсе
никакая не машина. Это,
если угодно, чертеж машины. А еще
правильнее сказать — рассказ о машине.
Но уж если рассказывать, то
рассказывать сначала **).
Тридцать пять лет назад в двух
математических журналах (в издаваемом
в США международном «Журнале
символической логики» и в «Трудах
Лондонского математического общества
») почти одновременно появились
статьи двух выдающихся ученых:
американца Эмиля Л. Поста
и англичанина Алана М. Тьюринга,
*) Школой рукогодит Валентин Николаевич
Касаткин, автор популярных книг
«Азбука кибернетики» и «Секрет кибернетики
». В конце статьи мы приводим несколько
присланных им чадач.
* * ) Данное здесь описание «машины Поста
» принадлежит Ю. А. Гастеву.

посвященные уточнению издавна употребляемого
в математике (да и не
только в математике) понятия алгорифма
(или алгоритма)*). Алгорифм
—это единый общий метод, пригодный
для решения целой серии однотипных
задач. Единый — в том смысле,
что, зная соответствующий алгорифм,
мы можем каждую задачу из
данной серии решить без всяких дополнительных
раздумий, как говорят,
«чисто механически», «формально».
«Формально», «бездумно», «механически
» — в эти слова часто вкладывается
довольно обидный смысл.
И почти всегда напрасно! Посудите
сами: додуматься до способа сложения
любых многозначных чисел «столбиком
» в первый раз было, конечно,
•) Способ написания определяется лишь
традициями и привычкой. Сохранись в
русском языке буква 0 («фита» — то же.
что греческая «тэта»), то и продолжали бы
все писать «алгориОм»!

громадным достижением. Но хороши
бы мы были, если бы каждый раз
заново «изобретали велосипед», придумывая
способ сложения для каждой
пары конкретных чисел! К счастью,
нам не приходится тратить время на
столь нелепое занятие: ведь мы владеем
алгорифмом сложения «столбиком
». И для умножения многозначных
чисел (любых!) мы знаем алгорифм.
И для вычитания. И даже для
деления. А среди наших читателей,
безусловно, найдутся и такие, к го
не забыл алгорифма извлечения квадратного
корня из произвольной десятичной
дроби… Совсем нетрудно овладеть
алгорифмом дифференцирования
функций. За дальнейшими примерами
незачем ходить в «высшую» математику:
алгорифм решения квадратного
уравнения (описываемый обыч-
« , „ — Ե±~է/ Ե* — 4ас \
НОИ формулой X — Կձ————Ь
алгорифм нахождения наибольшего
общего делителя (точнее, не один
алгорифм, а два, очень похожих —
для чисел и для многочленов), различные
алгорифмы решения систем
линейных уравнений, всевозможные
алгорифмы «упрощения формул» в
алгебре и тригонометрии, основанные
на применении «раз навсегда
вызубренных» тождеств вроде
(а+Ь)(с—Ь) —$2—Ь2, sin2x+cos**-= 1
и т. п. Да, можно сказать, вся
математика — даром, что пользуется
репутацией науки «творческой»—
буквально кишит алгорифмами! Ну,
а если вдуматься посерьезней, то
это ведь и понятно: не имей математики
в распоряжении весь этот
алгорифмический арсенал, где бы им
взять время на решение «нестандартных
» задач? (Тем более, что придумывание
нового алгорифма, пока он,
так сказать, не приобрел этого звания,
есть самая что ни на есть нестандартная
и творческая задача.) А
разве вообще в жизни не так: попытайтесь
только представить Моцарта,
каждый раз выясняющего, как
записать на нотной бумаге или «подобрать
» на фортепиано пришедшую
ему в голову музыкальную фразу,
или Пушкина, мучительно вспоминающего,
как пишется слово «любовь»
или, скажем, «свобода»… Потому-то
и возможно творчество этих художников,—
да и любое творчество вообще!
— что процесс писания (и многие
другие не менее полезные процессы,
вроде еды и питья) уже давным-
давно автоматизированы нашей
нервной системой (или алгорифмизи-
рованы,— это, как сами понимаете,
просто синонимы).
Развитие математики в значительной
мере состоит в открытии
алгорифмов для новых классов
задач и в открытии более совершенных
(более быстро приводящих к
цели, более общих или более удобных
в каком-либо другом отношении)
алгорифмов. Первый «род деятельности
» можно сравнить с изобретением
станков и механизмов для обслуживания
новых технологических
процессов (примеры: ткацкий станок,
паровая машина, передача радиоволн),
второй — с модернизацией уже известных
изобретений с учетом новых достижений
науки и техники (замена
металлорежущих станков на электроискровую
обработку металлов,
переход от ковшовых экскаваторов
к роторным или от ламповых
радиоприемников, телевизоров
и вычислительных машин к транзисторным
и- т. п.). Ответ же на общий
вопрос «Что такое алгорифм?»
так же мало нужен математикам, как
инженерам и конструкторам ответ
на вопрос «Что такое машина?» (не
конкретная машина, а любая).
«Мало нужен», — сказали мы. Но
это лишь до известных пор. Оттого,
что вы назовете паровую машину,
двигатель Дизеля, электромотор и домашний
холодильник «преобразователями
энергии», для тех, кто пользуется
этими устройствами или их
совершенствует, мало что изменится.
Но человеку, пытающемуся создать
вечный двигатель, владение таким общим
понятием сэкономило бы немало
времени! Ни Евклиду-, ни безвестным
«изобретателям» сложения,
9

ни даже Гауссу не было нужды в
общем понятии алгорифма. Но понять
— и, тем более, доказать, —
что бывают неразрешимые массовые
проблемы (то есть классы задач, не
допускающие никакого алгоритмического
решения, единого для всего
класса*)), без такого общего определения
уже, конечно, не удастся.
Не менее существенна и чисто
«положительная» ценность общего понятия
алгорифма: понимание общих
закономерностей, которым подчиняются
самые различные алгорифмы,
играет первостепенную роль для «машинной
» математики. Как известно,
универсальная электронная вычислительная
машина «способна воспринять
» программы самых разнообразных
математических (да и далеко не
только математических) задач**). Машинная
же программа это и есть алгорифм,
только вдобавок приспособленный
к особенностям данной конкретной
машины (или записанный на
специальном «языке программирования
», допускающем «трансляцию»,
то есть попросту перевод, на языки
команд разных машин).
У же первые работы Тьюринга и
Поста, посвященные уточнению
понятия алгорифма, давали возможность
существенного продвижения в
обоих указанных направлениях. Непосредственным
побудительным мотивом
к такому уточнению в обоих
случаях послужило желание установить
алгорифмическую неразрешимость
некоторых математических
массовых проблем (и именно Посту
принадлежат первые результаты в
этом направлении). Любопытно, что
оба ученых пошли, по существу, по
одному и тому же пути (вскоре выяснилось,
что этот путь—не единствен*)
Об алгоритмически неразрешимых
проблемах см., например, статью Ф. Л. В а р-
п а х о в с к о г о и А. Н. К о л м о г о р
о в а «О решении десятой проблемы Гильберта
» («Квант», № 7, 1970).
* * ) См., например, статьи P. С, Г у-
т е р а «Что умеют машины» («Квант», Ւ& 5,
1970) и «Язык человека и язык машины»
(«Квант», Nt 10, 1971).
но возможный): вместо интуитивно понятных,
ноабсолютно непригодных для
извлечения точных математических
следствий, разговоров о «едином общем
методе, пригодном для решения целой
серии однотипных задач» (см.
начало этой заметки), Тьюринг и
Пост выдвинули представление об
алгорифме как о некоей абстрактной
(мысленной) «машине», описанной
в точных математических терминах
и в то же время соответствующей
нашим представлениям о вычислительном
процессе, протекающем
по правилам-командам определенного
стандартного вида.
Какое именно определение алгорифма
принимать— Тьюринга, Поста
или принадлежащее кому-либо еще
(наиболее известны определения К- Гёделя,
А. Чёрча, С. К. Клини,
A. А. Маркова, А. Н. Колмогорова)—
несущественно: вскоре выяснилось,
что все эти определения в определенном
смысле эквивалентны. Поэтому
выбор какого-либо одного из этих
уточнений в качестве исходного определяется
не математической стороной
дела, а удобством изложения.
«Машина Тьюринга» описана и в
серьезных, и в популярных книгах *).
«Машине Поста» в этом отношении
повезло меньше, быть может, потому,
что «машина» эта, будучи проще
«машины Тьюринга», именно по
этой причине требует, вообще говоря,
более громоздкой системы команд для
выполнения конкретной задачи. Кроме
единственной статьи самого Поста,
это уточнение понятия алгорифма
описано, по сути дела, лишь в одном
месте: в серии из четырех статей
B. А. У с п е н с к о г о в журнале
«Математика в школе» за 1967 год.
Отсылая читателей к этим очень интересным
(и ясно написанным) статьям,
расскажем теперь о «машине
Поста» лишь самые первоначальные
сведения, необходимые для понимания
дальнейшего.
*) Из их числа в первую очередь рекомендуем
читателю книгу Б. А. Т р а х т е и —
б р о т а «Алгоритмы и машинное решение
задач», Физматгиз, I960, 2-е изд.

10

Итак, идея Поста *) состоит в том,
что любой алгорифм может быть
представлен в виде следующей абстрактной
«машины» **). Машина состоит
из ленты, разделенной на секции
(ячейки); в «абстрактной» машине
Поста эта лента предполагается
б е с к о н е ч н о й , желая же
иметь «действующую модель» машины
Поста, вы можете взять обычную
бумажную ленту для заклеивания
окон, расчертить ее карандашом
на прямоугольные ячейки произвольного
размера и, в случае надобности,
подклеивать к ней новые куски ленты.
В секции может стоять метка
(в этой роли в вашей «модели» с успехом
могут выступать обычные спички,
пуговицы или кнопки) или не
стоять ничего; в первом случае секция
называется отмеченной, во втором
— пустой. В машине есть еще
одна (причем последняя) «деталь»,
называемая кареткой, или считывающей
и записывающей головкой; каретка
движется вдоль ленты, «обозревает
» ячейку, против которой она
находится и, в случае надобности (в
соответствии с очередной командой,
совокупность которых образует программу),
записывает с нее метку или,
наоборот, стирает метку. В вашей
модели функции головки будут разделены:
«считывать» вы, разумеется,
будете просто глазами, в роли записывающего
устройства будет выступать
рука, кладущая и снимающая
спички из ячеек, а чтобы не забыть,
где в данный момент находится ваша
«каретка», кладите что-нибудь против
«обозреваемой» ячейки,— ну, хотя
бы спичечный коробок.
Программа машины Поста (инструкция,
алгорифм, в соответствии с
которым она «работает») состоит, как
уже говорилось, из команд. Команды
бывают следующих шести видов.
*) Именно идея: слова «машина» в изложении
самого Поста нет.
• * ) Поскольку на условность термина
мы уже внимание обратили, в дальнейшем
изложении при слове «машина» мы больше
не будем стаиить кавычек.
I. К о м а н д ы д в и ж е н и я
в п р а в о
а.=ФЬ
(а — это номер данной команды в
программе, то же и в дальнейших
командах; Ь — номер команды, к выполнению
которой следует перейти;
каретку при этом надо сдвинуть на
одну секцию вправо).
II. К о м а н д ы д в и ж е н и я
в л е в о
а.<==Ь
(сдвинуть каретку на одну секцию
влево и перейти к выполнению команды
№ Ь).
III. К о м а н д ы п е ч а т а ния
м е т к и
а. V b
(напечатать метку в обозреваемой секции
и перейти к команде № 6).
IV. К о м а н д ы с т и р а н н я
м е т к и
a. I b
(стереть метку из обозреваемой секции
и перейти к команде № Ь).
V. К о м а н д ы п е р е д а ч и
у п р а в л е н и я
(если обозреваемая секция пуста —
перейти к команде № Ь, если же
обозреваемая секция отмечена — перейти
к команде № с).
VI. К о м а н д а о с т а н о в-
к и
а. стоп
(прекратить выполнение программы).
Если задать некоторую программу
(то есть список из п, п ^ \ , команд,
расположенных в порядке возрастания
номеров от 1 до п, в правые
части которых не входят никакие
натуральные числа, кроме, быть
может, чисел 1,2 п) и определенное
состояние машины (то есть указание,
какие секции отмечены и против
какой секции находится обозревающая
ее каретка), машина начнет
выполнять программу (докажите, что
по меньшей мере один шаг она сделает
в любом случае!), после чего
возможны три исхода:
11

1) машина дойдет до невыполнимой
команды (печатание метки в отмеченной
секции или стирание метки
из пустой секции) — так называемая
безрезультатная остановка;
2) машина дойдет до команды остановки
— результативная остановка;
3) ни один из первых двух случаев
не осуществится — машина будет
работать бесконечно.
П р и м е р 1. В программе
1. =Ф2
շ. 13
3. стоп,
примененной к пустой ленте, безрезультатная
остановка наступит уже
на втором шагу, (так что до предписываемой
третьей командой результативной
остановки дело так и не
дойдет).
П р и м е р 2. Программа
1. =>2
2. =фЗ
3. стоп,
примененная к пустой ленте, будет
выполняться следующим образом: каретка
передвинется на две секции
вправо от обозреваемой, после чего
машина остановится.
П р и м е р 3. Если программу
1. V 2
2. = » 3
3. =փ1
применить к пустой ленте, то машина
будет печатать, начиная с обозреваемой
секции, метки через одну и
никогда не остановится.
Дальнейшие примеры читатель
найдет в уже упомянутых статьях
В. А. Успенского.
Мы же сейчас предоставим слово
участникам школы юных кибернетиков
«Малой академии наук», ученицам
9-го класса Бахчисарайской школы
N° 2 Наташе Кудрявской, Ире Ломакиной
и Светлане Приз, которые расскажут
вам о своем опыте обучения
программированию с помощью машины
Поста (работа которой в сильно
упрощенном виде воспроизводит
работу любой современной универсальной
вычислительной машины). Девочки
испытывали свои программы на
изготовленной сотрудниками Вычи-
12
слительного центра Симферопольского
педагогического института металлической
модели, снабженной клавишами,
тумблерами, штеккерами и прочими
непременными атрибутами «кибернетических
машин». «Лента» в
этой «действующей модели» состоит из
электрических лампочек (40 штук;
выход за пределы ленты квалифицируется
как безрезультатная остановка
машины), причем отмечаемые секции
загораются, а стираемые — гаснут
*).
…^Ч ч ен ь интересно программиро-
^ ✓ э а т ь и видеть, как, подчиняясь
твоей программе, машина решает
задачи. Счетчик команд позволяет
видеть, какая команда выполняется
в данный момент. Программа сначала
записывается на бумаге, а затем
с помощью штеккеров заносится на
наборное поле машины (каждой
команде соответствует свой двоичный
код). Машина работает (в автоматическом
режиме) не очень быстро,
поэтому все е е действия хорошо
наблюдаются; выполнение программы
можно приостановить.
Интересно наблюдать, как машина
выступает соперником человека в
различных играх. Мы решаем задачи
и по составлению программ, пользуясь
которыми машина никогда не
проигрывает **). Вот пример такой
программы. Условия игры: на ленте
стоит подряд 26 меток, самая левая
из которых обозревается кареткой.
Человек и машина ходят по очереди
(начинает игру всегда человек), стирая
за свой ход не более четырех
меток. Тот, кто стирсет последнюю
метку, проигрывает. Если условиться,
*) Мы специально не останавливались
выше на всех этих впечатляющих деталях,
дабы не отвлекать читателя от сути дела;
различие между «электронной моделью машины
Поста» и описанной выше «спичечнобумажной
» примерно того же рода, что различие
между магазинными чеками, отпечатанными
на электрическом или ручном кассовом
аппарате и выписанными от руки.
* * ) То есть всегда выигрывает: все эти
игры таковы, что не допускают ничейного
исхода.

что стираемые человеком метки (одна,
две, три или четыре) — всегда
самые крайние слева, то искомая
программа будет иметь следующий
вид:
j
» \ 1
2. =>3
3. =>4
4. = }5
5. = ,6
6.? / ?
\ 8
7. стоп
8. I 9
9. <=10
10.? ( и
\ 8
11. ==>12
12.? 1
М
Вот краткие пояснения к программе.
1-я команда — передача управления:
машина перейдет ко 2-й
команде только после того как человек
сделает ход. По 2-й, 3-й, 4-й и
5-й командам каретка сдвигается
вправо, а по 8-й команде *) стирает
в обозреваемой секции метку и переходит
к 9-й команде, по которой
она сдвигается влево и переходит к
команде № 10. По этой команде, если
обозреваемая секция пуста, машина
выполняет 11-ю команду, а если
отмечена — 8-ю. По 11-й команде
каретка сдвигается вправо и переходит
к 12-й команде. Если теперь
секция, под которой находится каретка,
пуста, то машина возвращается
к 11-й команде, а если отмечена,
начинает все сначала, то есть переходит
к 1-й команде.

Задачи

1. а) Докажите, что описанная здесь
«машинная стратегия» действительно всегда
обеспечивает выигрыш.
б) Докажите, что та же программа обеспечивает
беспроигрышную игру машины для
случаев, когда на ленте отмечено II или
16 меток; для какого еще числа меток иа ленте
годится та же программа (дайте ответ по
возможности в общем виде)?
2. Дан массив из п меток (то есть п
идущих подряд отмеченных секций). Составьте
программу, расставляющую эти метки на
ленте так, чтобы между каждой парой было
по одной пустой секции (каретка обозревает
крайнюю правую из отмеченных секций).
3. (Эта и следующие две задачи предложены
В. Н Касаткнны.ч.) На ленте имеется
массив из п отмеченных секций (обозревается
крайняя левая из них), а справа
от него, на расстоянии в т секций — еще
одна отмеченная секция. Составьте программу,
придвигающую данный массив к
данной секции.
4. На ленте расположены два массива
разной длины (о&>зревается крайняя секция
одного из них). Составьте программу,
сравнивающую длину массивов и стирающую
Фшьший из них. (Отдельно продумайте случай,
когда длины массивов равны.)
5. На лейте дан массив, крайняя слева
секция которого обозревается кареткой. Составьте
программу, наносящую иа ленту еще
одни массив той же длины, находящийся
через две пустых секции вправо от данного.
в. На ленте даны два массива на
расстоянии одной пустой секции друг от
друга, причем каретка находится под крайней
слева отмеченной секцией левого массива.
Составьте программу, придвигающую
эти массивы друг к другу.
7. Составьте выигрывающую программу
для следующей игры. На ленте машины
Поста отмечена 21 секция, крайняя слева
обозревается. Человек и машина ходят по
очереди (первым ходит человек!), стирая за
ход не более 6 меток. Побеждает (в отличие
от приведенной выше игры) тот, кто стирает
последнюю метку.
*> Назначение 6-н и 7-й команд — остановка
после того, как человек сотрет
последнюю метку

 

#физика #квант

Машина Поста