Akademik

        в математике и логике, подход в основаниях этих наук, при котором их сфера ограничивается конструктивными объектами и такими рассуждениями об этих объектах, в которых не присутствует идея актуальной бесконечности. Конструктивными наз. объекты, являющиеся либо элементарными знаковыми образованиями (т. е. не построенными из др. знаков), относительно которых предполагается, что они однозначно опознаваемы — различаемы и отождествляемы, как, напр., буквы некоторого алфавита (см. Абстракция отождествления), либо сложными (но обязательно конечными) знаковыми конструкциями, возникающими в результате к.-л. конструктивного процесса. Последний представляет собой основанный в конечном счёте на оперировании с элементарными конструктивными объектами и протекающий по чётким правилам дискретный (по шагам) процесс построения новых конструктивных объектов [примерами объектов, возникающих в конструктивных процессах, являются слова (формулы) в к.-л. алфавите, конечные таблицы и графы, деревья логич. выводов]. Конструктивные процессы задаются либо исчислениями как системами порождающих правил, либо алгоритмами. К. н. в применении к таким процессам допускает абстракцию потенциальной осуществимости (позволяющую, напр., рассуждать о формулах с любым конечным числом знаков, о сколь угодно сложных формальных логич. выводах), но не абстракцию актуальной бесконечности. Это приводит к финитной установке (см. Финитизм), состоящей в отказе от рассмотрения «завершённых» бесконечностей типа множеств всех натуральных, всех действит. чисел, всех формул к.-л. логич. исчисления. В логич. плане подобная установка влечёт отказ от применения исключённого третьего принципа к бесконечным совокупностям объектов, а также отказ от правила снятия двойного отрицания (позволяющего умозаключать от опровержения допущения о несуществовании некоторого объекта к утверждению о его существовании). Эти черты К. н. определяют его отличие от подходов классич. (теоретико-множественной) математики и классич. логики, сближая его с математикой и логикой, реализуемой в системах «искусств. интеллекта».

        Конструктивные процессы и соответств. им конструктивистские тенденции неотделимы от истории математики и дедуктивной логики, однако как самостоят. подход К. н. начинает складываться в первые десятилетия 20 в. в связи с концепцией формализма Гильберта и появлением интуиционизма (с которым его сближает ряд общих черт). Чёткий вид К. н. приобрело после возникновения совр. теории эффективной вычислимости (теории алгоритмов) в 30-х гг. Начиная с 40-х гг. в СССР сложилась оригинальная форма К. и., созданная А. А. Марковым и развитая его учениками (Н. А. Шанин и др.).

        см. также Конструктивная логика.

        M a p к о в А. А., Теория алгоритмов, М.— Л., 1954 (Тр. Математич. института АН СССР, т. 42); его ж е, О логике конструктивной математики, М., 1972; Шанин ?. ?., Ветуп. ст., в кн.: Гудстейн Р. Л., Рекурсивный математич. анализ, М., 1970, с. 7—76.

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

Один из простейших типов конструктивных объектов образуют слова в определ. фиксированном а л ф а в и т е. Слово в данном алфавите есть ряд букв этого алфавита. Напр., (1): παπαγιγλημμα есть слово в греч. алфавите. Здесь элементарными конструктивными объектами являются буквы данного алфавита, а способ их сочленения – это написание рядом друг с другом. Натуральные числа можно рассматривать как слова в алфавите, единств. буквой к-рого является |. В частности, единица рассматривается как слово |, два – как слово ||, три – как слово |||. При рассмотрении слов появляется понятие о д и н а к о в о с т и. Напр., слово (1) мы считаем одинаковым со словом (2) παπαγιγλημμα. Естеств. образом здесь применяется а б с т р а к ц и я отождествления: мы отождествляем одинаковые слова (1) и (2), отвлекаемся от имеющихся различий между ними, говорим, что это одно и то же слово.

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

