книги из ГПНТБ / Кушнер, Б. А. Лекции по конструктивному математическому анализу

22 ВВЕДЕНИЕ

(источником такого рода конструкций может служить построенный К л и н и [2] пример бесконечного дерева с конечным ветвлением, все общерекурсивные пути ко­

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

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

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

вая относящаяся сюда статья Гудстейна, сданная в пе­ чать в 1941 г., увидела свет в 1945 г.; исследования Гудстейна собраны в двух его монографиях [1] и [2], объединенных в русском переводе в одну книгу). Харак­ терной чертой подхода Гудстейна является стремление

курсивной арифметики или, точнее, на основе разрабо­ танной им оригинальной аксиоматической теории не­ которых классов арифметических функций (исчисление равенств Гудстейна; за подробной общей характеристи­ кой как исчисления равенств, так и подхода Гудстейна вообще мы отсылаем читателя к статье Ш а н и н а [8]). Объектом рассмотрения являются рекурсивные (чаще всего примитивно рекурсивные) функции над полем рациональных чисел с рациональными значениями, а также рекурсивные последовательности таких функций, задаваемые двухместными рекурсивными функциями. При построении анализа последовательно используются аппроксимативные методы, причем объекты, обычно воз­ никающие в анализе из аппроксимаций в результате предельных переходов, как правило, не вводятся. На­ пример, у Гудстейна фактически отсутствует понятие рекурсивной действительной функции, хотя читатель, владеющий какой-нибудь концепцией действительной функции, без труда обнаружит приводящие к таким функциям последовательности рациональных приближе­ ний. Достоинством этой методики является логическая простота используемых понятий, вместе с тем она не ли­ шена, по мнению автора, и некоторых недостатков — по мере накопления никак не обозначенных предельных переходов растет громоздкость (но не сложность!) определений и формулировок теорем. В целом анализ приобретает очень необычный вид, что существенно за­ трудняет математику, интересующемуся кругом проблем

24 ВВЕДЕНИЕ

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

доклада Бишопа на Московском международном кон­ грессе математиков). Конструктивный анализ Бишопа занимает промежуточное положение между интуицио­ нистским анализом и системами, использующими точ­

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

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

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

и в рамках систем анализа, опирающихся на точное понятие алгорифма.

Излагаемая в данной книге система конструктивного анализа принадлежит к так называемому конструктив­ ному направлению в математике, главные положения которого были выдвинуты в 1948—1949 гг. А. А. Мар­ ковым. Формирование основных понятий этой системы относится к 50-м годам; в это же время были получены и наиболее принципиальные, определившие современное лицо теории, результаты. Здесь следует прежде всего указать на основополагающий вклад самого А. А. Мар­ кова, а также его учеников Н. А. Шанина, И. Д. За­ славского и Г. С. Цейтина. Краткая характеристика конструктивного направления и строящегося в его рам­ ках конструктивного анализа приводится в следующих пунктах. Ниже прилагательное «конструктивный» будет (за исключением особо оговоренных случаев) упот­

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

26 ВВЕДЕНИЕ

«конструктивный анализ» закрепляется за излагаемой нами системой.

Заканчивая наш краткий обзор, отметим, что с рас­ смотренных позиций исследовались (в особенности в последние годы) и достаточно далекие области матема­ тики. В этой связи, помимо монографии Бишопа и

рии меры и интеграла Лебега, посвященный этой же

численные работы принадлежат конструктивному на­

[1]), выяснилась возможность плодотворного применения теории рекурсивных функций для обоснования теории информации и теории вероятностей.

3. Конструктивное направление в математике может быть охарактеризовано следующими основными чертами

I . В качестве объектов изучения выступают кон­ структивные объекты, при обращении с которыми до­ пускается абстракция потенциальной осуществимости, но полностью исключается абстракция актуальной бес­ конечности.

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

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

В целом конструктивная математика использует го­ раздо более «скромную» систему абстракций, нежели

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

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

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

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

том или ином алфавите. Понятие слова в данном ал­

тельным выписыванием прямолинейных цепочках букв

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

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

стр. 15]). Относительно используемых алфавитов пред­ полагается также, что они обеспечивают однозначность чтения слов: каждое слово в данном алфавите един­ ственным образом составлено из его букв. Эта одно­ значность позволяет естественным образом говорить об одинаковости слов. Два слова в данном алфавите оди­ наковы (графически равны), если они составлены из одних и тех же букв, расположенных в одинаковом по­ рядке. Процесс опознавания графического равенства сводится к одновременному последовательному «чте­ нию» обоих испытуемых слов и сравнению одновремен­ но появляющихся в поле зрения букв. При неблагопри­ ятном исходе этого процесса испытуемые слова счи­ таются (графически) различными.

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

знаковых комплексов словами можно указать на опре­ деления изображения и записи нормального алгорифма (см. п. 8 § 1 гл. 1). При такого рода кодировании обыч­ ным является использование вспомогательных «разде­ лительных» букв, не входящих в алфавиты исходных знаковых комплексов. Например, произвольная матрица

может быть закодирована следующим образом. Выбе­

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

в А, называется а-системой (а-кортежем, а-вектором)

{0|}; дополнение этого алфавита буквами «—» и «/» по­

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

в) направленность алгорифма на получение некото­ рого искомого результата, в конце концов и получаемого при надлежащих исходных данных, — результативность алгорифма».

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

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

того или иного точного определения являются и алго­

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

алгорифма понятие нормального алгорифма, предло­

женное А. А. М а р к о в ы м [1]—[2] и специально при­ способленное для оперирования со словами. Следует отметить, что получаемые результаты, по существу, не зависят от принятия или непринятия принципа норма­ лизации. Все построения в конечном счете могут быть