Конструктивная математика Маркова и Бишопа

Сейчас, когда гигантская работа, проделанная и самим Кантором, и рядом других работавших вслед за ним выдающихся математических мыслителей, таких как Л. Э. Брауэр, Д. Гильберт и А. А. Марков, отошла в прошлое и результаты ее стали всеобщим достоянием, нам все более естественной начинает казаться та — теперь уже действительно простая — мысль, что подобно всякому другому сложно устроенному «творению ума и рук человеческих», математика — для целесообразного, правильного и естественного ее функционирования — должна быть разумно, по детально продуманному плану «возведена» на достаточно прочном «фундаменте» с использованием надлежаще подобранного «строительного материала».

Н. Нагорный ^1,2

Классические математики считают базисным для построения всей математики понятие множества. Интуиционисты — понятие свободно становящейся последовательности. В 40-е гг. XX в. возникло новое направление в обосновании математики, которое признало понятие свободно становящейся последовательности туманным, основанным на субъективистски истолковываемом понятии интуиции, и заменило его понятием алгорифма. Это направление конструктивной математики возглавил отечественный ученый — А. А. Марков (1903;1979). На становление конструктивизма Маркова определенное влияние оказала работа А. Н. Колмогорова, посвященная переинтерпретации интуиционистской логики как исчисления задач (проблем)^[1][2]. Колмогоров показал, что каждая задача, выводимая из интуиционистского исчисления высказываний, имеет решение. Значит, интуиционистское исчисление задач можно было интерпретировать как исчисление разрешимых проблем.

Конструктивная математика Маркова представляет «ветвь интуиционистской математики, для которой характерно исследование конструктивных объектов алгорифмическими методами»" ⁴. Понятия конструктивного объекта и алгорифма являются в этом определении решающими.

Конструктивный объект — результат осуществления конструктивного процесса. Простым примером конструктивного процесса является «построение ряда вертикальных черточек.

путем писания одной такой черточки, приписывания к ней справа ее копии — другой черточки, приписывания к полученным черточкам еще одной черточки, затем еще одной черточки, затем еще одной и еще одной"" ⁵. Результатом конструктивного процесса является конструктивный объект, изображенный пятью строками выше.

Под алфавитом в конструктивной математике Маркова понимается любой конечный набор четко отличимых друг от друга графических символов (букв), а под словом в данном алфавите — произвольная конечная цепочка букв этого алфавита, включая пустое слово (не содержащее ни одного знака и эквивалентное операции стирания знака). Более точно, конструктивными математическими объектами называются слова в алфавите А, удовлетворяющие следующим порождающим правилам" ⁶:

• (а) если а — буква алфавита А, то а представляет собой слово в алфавите А;
• (б) если Р — слово в алфавите, А и, а — буква алфавита А, то результат приписывания буквы а справа к слову Р является словом в алфавите А;
• (в) пустое слово Л является словом в алфавите А.

Каждое слово — результат некоторого построения, к которому может быть применено новое построение, а к полученному ре-^[3][4][5]

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

Понятие алгорифма (такой транскрипцией слова «алгоритм» Марков отделял свою теорию от других теорий алгоритмов) представляет дальнейшее уточнение понятия эффективного метода, вычислимой (рекурсивной) функции. Алгорифм создается для решения какого-нибудь класса однотипных задач (проблем). Абстракция потенциальной осуществимости — идейная основа теории алгорифмов. «Осуществляя конструктивные процессы, мы часто наталкиваемся на препятствия, связанные с нехваткой времени, места и материала… Тем не менее мы в дальнейшем не будем считаться с этими препятствиями в наших рассуждениях о конструктивных объектах. Мы будем рассуждать так, как если бы этих препятствий не существовало, т. е. как если бы в каждый момент в нашем распоряжении были и пространство, и время, и материал, потребные для осуществления очередного шага рассматриваемого конструктивного процесса. Поступая так, мы будем отвлекаться от ограниченности наших возможностей в пространстве, времени и материале. Это отвлечение принято называть абстракцией потенциальной осуществимости"'¹⁷. Теория алгорифмов Маркова — модель математики, реализующей данную абстракцию.

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

Алгорифмы должны соответствовать следующим общим критериям. Во-первых, они обязаны быть определенными, т. е. точными и понятными для всех людей или автоматов, которые их^[6][7]

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