Характерное различие между этими двумя направлениями связано с предложениями о существовании. Конструктивисты и "классики" по-разному понимают самый термин "существование" в связи с объектами математики и логики. В "классической" математике и логике доказываются многочисленные "чистые теоремы существования", состоящие в утверждениях о существовании объектов с такими-то свойствами, при полном игнорировании способов построения таких объектов. К. н. отвергает такого рода предложения. Так, конструктивное понимание параметрич. предложений о существовании, т.е. предложений о существовании, содержащих параметры, могущие принимать различные значения, состоит в их трактовке как предложений о возможности построения алгорифмов, перерабатывающих любое допустимое значение параметров в объект, существование которого утверждается. Например, конструктивный смысл теоремы Эвклида: "для всякого натурального числа х существует простое число у, большее х" (где х играет роль параметра) усматривается в том, что имеется алгорифм, к-рый дает возможность, исходя из произвольного натурального числа х, получить простое число у, большее х – алгорифм, "перерабатывающий" любое натуральное число х в простое число у, большее х.

Конструктивному пониманию существования объекта соответствует конструктивное понимание дизъюнкций – предложений вида "Р или Q". Такое предложение тогда считается установленным, когда хотя бы одно из предложений Р, Q установлено как верное. Это понимание дизъюнкции не дает оснований считать верным закон исключенного третьего: "Р или не верно, что Р". Т.о., К. н. требует своей конструктивной логики, в нек-рых важных пунктах отличной от классической.

Оформление и развитие К. н. имело место на основе осуществленного в 30-х гг. 20 в. уточнения понятия алгорифма (см. Алгоритм), освободившего это понятие от расплывчатости и субъективизма. Это было сделано в работах неск. авторов, шедших разными путями: Чёрча, Клини, Тьюринга, Поста. Теории, построенные этими авторами, – теория рекурсивных функций Клини, исчисления λ-конверсии Чёрча, теория машин Тьюринга, теория финитных комбинаторных процессов Поста – оказались эквивалентными друг другу и привели по существу к одному и тому же уточнению понятия алгорифма. Новые уточнения этого понятия, также эквивалентные прежним, были построены рядом др. авторов. В наст. время продолжают публиковаться все новые и новые теории алгорифмов, эквивалентные прежним теориям. Для целей К. н. оказалась удобной теория "нормальных" алгорифмов.

Н о р м а л ь н ы е а л г о р и ф м ы строятся по следующему плану. Фиксируется нек-рый алфавит А. Из его букв и нек-рых вспомогат. знаков строится стандартного вида "схема" будущего алгорифма. Алгорифм формулируется затем как нек-рое стандартного вида предписание, определяемое схемой. Оно определяет процесс последоват. преобразования слова в алфавите А. В качестве исходного слова при этом может быть взято любое слово P в алфавите А. Процесс, порождаемый данным алгорифмом, состоит из последоват. дискретных шагов, на каждом из к-рых получается нек-рое слово в алфавите А. Алгорифм определяет также окончание процесса, к-рое может и никогда не наступать. Если окончание наступает, то мы говорим, что данный алгорифм п р и м е н и м к с л о в у Р, и называем слово Q, получаемое на последнем шаге, р е з у л ь т а т о м применения алгорифма к слову Р. Мы говорим тогда, что данный а л г о р и ф м перерабатывает слово P в слово Q и выражаем это равенством U (Р) = Q, где U – знак рассматриваемого алгорифма. Нормальный алгорифм определяется своим алфавитом и своей схемой. Схема нормального алгорифма может быть закодирована словом в двубуквенном алфавите. Это слово называется з а п и с ь ю данного алгорифма.

