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

Светлой памяти

Эта книга, являющаяся введением в теорию алгоритмов, посвящена разъяснению одного из самых' основных поня­ тий математики — цонятия алгоритма; в ней рассматрива­ ется круг вопросов, лежащих на грани между математи­

Книга состоит из трех почти равных по объему частей. Первая часть, «Алгоритмы» (§ 1—6), еще не относится к тео­ рии алгоритмов, хотя в ней сплошь и рядом идет речь об ал­ горитмах. Дело в том, что здесь слово «алгоритм» понима­ ется в интуитивном смысле; теория же начинается лишь там, где термин обозначает уже точно определяемое мате­ матическое понятие. Тем не менее материал этой части, но­ сящий подготовительный характер, весьма важен и полезен для понимания содержательных стимулов в пользу теории.

Вторая часть, «Машины Тьюринга» (§ 7—13), вводит уже непосредственно в круг основных понятий теории ал­ горитмов.

Третья часть, «Алгоритмические проблемы» (§ 14—23), является кульминационной. В ней излагается ряд фунда­ ментальных результатов теории, которые, к счастью, под­

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

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

3

В результате этого появилась статья «Алгоритмы и ма­ шинное решение задач» («Математика в школе», 1956, № 4— 5); ее расширенные варианты были изданы дважды (Гос-

Параграфы 1—9 и 13—16 настоящей книги целиком включают содержание упомянутых выше публикаций, ко­ торые подверглись тщательному просмотру и переработке.

Кроме того, книга содержит довольно обширный новый материал, а именно § 10—12 и § 17—24, в основу которых легли лекции, прочитанные автором студентам отделения математической лингвистики и слушателям факультета повышения квалификации Новосибирского университета. Этот материал представляет, как нам кажется, большой интерес для понимания таких разделов теории алгорит­ мов, которые уже не связаны непосредственно с явлением алгоритмической неразрешимости. Здесь имеются в виду главным образом следующие три проблемы: програм\щрсь-__ вание (§ 10—12), качество aлjroгJит^ю_в_($ 17—20)""й~автома-

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

этой книги.

Его моральная поддержка и постоянное внимание име­

ческой кибернетики. Автор рассматривает эту книгу как скромную дань памяти Алексея Андреевича.

Новосибирск, Академгородок, ноябрь, 1973 г.

Б. Трахтенброт

ВВЕДЕНИЕ

Понятие алгоритма • принадлежит к числу основных понятий математики. Под алгоритмом понимают точное предписание о выполнений в определенном порядке некото­ рой системы операций для решения всех задач некоторого данного типа.

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

Простейшими алгоритмами являются правила, по кото­ рым выполняется то или иное из четырех арифметических действий в десятичной системе счисления. Термин «алго­ ритм» происходит от имени средневекового узбекского ма­ тематика Аль-Хорезми, который еще в IX веке предложил такие правила. В математике серия задач определенного типа считается решенной, когда для ее решения установлен алгоритм. Например, в алгебре установлены алгоритмы, которые по заданным коэффициентам алгебраического урав­ нения позволяют совершенно автоматически определить, сколько различных корней (и какой кратности) имеет дан­ ное уравнение, и вычислить эти корни с любой наперед заданной точностью*'. Нахождение алгоритмов является естественной целью математики.

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

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

5

их обработка и составление материальных балансов для получения оптимальных результатов складываются из длин­ ной цепи элементарных операций нескольких типов, кото­ рые осуществляются в строгом соответствии со специаль­ ными инструкциями и схемами. Список таких примеров можно было бы продолжить. В § 1—4 этой книги на ряде примеров разъясняется, что такое алгоритм, и строятся алгоритмы для решения некоторых классов математиче­ ских и логических задач.

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

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

6

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

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

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

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

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

7

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

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

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

8

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

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

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

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

9