Всякий алгорифм строится по определенной схеме, состоящей из детерминированной последовательности дискретных (прерывистых) шагов, называемых подстановками, на каждом из которых получается новое слово в алфавите А: Р -> Q> Р2 -> Qi, где Р_и, Qi — слова, построенные из букв алфавита А. Допустим, дана подстановка СМ —> ГР. Если эту подстановку применить к слову СМОГ', возникнет слово ГРОГ. Иными словами, алгорифм — это предписание, позволяющее осуществить детерминированный процесс переработки слов.

Каждая формула в конструктивной математике Маркова символизируется в виде упорядоченной пары (U, V) слов в алфавите А. Слово U называется левой частью этой формулы, а V — ее правой частью. Среди формул некоторые выделяются в качестве заключительных. В схеме алгорифма заключительная формула записывается в виде U —? • К, а промежуточная — в виде U —> V. Когда процесс заканчивается, то это называется применением данного алгорифма к слову U, взятому за исходное. Результатом применения алгорифма к слову U является слово Q, которое получается на последнем шаге начатого нами процесса.

Алгорифм называется нормальным, если он представляет стандартное предписание, задаваемое схемой подстановок и определяющее процесс последовательного (шаг за шагом) преобразования одного конструктивного объекта в другой конструктивный объект. Формально нормальный алгорифм Е задается тремя объектами: алфавитом А, схемой Z, состоящей из некоторого множества формул подстановок, и технического трехбуквенного алфавита не входящего в алфавит, А (и выполняющего функцию «знаков препинания» для отделения друг от друга формул подстановок; знак у отделяет друг от друга формулы подстановок, знаки а и Р — левые части формул от правых, указывая одновременно на тип формулы подстановки: а у простых формул, р — у заключительных). Применить нормальный алгорифм? к слову Р означает применить к Р схему алгорифма Z.

Например, схема.

в алфавите abc состоит из четырех формул подстановок которые могут быть также представлены следующим образом:

Нормальный алгорифм? представляет предписание по построению, начиная с произвольного слова Р в алфавите А, последовательности слов Pj согласно следующему правилу. Выберем слово Р в качестве первого члена Р₀. Пусть для некоторого i > 0 слово P_t построено, и процесс построения нужной последовательности слов еще не завершился. Если в схеме нормального алгорифма? нет формул, левые части которых входили бы в Р" то P_i+1 полагают равным Р^ и процесс построения последовательности на этом заканчивается. Если же в схеме? имеются формулы с левыми частями, входящими в P_ti то в качестве Р,₊₎ берется результат подстановки правой части первой из таких формул вместо первого вхождения ее левой части в слово Р,; при этом процесс построения последовательности считается завершившимся, если примененная на этом шаге формула подстановки была заключительной, и продолжающимся в противном случае. Если процесс построения упомянутой последовательности обрывается, то говорят, что рассматриваемый нормальный алгорифм? применим к слову Р. Последний член Q этой последовательности считается результатом применения нормального алгорифма? к слову Р и обозначается символом ?(Р). При этом говорят, что? перерабатывает Р в Q, и пишут ?(Р) = Q.

Очевидно, что если принимается абстракция потенциальной осуществимости, то процесс построения может продолжаться сколь угодно долго. И относительно его результата всегда можно с уверенностью сказать: процесс завершен (нужный объект построен) или процесс не завершен (нужный объект еще не построен). Для тех случаев, когда процесс построения не может быть завершен в конечное время, конструктивисты принимают следующее допущение (принцип Маркова)" ⁹:

Если предложение о неограниченной продолжаемости процесса применения алгорифма 1 к слову Р опровергнуто приведением к нелепости, то Г применим к Р.

