Файл: Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы.pdf

Очевидно, графически различных (т. е. различных по своему начертанию) слов в алфавите {а, Ь, с) существует бесчисленное множество; однако графически различные сло­ ва могут изображать одно и то же самосовмещение из 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