Теория нормальных алгорифмов строится в рамках абстракции потенциальной осуществимости. Слова в рассматриваемом алфавите А, схемы нормальных алгорифмов в А – все это потенциально осуществимые конструктивные объекты. Сам процесс применения нормального алгорифма к данному слову рассматривается как потенциально осуществимый процесс. Для того чтобы удостовериться в применимости алгорифма U к слову Р, не обязательно, чтобы процесс применения U к P был выполнен перед нашими глазами от начала до конца. Как же можно удостовериться в этом? Сов. конструктивисты А. А. Марков и Н. А. Шанин считают здесь возможным применять рассуждение "от противного", т.е. утверждать, что а л г о р и ф м U применим к слову Р, если предположение о неограниченной продолжаемости процесса приме-нения U к P опровергнуто приведением к нелепости. Они мотивируют это тем, что никакого выхода за рамки К. н. при этом не происходит: абстракция актуальной бесконечности не привлекается, существование продолжает совпадать с потенциальной осуществимостью построения. Если на основании доказанной невозможности неогранич. продолжаемости детерминированного процесса утверждается, что этот процесс закончится, то при этом дается совершенно определенный способ построения: продолжать процесс до его завершения. То обстоятельство, что при этом число шагов может не быть "заранее" ограниченным, ничего здесь по существу не меняет. К тому же требование, чтобы это число было заранее ограниченным, едва ли может быть точно и объективно формулировано.

Рассмотренный способ доказательства применимости алгорифма дает возможность обосновать следующий способ рассуждения. Пусть для свойства b; имеется алгорифм, выясняющий для всякого натурального числа n, обладает ли n свойством b;. Если опровергнуто предположение о том, что ни одно число не обладает свойством n, то имеется натуральное число со свойством b;. Найти это натуральное число можно тогда путем перебора натуральных чисел, начиная с нуля, причем для каждого рассматриваемого натурального числа n мы выясняем, пользуясь алгорифмом, наличие к-рого предполагается, обладает ли n свойством b;. В силу этого данный способ рассуждения наз. методом конструктивного п о д б о р а.

Использование точного понятия алгорифма дает возможность развивать конструктивную математику и конструктивную математич. логику как науки. В частности, в настоящее время строятся конструктивный математич. анализ (важные результаты здесь получены А. А. Марковым, Н. А. Шаниным, Г. С. Цейтиным, И. Д. Заславским и др. сов. учеными), во многих отношениях непохожий на классический. Есть основания думать, что К. н. в математике будет удовлетворять запросам, предъявляемым математике со стороны др. наук.

К. н. имеет точки соприкосновения с т. н. интуиционистской математикой (см. Интуиционизм). Конструктивисты сходятся с интуиционистами в трактовке предложений о существовании натурального числа с данным свойством как констатации наличия метода построения числа с этим свойством. Конструктивисты сходятся с интуиционистами в понимании дизъюнкций и в силу этого признают правильной данную Брауэром критику закона исключенного третьего. Вместе с тем конструктивисты считают неприемлемыми методологич. основы интуиционизма.

Интуиционисты не признают человеч. практику источником формирования математич. понятий, методов математич. построении и методов умозаключений. Единств. источником математики они считают первоначальную "интуицию", а критерием истинности в математике – "интуитивную ясность". В основу своей теории действит. чисел интуиционисты кладут идею "свободно становящейся последовательности", к-рую они считают интуитивно ясной, но к-рая для многих др. математиков совсем не ясна. Эта идея во всяком случае несовместима с осн. требованием К. н., состоящим в том, что лишь конструктивные объекты допускаются в качестве объектов исследования.