Иными словами, если процесс применения алгорифма к некоторому слову не является безгранично применимым, то алгорифм применим к этому слову. Откуда следует, что данный объект является конструктивным. Принцип Маркова радикально отличает конструктивную логику от интуиционистской, так как вводит косвенный способ доказательства утверждения существования. Это не соответствует канонам интуиционистской логики, в которой позволяется доказывать косвенным способом только отрицания суждений существования. Оправдывая данный принцип, Марков и Нагорный пишут: «Мы не видим разумных оснований отвергать этот способ рассуждения, так как никакого выхода за рамки конструктивного направления при этом не происходит: абстракция актуальной бесконечности не применяется, существование продолжает пониматься как потенциальная осуществимость построения. Если мы утверждаем на основании доказанной невозможности неограниченной продолжаемости детерминированного процесса, что этот процесс закончится, то при этом дается совершенно определенный способ построения: продолжать процесс до его завершения. То обстоятельство, что при этом число шагов процесса может не быть ‘заранее' ограниченным, ничего здесь по существу не меняет. К тому же требование, чтобы это число было заранее ограниченным, едва ли может быть точно и объективно сформулировано»^[8][9].

Марков формулирует принцип нормализации, связывающий теорию нормальных алгорифмов с известными результатами Гёделя^[10], Клини^[11], Поста^[12], Тьюринга^[13] и Чёрча^[14]. Алгорифм, применяемый к словам и называемый вербальным, обладает большей степенью общности, чем нормальный алгорифм. Встает вопрос: всякий ли вербальный алгоритм нормализуем, т. е. выразим в виде нормального алгорифма? Утвердительный ответ на этот вопрос дает принцип нормализации^[15]:

Всякий вербальный алгорифм в алфавите, А вполне эквивалентен относительно, А некоторому нормальному алгорифму над, А (всякий вербальный алгорифм нормализуем).

Марков и Нагорный отмечают, что принцип нормализации «представляет собой вариант тезиса Чёрча, относящийся к нормальным алгорифмам»^[16]. Тезис Чёрча относится к так называемым арифметическим функциям, для вычисления значений которых имеются какие-либо алгоритмы и которые принято называть вычислимыми. Буквально он гласит: «…Для каждой функции положительных чисел, которая эффективно вычислима в только что определенном смысле (т. е. является рекурсивной функцией. — В. С), существует алгоритм вычисления ее значений. Обратно, при этом же определении эффективной вычислимости верно, что каждая функция, алгоритм вычисления значений которой известен, эффективно вычислима»^[17].

Значение принципа нормализации состоит в следующем. После того как в 30-е гг. XX в. было разработано множество специальных видов алгоритмов, «для каждого из этих видов возникла увсрснность в том, что он с точностью до эквивалентности исчерпывает все алгорифмы. Иначе говоря, математики прониклись убеждением в том, что всякий алгорифм эквивалентен некоторому алгорифму данного вида. Эта идея стандартизации алгорифмов лежит в основе их современной теории. Вскоре после того, как были выработаны первые стандартные понятия алгорифма, удалось установить, что все предложенные стандартизации в определенном точном смысле слова равносильны друг другу, и когда в дальнейшем были предложены некоторые новые стандартизации, они также оказались равносильными ранее определенным. Поэтому при построении общей теории алгорифмов в конечном счете оказывается безразличным, какой именно их стандартизацией пользоваться. Мы будем использовать наиболее привычные нам ‘нормальные алгорифмы'»^[18].

Слова в заданном алфавите определяются как возможные результаты осуществления процессов построения. Поэтому суждение классической математики вида «Существует слово, удовлетворяющее условию ф» признается конструктивистом неточным и заменяется следующим конструктивным суждением: «Потенциально осуществимо построение слова, удовлетворяющего условию ф» или «Слово, удовлетворяющее условию ф, является конструктивным математическим объектом».

Различие между классическим и конструктивистским суждениями существования состоит в том, что из доказательства «классического» суждения существования не всегда следует истинность «конструктивного»: первое может быть истинным, но второе тем не менее ложным.

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

В целом к конструктивному направлению в математике относятся все исследования, удовлетворяющие следующим условиям:

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

Пусть приписывание вертикальной «черточки» справа от данного натурального числа обозначает новое натуральное число, отличающееся от него на единицу. Тогда алфавита, А = {0, |} достаточно для порождения ряда натуральных чисел согласно следующим правилам:

• • 0 есть натуральное число.
• • Если п — натуральное число, слово п | также есть натуральное число.

Согласно указанному алгорифму, для получения нового натурального числа достаточно приписать справа к данному вертикальную черточку. Таким образом, натуральными числами являются слова 0 (ноль), 0 | (единица), 0 11 (два), 0 111 (три),…

