книги из ГПНТБ / Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы

первых, заметим, что если дана дедуктивная цепочка, ве­ дущая от какого-либо слова R, не содержащего буквы Ь, к слову 5, также не содержащему этой буквы, то можно из нее извлечь дедуктивную цепочку, ведущую от R к S, но такую, что в промежуточных словах цепочки не встречается буква Ь. Действительно, если во всех словах данной дедуктивной цепочки заменить каждое вхождение буквы b словом асе, то получится последовательность слов, в которой каждые два рядом стоящие слова являются смеж­ ными (в смысле исчисления) или просто одинаковыми. Если удалить теперь лишние повторяющиеся слова (из рядом стоящих), то получится нужная дедуктивная цепочка. В де­ дуктивных цепочках этого типа совсем не участвует подста­ новка b — асе.

Далее, в каждой из оставшихся допустимых подстано­ вок число вхождений буквы а в левой части и число вхожде­ ний в правой части либо одновременно четны, либо одновре­ менно нечетны. Аналогичное утверждение справедливо и для буквы- с. Значит, четность числа вхождений буквы а (или буквы с) является дедуктивным инвариантом для де­ дуктивных цепочек вышеуказанного вида. Отсюда сразу вы­ текает, что ни одно из четырех приведенных слов, содер­ жащих по одному вхождению буквы а, не эквивалент­ но ни одному из четырех приведенных слов, не содержащих вовсе таких вхождений. Точно так же ни одно из приведен­ ных слов, содержащих одно или три вхождения буквы с, не эквивалентно какому-либо слову, содержащему два та­ ких вхождения или не содержащему ни одного вхождения. Поэтому остается еще убедиться в неэквивалентности сле­ дующих пар слов: Д, сс; с, есс,; а, асе; ас, асес.

Если бы имела место эквивалентность хотя бы одной из

40

называется число всех вхождений буквы с, встречающихся правее этого вхождения буквы а. Индексом слова R называет­ ся сумма индексов всех вхождений буквы а*'. Каждая из подстановок аа— Д и сссс— Д не меняет четности индекса слова. Действительно, при подстановке аа вместо пустого слова индекс слова увеличивается на сумму равных между собой индексов этих двух вхождений буквы а, т. е. на чет­ ное число; при замене же вхождения аа пустым словом ин­ декс слова уменьшается на четное число.

При подстановке сссо индексы некоторых вхождений а увеличиваются на четыре, индексы других не изменяются; в целом индекс слова увеличивается на четное число. Ана­ логично при зачеркивании сссс. Подстановка Ь — асе оче­ видным образом не меняет четности индекса слова.

Наконец, покажем, что подстановка са — ассс изменяет четность индекса слова. Для этого сравним слова PcaQ и PacccQ; индекс каждого вхождения а в часть Р слова R из­ меняется ровно на 2, а индекс вхождения а. в Q не из­ меняется. Чго же касается индекса единственного вхожде­ ния а между Р и Q, то он изменяется в точности на 3. В це­ лом индекс слова изменяется на нечетное число. Оба слова ас и ассс имеют индексы одной и той же четности; поэтому, если они эквивалентны, то в соответствующей дедуктивной цепочке (можно считать, что в ней буква Ь не встречается, см. выше) может быть лишь четное число подстановок са — ассс.

Однако такое предположение приводит к противоре­ чию, как видно из следующих рассуждений. Каждое при­ менение подстановки са — ассс меняет число вхождений бук­ вы с на 2, поэтому четное число ее применений меняет чис­ ло вхождений буквы с на число, кратное четырем. Очевидно,

числа. Подведя итог всему сказанному, мы должны заклю­ чить, что если ас ~ ассс, то количества вхождений буквы с в них отличаются на число, кратное четырем, чего на самом

*) Например, в слове acbca первое слева вхождение буквы о имеет индекс 2; второе же слева вхождение буквы а имеет индекс О (правее нет вхождений буквы с). Индекс слова — 2.

41

деле Нет. Итак, слова ас и йссс неэквивалентны. Вместе с тем мы завершили обоснование предложенного алгоритма.

