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

уже были предвосхищены математиками, точнее, математи­ ческими логиками. В 1936 г. А. Тьюринг (Англия) и одно­ временно с ним, хотя и не в столь явной форме, Э. Пост (США) сформулировали понятие абстрактной вычислитель­ ной машины. Машина Тьюринга не стала реально сущест­ вующим, кем-то сделанным устройством, хотя в принципе ее и можно было изготовить, например, как механическое устройство; технический прогресс привел к другому пути воплощения принципов конструирования больших (так на­ зываемых универсальных) вычислительных машин. Тем не менее умозрительные конструкции Тьюринга — Поста ос­ таются ярчайшими образцами научного предвидения; ведь именно на абстрактных математических моделях было стро­ го доказано существование универсальных вычислительных машин (см. § 14). Более того, и по сей день в теории алгоритмов машина Тьюринга постоянно используется в качестве основной модели для выяснения сущности таких понятий, как «вычислительный процесс», «алгоритм», а так­ же для выяснения связи между алгоритмами и вычисли­ тельными машинами*'.

Вторая часть данной книги (§ 7—13) посвящена деталь­ ному изучению тыорпнговых машин и реализации алго­ ритмов в них. Значительное место занимают здесь методы тьюрингова программирования, полезные также и для по­ нимания проблем программирования для реальных вычис­ лительных машин, включая проблему автоматизации прог­ раммирования (см. § 10, «Программирующие алгоритмы»). Хотя возможны и другие абстрактные модели вычисли­ тельных машин, отличные от машины Тьюринга, тем не ме­ нее все они равносильны друг другу (а значит, и тыоринговой модели) в следующем смысле: класс проблем, которые можно решать на моделях одного типа, в точности совпадает с классом проблем, которые можно решать на моделях

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

8

другого типа, в частности, на машинах Тьюринга. Именно благодаря этому в математических терминах приобретают свой точный смысл и решаются два принципиальных воп­ роса, которые кратко можно сформулировать так: что мо­ гут делать машины? Как они это делают?

Третья часть книги (§ 14—23) содержит.материал, из которого можно почерпнуть определенные ответы на эти вопросы.

Первый вопрос направлен на выяснение того, какие ви­ ды умственной работы могут выполнять автоматические вычислительные машины. Его актуальность и острота свя­ заны, в частности, с тем, что достигнутые успехи могут породить и действительно порождают фантастические прог­ нозы и несбыточные иллюзии по поводу всемогущества ма­ шин (гигантских электронных мозгов!). Анализ процессов, протекающих в соответствии с заданными алгоритмами, н в том числе процессов, протекающих в автоматических вычислительных машинах, привел к замечательным отк­ рытиям. Было строго доказано существование таких типов задач, для которых невозможен единый эффективный ме­ тод — алгоритм, — решающий все задачи данного типа; в этом смысле невозможно и машинное решение задач такого типа. С тех пор одной из главных целей теории алгоритмов (и математики в целом) является исследование отдельных типов задач, возникающих в различных областях матема­ тики с целью выяснить, возможен ли для них разрешающий алгоритм. В этом направлении имеются очень крупные достижения, способствующие лучшему пониманию того, что могут делать машины и чего они не могут делать. К ним относятся, в частности, сравнительно просто формули­ руемые результаты А. А. Маркова и П. С. Новикова, которые излагаются в § 4, 15, 16.

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

9

Ч А С Т Ь I А л г о р и т м ы

§1. ЧИСЛЕННЫЕ АЛГОРИТМЫ

1.1.Арифметические действия; алгоритм Евклида. Как уже говорилось во введении, простейшими алгоритмами являются правила, по которым выполняются арифметиче­ ские действия по десятичной системе счисления. Например,

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

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

11

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

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

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

У к а з а н и е 4. Если первое обозреваемое число меньше второго обозреваемого числа, переставьте их мес­ тами и продолжайте обозревать их. Переходите к следую­

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

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

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

12