Для определения рациональных чисел алфавит, А = {0, |} достаточно расширить, включив в него дополнительные слова (косая черта отделяет числитель от знаменателя, знак «-» обозначает «минус»): А = {0, |, /, -}:

Для определения действительных чисел строится алгоритмическая интерпретация критерия сходимости Коши, с помощью которого Кантор строил теоретико-множественное определение действительных чисел. Согласно Кантору, всякая последовательность рациональных чисел, выполняющая критерий сходимости Коши, определяет некоторое действительное число.

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

Нормальный алгорифм Е в расширенном алфавите называется конструктивной последовательностью рациональных чисел, если он применим ко всякому натуральному числу и перерабатывает его в некоторое рациональное число. Число E (JV), где N— произвольное натуральное число, называется N-м членом последовательности Е.

Пусть Е — конструктивная последовательность рациональных чисел. Конструктивная последовательность натуральных чисел 0 называется регулятором сходимости последовательности Е, если для любых натуральных чисел L, М и N из М, N > 0(Г) следует, что

Конструктивное действительное число есть всякое слово вида Е0, где Е — конструктивная последовательность рациональных чисел, О — се регулятор сходимости^[19].

Таким образом, для построения действительного числа требуется два алгорифма. Первый — для задания последовательности рациональных чисел Е (Л/), второй — для доказательства возможности построения числа 0(N) по данному натуральному числу L.

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

некоторого конкретного нормального алгорифма I в, А проблема распознавания применимости (неприменимости) к словам в, А неразрешима: искомый в этой проблеме нормальный алгорифм невозможен.

Результат Маркова соответствует аналогичным отрицательным доказательствам А. Тьюринга и А. Чёрча, полученным ранее (в 1936 г.).

Некоторые пояснения к основной теореме Маркова дают следующие определения и результаты.

• ? Множество М слов в алфавите, А называется разрешимым в А, если существует нормальный алгорифм? над А, проверяющий принадлежность слов в, А к М.
• ? Множество М слов в алфавите, А называется перечислимым, если существует алгорифм? над, А такой, что для любого слова Р в, А ?(Р) определено тогда и только тогда, когда Ре М.
• ? Всякое разрешимое множество слов является перечислимым.
• ? Существует перечислимое, но не разрешимое множество слов в алфавите.

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

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

Вместе с этими результатами стало ясно видно, что «никакого упрощения теории не получается. Наоборот, исследование конструктивных аналогов даже весьма элементарных теорий обычного анализа потребовало больших усилий и редкой изобретательности. Что же касается отделов анализа, касающихся наиболее абстрактных свойств банаховых, гильбертовых и топологических пространств, то тут зачастую не удается построить конструктивных аналогов по причинам больших технических трудностей. Короче говоря, конструктивный анализ как по требуемому для его осмысления умственному напряжению, так и по громоздкости применяемого аппарата оказывается не более простым предметом, чем классический анализ, а, пожалуй, даже более сложным…»^[20].

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

Новая версия конструктивизма, независимая от интуиционизма Брауэра, конструктивизма Маркова, призванная спасти классическую математику, связана с именем американского математика Эррета Бишопа (1928;1983)^[21]. В первой главе своего монументального труда «Конструктивный анализ», названной «Конструктивистским манифестом», Бишоп формулирует основные положения нового видения математики в послебрауэровскую и послегильбертовскую эпоху^[22].

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

Первичный объект математики — натуральное число. Мы постигаем число тем же способом, каким, согласно Канту, воспринимается пространство. Существование натуральных чисел вместе с арифметикой обусловлено природой нашего интеллекта и, возможно, разума как такового. Теория натуральных чисел создается из понятий единицы, добавления единицы и принципа полной индукции. Все остальные «этажи» математики строятся посредством последовательного восхождения от базисной теории натуральных чисел. Таким способом создается большая часть математики.

Но существует и другой способ «трансцендснции математики». Можно восходить от фактически сконструированного объекта к новому, гипотетическому по своей сути. Так, можно вводить гипотетические множества с гипотетическими операциями на них, выполняющие определенные аксиомы. Оправданием такого способа построения математики становится возможность решения конкретных математических проблем, выраженных в терминах натуральных чисел. Гипотетические объекты можно строить на основании других гипотетических объектов, т. е. возможна иерархия гипотетических конструкций. Какой бы высоты ни было все здание, его основанием служит натуральный ряд чисел. Значит, любая математическая проблема при таком построении получает надежный вычислительный базис.