4.5. Самосовмещения квадрата. Приведенное в примере 4 подробное решение проблемы слов для конкретного ассо­ циативного исчисления во многом характеризует понятия и методы, возникающие и при исследовании проблемы слов для других исчислений. Нам остается еще пояснить содер­ жательный смысл проблемы слов и ее значение в современ­ ной алгебре. Это удобно сделать не конкретном примере.

Вертикальная ось

Левая диагональ

Горизонтальная ось

Правая диагональ

Л

Я Сг

Рис. 9.

Возьмем какой-нибудь квадрат (рис. 9, I). Рассмотрим следующие три его самосовмещения, т. е. преобразования, которые переводят квадрат в самого себя:

1)симметрия (зеркальное отображение) относительно вертикальной оси, проходящей через центр квадрата О;

2)симметрия относительно горизонтальной оси, про­ ходящей через центр квадрата О;

3)вращение по часовой стрелке на 90° вокруг центра О. Эти преобразования будем называть элементарными и

обозначать буквами а, Ь, с соответственно. На рис. 9 ( I I I — IV—V) показано, как изменяется расположение вершин квадрата (II) при каждом из элементарных преобразований.

42

Заметим, что в результате последовательного осуществле­ ния каких бы то ни было двух или нескольких самосовме­ щений квадрата происходит также самосовмещение квадра­ та. Будем придерживаться общепринятого определения, со­ гласно которому умножить два заданных преобразования (в частности, два самосовмещения квадрата), — значит последовательно произвести их одно за другим. Условимся еще для операции умножения преобразований сохранить обычные обозначения, а также термин произведение для ре­ зультирующего преобразования. Например, произведение

ссесть результат двух последовательных вращений по 90°,

т.е. вращение на 180°; произведение, ас — результат сим­ метрии относительной вертикальной оси с последующим поворотом на 90° — равносильно симметрии относительно левой диагонали. Произведение же (ас) [сс) двух предыдущих произведений равносильно симметрии относительно правой диагонали (см. рис. 9, I).

пример, (ас) (сс) и (((ас)с)с) дают одно и то же самосовмеще­ ние квадрата—симметрию относительно левой диагонали.

Объектом наших последующих рассмотрений будет со­ вокупность Q, состоящая из элементарных преобразований а, Ь, с и всех самосовмещений квадрата, которые могут быть представлены как произведения конечного (но произвольного) числа элементарных преобразований. Бла­ годаря ассоциативности умножения при символической записи элементов из Q, можно опустить скобки и ограничить­ ся записью в соответствующем порядке букв, изобра­ жающих соответствующие элементарные самосовмещения, например abb, cabb, ассс и т. д. Это означает, что всякое про­ изведение изобразится в виде слова в алфавите {а, Ь, с).

Из ассоциативности умножения вытекает также, что если к слову Р приписать справа слово Q так, чтобы полу­ чилось одно слово PQ, то оно будет изображать произведе­ ние самосовмещений, изображенных словами Р и Q соот­ ветственно; например, слово abccab изображает произведе­ ние совмещений, изображаемых словами abc и cab.

43

Очевидно, графически различных (т. е. различных по своему начертанию) слов в алфавите {а, Ь, с) существует бесчисленное множество; однако графически различные сло­ ва могут изображать одно и то же самосовмещение из Q. В этом случае естественно слова считать равными и обозна­ чать такое равенство обычным образом. Читатель легко проверит справедливость равенств

Для этого достаточно сравнить расположения вершин квадрата, которые возникают в результате преобразова­ ний из левой и правой частей этих равенств. Далее легко видеть, что каждое из слов аа, bb, сссс задает одно и то же самосовмещение, а именно так называемое тождественное преобразование, при котором все вершины остаются на прежних местах. Поскольку это преобразование ничего не меняет, целесообразно его изображать также пустым сло­ вом Л - Итак, имеют место и равенства

новками ассоциативного исчисления примера 4 подсказы­ вает следующее предложение, устанавливающее связь меж­ ду этим исчислением и рассматриваемой системой преобра­