Лит.: Марков Α. Α., Теория алгорифмов, Тр. Матем. ин-та, т. 38, М., 1951, с. 176–89; его же, Теория алгорифмов, там же, т. 42, М., 1954; Цейтин Г. С., Алгорифмич. операторы в конструктивных метрич. пространствах, там же, т. 67, М.–Л., 1962; Заславский И. Д., Некоторые свойства конструктивных чисел и конструктивных функций, там же; Шанин Η. Α., О конструктивном понимании математических суждений, там же, т. 52, М.–Л., 1958; его же, Конструктивные веществ. числа и конструктивные функциональные пространства, там же, т. 67, М.–Л., 1962; Specker E., Nicht konstruktiv beweisbare Sätze der Analysis, "J. Symbolic Logic", 1949, v. 14, No 3.

    КОНСТРУКТИВНОЕ НАПРАВЛЕНИЕ (в математике и логике) — одно из направлений в основаниях математики, в рамках которого исследования ограничиваются конструктивными процессами и конструктивными объектами. Конструктивное направление имеет точки соприкосновения с интуиционистской математикой (см. Интуиционизм). Конструктивисты сходятся с интуиционистами в трактовке предложений о существовании и в понимании дизъюнкции и в силу этого признают правильной данную Брауэром критику закона исключенного третьего. Вместе с тем конструктивисты считают неприемлемыми методологические основы интуиционизма. В основу своей теории действительных чисел интуиционисты кладут идею свободно становящейся последовательности, которую они считают интуитивно ясной, но которая для многих других математиков совсем не ясна. Эта идея, во всяком случае, несовместима с основным требованием конструктивного направления, состоящим в том, что лишь конструктивные объекты допускаются в качестве объектов исследования. Один из простейших (но достаточный для развития конструктивной математики) типов конструктивных объектов образуют слова (ряд букв) в некотором фиксированном алфавите. Естественным образом здесь применяется абстракция отождествления. При рассмотрении слов в данном алфавите возникает потребность в абстракции и другого типа — в абстракции потенциальной осуществимости. Она состоит в отвлечении от практических границ наших возможностей в пространстве, времени и материале при построении слов. Напр., мы отвлекаемся от практической невозможности написать на данной доске данным мелом сколь угодно длинные слова и начинаем рассуждать так, как если бы это было возможно. Мы утверждаем, в частности, что к любому слову в данном алфавите можно приписать справа любое другое слово в этом алфавите. Рассматривая натуральные числа как слова в однобуквенном алфавите |, мы утверждаем, что любые два натуральных числа можно сложить. Это, однако, вовсе не означает, что мы начинаем рассматривать “натуральный ряд” как некоторый бесконечный объект. Такое рассмотрение было бы связано с абстракцией актуальной бесконечности, выходящей за рамки конструктивного направления и характерной для классической математики и логики. Здесь мы имеем водораздел, отделяющий конструктивное направление от классического.

    Характерное различие между этими двумя направлениями связано с предложениями о существовании. Конструктивисты и классики по-разному понимают самый термин “существование” в связи с объектами математики и логики. В классичес

    кой математике и логике доказываются многочисленные чистые теоремы существования, состоящие в утверждениях о существовании объектов с такими-то свойствами при полном игнорировании способов построения таких объектов. Конструктивисты отвергают такого рода предложения. Конструктивное понимание параметрических предложений о существовании (содержащих параметры, могущие принимать разные значения) предполагает их трактовку как предложений о возможности существования алгоритмов, перерабатывающих любое допустимое значение параметров в объект, существование которого утверждается. Напр., конструктивный смысл теоремы Евклида: “для всякого натурального числа существует простое число у, большее х” (где χ играет роль параметра) усматривается в том, что имеется алгоритм, который дает возможность, исходя из произвольного натурального числа х, получить простое число у, большее — алгоритм, перерабатывающий любое натуральное число х в простое число у, большее х

    Конструктивному пониманию существования соответствует конструктивное понимание дизъюнкций — предложений вида “Р или β”. Такое предложение тогда считается установленным, когда хотя бы одно из предложений установлено как верное. Это понимание дизъюнкции не дает основания считать верным исключенного третьего закон. Т. о., конструктивное направление требует своей конструктивной логики, в некоторых важных аспектах отличной от классической.

    Оформление и развитие конструктивного направления имело место на основе осуществленного в 30-х гг. 20 в. уточнения понятия алгоритма. Слова в рассматриваемом алфавите, записи (программы) алгоритмов — все это потенциально осуществимые конструктивные объекты. Сам процесс применения алгоритма к данному слову рассматривается как потенциально осуществимый процесс. Для того, чтобы удостовериться в применимости алгоритма А к слову Р, не обязательно, чтобы процесс применения А к Р был выполнен перед нашими глазами от начала до конца. Здесь возможно применить рассуждение от противного: алгоритм А применим к слову Р, если предположение о неограниченной продолжаемости процесса применения А к Р опровергается приведением к нелепости. Данный способ рассуждения назвали принципом Маркова.

    Использование точного понятия алгоритма дало возможность развивать конструктивную математику и конструктивную математическую логику как науки. Н. А. Шанин построил алгоритм конструктивной расшифровки, выделяющий из любой математической формулы явное построение конструктивного объекта и условие, которое необходимо доказать для корректности данного построения. Он заметил, что для обоснования уже сделанного построения можно, в предположении принципа Маркова, использовать классическую логику. Т. о., при конструктивном понимании формула содержит две задачи: задачу на построение и задачу на доказательство. Если первая из них практически с неизбежностью требует перехода к неклассической логике, то вторая зачастую может быть решена традиционными средствами. Это разделение двух типов задач явилось важным методологическим следствием, достичь которого помог принцип Маркова, поскольку без него такого простого алгоритма расшифровки и простой характеризации задач на доказательство достичь не удается.

    Вместе с тем Б. А. Кушнер выяснил, что из чисто математических результатов от принципа Маркова зависит лишь теорема Г. С. Цейтина о непрерывности конструктивных функций действительного переменного. Но как раз она явилась самым важным результатом конструктивного анализа. Ее доказательство в корне отлично от соответствующей теоремы интуиционистского анализа, поскольку опирается не на ограниченность доступной конечной информации о бесконечных объектах, а на сложность полной информации об алгоритмах, которыми располагает конструктивная функция. Свойства конструктивных функций оказались резко отличными от классических.

    Еще более жесткий вариант конструктивного подхода предложил Р. Л. Гудстейн. Он использовал лишь такие алгоритмы, которые по своему определению заведомо заканчивают работу, и лишь такие свойства их, которые выражаются в виде V x^...x,^f(x):=g(x). Т.о., он изгнал не только неконструктивные объекты, но и идеальные суждения (см. Фтитизм). Даже столь простые утверждения, как существование предела вычислимой последовательности, пришлось приближать более простой последовательностью. В дальнейшем подобным путем пошел Н. А. Шанин, создав теорию приближений идеальных высказываний непосредственно конструктивно интерпретируемых. Порою такие приближения (трансфинитные развертки, по Шанину) позволяют выявить глубоко скрытый конструктивный смысл классических чистых теорем существования.

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

    П. Мартин-Лёф создал оппортунистическую систему, воспользовавшись наблюдением Клини, что фиксация алгоритмических функций еще не означает фиксации алгоритмов преобразования функций. Объекты нижнего уровня у него алгоритмы, а высших — строятся по Бишопу. Конструктивная математика, по Мартин-Лёфу, изложена столь же строго, как и российская, но включила многие преимущества до сих пор не формализованного изложения Бишопа. Свойства функций, по Бишопу и Мартин-Лёфу, оказались значительно ближе к классическим, расходясь с ними лишь в тех случаях, когда классические теоремы существования не дают и не могут дать никакого алгоритмического построения. Доказательства теорем у них, как правило, короче и прозрачнее, чем в трудах российской школы. Таких преимуществ они достигли за счет более смелого использования идеальных понятий.

    Лит.: Марков А. А. Теория алгорифмов. — Труды Математического института, т. 42. M., 1954; Шанин H. A. 0 конструктивном понимании математических суждений. — Там же, т. 52. M.—Л., 1958; Гудстейн Р. Л. Рекурсивный математический анализ. М., 1970; Кушнер Б. А. Лекции по конструктивному математическому анализу. М., 1973; МартинЛёф П. Очерки по конструктивной математике. М., 1975; Марков А. А., Нагорный Н. М. Теория алгорифмов. М., 1984; Bishop E. Foundations of constructive analysis. N.Y, 1967; Η. Η. Непейвода