На 70-е гг. прошлого столетия пришлась новая волна интереса к конструктивной математике. Возник своеобразный ренессанс конструктивизма. «Существуют две принципиальные причины этого ренессанса: Бишоп и компьютер. В 60-е гг. компьютер использовался для численного решения определенных математических проблем, самой поразительной из которых можно назвать расчет орбит для космических кораблей. Это вызвало значительный прогресс в развитии методов численного анализа и численной алгебры, были построены необходимые алгорифмы и исследовано их применение. Распространение этих методов и алгорифмов на другие области и проблемы породило неожиданный интерес к тому способу решения математической проблемы, который связан с ее вычислением. Неизбежным результатом всего этого стало переосмысление проблемы, относительно которой спорили Брауэр и Гильберт. Оно было предпринято Эрретом Бишопом из Калифорнии… Главным поражающим открытием Бишопа стало доказательство, что как Гильберт, так и Брауэр ошибались как раз в том пункте, относительно которого у них не было разногласий. А именно, они оба предполагали, что если принять конструктивную (интуиционистскую. — В. С.) математику серьезно, то необходимо будет ‘отказаться' от самых важных частей современной математики (таких, например, как теория меры или комплексный анализ). Бишоп доказал, что это было обычным заблуждением и что не было никакой необходимости вводить экстравагантные допущения, кажущиеся противоречивыми всем непосвященным. Длившийся долгое время конфликт между мощью и безопасностью математического мышления был на самом деле иллюзорным!.. Бишоп нашел способ представить математику как ‘язык высокого уровня программирования', в котором следует записывать доказательства. Каждое доказательство существования должно сопровождаться построением алгорифма»^[23].

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

• [1] Нагорный Н. Вместо предисловия ко второму изданию // Марков А. А., Нагорный Н. М. Теория алгорифмов. М., 1996.
• [2] 1,3 Колмогоров А. Н. О принципе tertium non datur // Математический сборник. 1925. Т. 32. № 4. С. 646−667.
• [3] ' Драгалин А. Г. Конструктивная модель интуиционистского анализа // Философия и логика. М., 1974. С. 59.
• [4] Марков А. А., Нагорный И. М. Указ. соч. С. 1.
• [5] ' Там же. С. 5.
• [6] Марков А. А., Нагорный Н. М. Указ. соч. С. 10−11.
• [7] Там же. С. 109.
• [8] Марков А. А., Нагорный Н. М. Указ. соч. С. 420−421.
• [9] Там же. С. 421.
• [10] Godel К. On Formally Undecidable Propositions of Principia Mathematica andRelated Systems I I Collected Works. Vol. 1. Oxford, 1986. P. 145−195 (текст статьиприводится параллельно на немецком и английском языках).
• [11] Kleene S. С. General Recursive Functions on Natural Numbers // The Undecidable. Basic Papers on Undecidable Propositions, Unsolvable Problems and ComputableFunctions. N. Y., 1965. P. 237−252.
• [12] Post E. L. Finite Combinatory Processes // The Undecidable. N. Y., 1965.P.289−291.
• [13] Turing A. On Computable Numbers, with an Application to the Entscheidungs-problem // The Undecidable. N. Y., 1965. P. 116−151.
• [14] Church A. An Unsolvable Problem of Elementary Number Theory // The Undecidable. N. Y., 1965. P. 89−107.
• [15] Марков А. А., Нагорный //. M. Указ. соч. С. 115.
• [16] Там же. С. 117.
• [17] Church A. Op. cit.P. 100.
• [18] Марков А. А., Нагорный Н. М. Указ. соч. С. 116−117.
• [19] Марков А. А., Нагорный И. М. Указ. соч. С. 404.
• [20] Тростников В. Н. Конструктивные процессы в математике (философскийаспект). М" 1975. С. 177.
• [21] См.: Bishop Е., Bridges D. Constructive Analysis. N. Y., 1985. (Второе переработанное издание. Первое опубликовано в 1967 г.); Beeson М. Foundations ofConstructive Mathematics. N. Y., 1985.
• [22] Ibid. P.4−13.
• [23] Beeson М. Foundations of Constructive Mathematics. P. XV.