каждом применении любой допустимой подстановки к лю­ бому слову S оно переходит в равное слово. Например, при­ меняя подстановку са — асес к слову Ьсас, получаем слово Ьасссс; но ведь в силу ассоциативности умножения мы можем писать: Ьсас = Ь(са) с и Ьасссс = Ь(ассс)с; правые части рав­ ны как произведения соответственно равных множителей, значит, и левые равны между собой. Итак, любые два смеж­ ных слова равны.

Теперь уже легко понять, что эквивалентность двух слов в нашем ассоциативном исчислении влечет за собой их

44

равенство (т. е. одинаковость самосовмещений, задаваемых

то они эквивалентны. Действительно, если два слова равны,

им соответствует одно и то же приведенное слово, а зна­ чит, по ранее доказанному они эквивалентны.

Таким образом, формальная эквивалентность двух слов в нашем исчислении получает конкретный геометрический смысл и распознавание эквивалентности двух слов приобре­ тает значение решения конкретной геометрической задачи. Вместе с тем описанный нами алгоритм предстает перед на­ ми как общий метод решения любой геометрической задачи данного типа.

толкование. Без преувеличения можно сказать, что во вся­ кой области математики имеются теоремы, которые могут быть сформулированы после некоторой обработки в вид-,е утверждений об эквивалентности двух слов в некотором ис­ числении. В этой книге нет возможности разобрать этот круг вопросов; некоторые пояснения будут даны еще по хо­ ду дальнейшего изложения (см. п. 7.2).

Заметим еще, что, исходя из того геометрического истол­ кования, которое мы дали проблеме слов в рассмотренном исчислении, можно теперь построить алгоритм непосред­ ственно и даже несколько проще. Именно, достаточно для каждого из двух предлагаемых произведений фактически

циативного исчисления, заданного в алфавите {а, Ь} с до­ пустимыми подстановками:

ааа = bb, bbbb = Л-

45

взятых в указанном порядке, понимаем слово, которое получается,

гут содержать и коэффициенты, которыми являются слова в алфа­ вите (а, Ь). Например, выражение xbabay = uyba является уравне­ нием в словах, в котором наряду с неизвестными х, у, и встречаются коэффициенты baba (в левой части), Ьа (в правой части). Одно из воз­ можных решений:

х = ab, у = baba, и = abba.

Далее, под системой уравнений в словах будем понимать систему,

алгоритм, который для любой системы уравнений в словах позволяет выяснить, имеет ли она решение.

§5. ВЫЧИСЛИТЕЛЬНАЯ МАШИНА

САВТОМАТИЧЕСКИМ УПРАВЛЕНИЕМ

5.1.Человек-вычислитель. Наша ближайшая цель со­

стоит в том, чтобы выяснить основные принципы устройства и работы автоматических вычислительных машин. Для это­ го мы предварительно еще раз обратимся к рассмотрению алгоритмического процесса, осуществляемого человеком (вычислителем).

Руководствуясь алгоритмом, человек-вычислитель совершает процесс, в котором происходит прием, хранение,

46

переработка и выдача некоторых сведений (некоторой ин­ формации). Обычно эти сведения вычислитель записывает (изображает) на бумаге с помощью цифр, букв или других символов. Совокупность всех этих символов принято назы­ вать алфавитом. Например, в алгебре применяется алфавит, в который входят, кроме обычных букв, цифры, знаки алгебраических операций, скобки и т. д.

Для вычислительного процесса, происходящего с уча­ стием человека-вычислителя, характерно наличие следую­ щих трех факторов (см. схему на рис. 10, а):

при этом к сведениям относят также инструкцию (схему алгоритма) для решения задачи. Заметим, что фактически вычислитель не записывает буквально все иа бумаге; кое-что он просто запоминает (хранит не на листе бумаги, а в памяти), а некоторые сведения черпает из разных спра­ вочников и таблиц. Однако эти обстоятельства не должны

средств, которые обеспечивают хранение всех необходимых сведений. Таким образом, п о д л и с т о м б у м а г и в нашей схеме следует понимать совокупность всех средств,

способность вычислителя выполнять отдельные элементар­ ные операции, предусмотренные в алгоритме, и может осу-

47

ществляться вычислителем посредством специализирован­ ных механизмов, например арифметические операции над числами могут быть реализованы на арифмометре. Каж­ дая отдельная операция заключается в том, что вычисли­ телем в соответствии с инструкцией извлекаются некоторые сведения (например, числа) из определенных граф листа бумаги, они подаются на обрабатывающее устройство (ариф­ мометр), а результат обработки помещается в определенное

или иной операции и создание условий для ее выполнения, осуществляется самим вычислителем согласно инструкции.

5.2. Вычислительные машины. Из каких устройств со­ ставлена машина и как они взаимодействуют между собой? Ответ на этот вопрос подсказывается тем, что в ней должны происходить те же процессы, какие были только что описа­ ны, но уже без участия вычислителя.

Во-первых, для изображения информации машина также должна иметь определенный алфавит; однако вместо обыч­ ного графического изображения символов, различаемых друг от друга по их начертанию, в машине различные сим­ волы алфавита изображаются некоторыми отличными друг от друга физическими состояниями, например различными электрическими напряжениями или различными состояния­ ми намагничивания.

Целый ряд соображений оправдывает преимущественное применение алфавита из двух символов (двоичного алфавита), условно называемых 0 и 1. Так, например, этот алфавит проще всего осуществляется физически в электрических цепях в виде двух состояний: высокое напряжение (или — ток идет) и низкое напряжение (или—ток не идет). Далее приходится считаться и с тем, что простейшие логические операции совершаются над переменными, могущими прини­ мать два значения: «истинно» и «ложно». Однако выбор того или иного алфавита и способ изображения в нем нужных сведений далеко не является решающим для понимания

преимущественно двоичным алфавитом и двоичной системой счисления (вместо употребительной десятичной), мы в даль­ нейшем не будем вдаваться в эти детали.

Итак, информация, которая поступает в машину, а также та, которая вырабатывается в ней в процессе ее работы, изо-

бражена в виде некоторых физических параметров. В инте­ ресующих нас случаях все сведения, составляющие инфор­ мацию, будут зашифрованы числами. В частности, в виде набора чисел будет зашифрован и сам алгоритм, которым должна «руководствоваться» машина в своей работе. Алгоритмы, составленные специально для машин, называют

сируются все нужные сведения, включая программу. Воз­ можность физического осуществления органа, выполня­ ющего такие функции, вряд ли вызовет у кого-либо сомне­ ние. Действительно, эту функцию может выполнять магнит­ ная лента, на которой кодированные, сведения фиксируют­ ся и с которой они снимаются примерно так же, как на обыч­ ном магнитофоне. Запоминающее устройство {память ма­ шины) состоит из набора ячеек, занумерованных натураль­ ными числами: 1,2,3 ... Эти числа называются адресами ячеек. Каждая ячейка хранит или может принять на хра­ нение одно закодированное сообщение; в вычислительных машинах каждое такое сообщение представлено, как мы уже отметили, в виде некоторого числа.

Практически в электронных машинах кроме магнитной ленты применяются и другие средства «запоминания»,

аименно электронно-лучевые трубки, принцип работы ко­ торых несколько напоминает работу телевизионных трубок,

атакже магнитный барабан, причем функции запоминания разделены между этими органами целесообразным способом. Однако мы не будем различать отдельных составных час­ тей памяти и без ущерба для понимания дела будем исходить из представления об едином запоминающем устройстве, хо­ тя бы в виде магнитной ленты.

2. А р и ф м е т и ч е с к и й б л о к играет ту же роль, что и обычный арифмометр, хотя физические принци­ пы, лежащие в основе его конструкции, сильно отличают­ ся от тех, которые использованы в обычном арифмометре.

преобразования в электронном устройстве входных элек­ трических сигналов, изображающих входные данные, в элек-

49