markov_teorija_algorifmov (Марков - Теория алгоритмов), страница 4

Принцип этот, впервые отмеченный и обоснованный А. А. Марковым (см. например, 17!), специфичен для его конструктивизма. В оценке допустимости этого принципа между представителями различных направлений в основаниях математики имеются определенные расхождения. Поэтому мы помещаем его в книге там, где он впервые фактически потребовался (предшествующее изложение, таким образом, от этого принципа не зависит). Отдельные замечания и комментарии 5 37.5, $ 47.2, $ 54.1.

3', $ 56.2.5', $ 64.1, $64.5 — 64.7 и др.), по своему характеру относящиеся к проблемам логики и оснований математики, включены мною в текст основного материала. Особо следует сказать о теоретико-множественных комментариях в тексте книги Я 49 и далее), которые я ввел в изложение под личную ответственность, понимая их полезность для определенной категории читателей, Позиция А. А. Маркова состояла в последовательном неупотреблении теоретико-множественных представлений, и, вероятно, он не согласился бы с введением этих комментариев, чтобы у читателя не возникло мысли о их существенности.

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

Внимательный читатель У Й б Р ') Параграфы 1 и 4 — 16 в основном следуют тексту брошюры Л.д.й1аркова 141. ПРЕДИСЛОВИЯ !6 ПРЕДИСЛОВИЯ «и т. дль столь характерных для математической литературы. С другой стороны, обращает на себя внимание наличие большого количества индуктивных определений и доказательств по индукции. Такой характер изложения был запланирован А, А.Марковым с целью подчеркнуть особую роль метода индукции в элементарной семиотике. Последовательно проводя этот замысел в жизнь, я счел правильным и целесообразным распространить его и на самые первоначальные понятия семиотики — на понятие слова, на отношения графического равенства и различия, а также на операцию соединения слов.

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

Кроме того, при таком подходе становится особенно естественной семантическая мотивация принципа индукции. Роль индукции хорошо также видна в доказательствах правильности работы ряда приведенных в книге конкретных нормальных алгорифмов (см. 8 28 — 34). Эти доказательства проведены с большой степенью детализации. Но считать их чрезмерно подробными было бы поверхностным: суть их не только в том, чтобы убедить читателя (который сам по себе может оказаться склонным к торопливости и доверчивости), а еще и в том, чтобы провести, как теперь говорят, «вернфикациюэ по определенным правилам — фактически в виде вывода в рамках некоторого исчисления.

При минимальных навыках такие выводы могут быть получены на основе наших доказательств без особых усилий. В монографии [2) из-за наличия переменных индексов и многоточий ситуация менее прозрачна, но, несомненно, идея верификации присутствует уже и в ней, так что эта монография может, по-видимому, считаться первой в литературе работой, где проблема верификации разрабатывается хотя и в частном случае, но отчетливо и в достаточно подробном виде, Особенно поучительными с точки зрения проблемы верификации в нашей книге представляются Я 31 и 32.

Приведенные в них доказательства правильности работы удваивающего и обращающего нормальных алгорифмов, стилистически по сравнению с монографией [2) болеевыдержанные, демонстрируют, в частности, любопытную специфику применения метода индукции (см. замечание в конце и. 2 $ 31). Что касается изменений в техническом аппарате общей теории нормальных алгорифмов, то для данной книги написаны новые доказательства теорем о разветвлении (3 39) и о повторении ($40).

Теорема о приведении (й 41.7.1) и ее усиление (З 41.8.1) доказаны для отношения сильной эквивалентности алгорифмов, которое в монографии [2) не рассматривалось. Заново, с учетом достижений Д. А. Остроухова и В. Г. Жарова, написана глава об универсальном алгорифме. Здесь мне существенную помощь оказал мой ученик Виктор Гаврилович Жаров, которому я считаю своим приятным долгом выразить мою признательность. Несколько расширен мною раздел, касающийся принципа нормализации. Материал, отвечающий гл. «' монографии [2), пополнен мною Я 49 — 50 и 52 — 55. Внесенные добавления содержат ряд комментариев и необходимых дополнений к тем основным теоремам о невозможности алгорифмов, которые в свое время были изложены в гл. Ъ' монографии [2).

Гл. 1Х посвящена рассмотрению ряда вопросов конструктивного анализа, интенсивное развитие которого А. А. Марков предсказывал еще в периодсоздания монографии[2). Это предсказание, как мы теперь знаем, впоследствии полностью оправдалось. К сожалению, за недостатком места изложение в этой главе мне пришлось сделать несколько фрагментарным и гораздо более беглым, чем в остальных. По той же причине сжат почти до минимума материал гл. Ч! монографии [2). Я довел изложение лишь до примера ассоциативного исчисления с неразрешимой проблемой эквивалентности пустому слову н добавил к нему разработанный А. А, Марковым метод зычислимых инвариантов.

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

Чебышева,— доказательство неразрешимости проблемы гомеоморфии полиэдров. Однако восполнение этого пробела потребовало бы значительно большего места и времени, чем имелось в моем распоряжении. Задача систематического изложения теории алгорифмов перед любым берущимся за ее решение авто[в«)эщ)[вняав[)18)зд- Вв, Й И, Гззыйгэ з«Г у )9 ПРЕДИСЛОВИЕ ПРЕДИСЛОВИЕ )8 иых проблем и принципиального, и методического характера.

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

Э. Я. Брауэра и Д. Гильберта, и после критики, которой в связи с этим подвеглась традиционная аристотелевская логика, такого рода способ подхода к решению упомянутой задачи представляется отнюдь не праздным. Трудности, связанные с использованием теоретико-множественных представлений, хорошо известны. Мы знаем, что, несмотря на всю проделаннуюспециалистами работу, так называемая „наивная" теория множеств не может считаться избавленной от угрозы появления дальнейших парадоксов. Трудно игнорировать и то обстоятельство, что попытка уточнения этой теории путем ее аксиоматизации также не может считаться удавшейся из-за отсутствия доказательства непротиворечивости предложенных систем аксиом.

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

Поэтому при выборе средств, с помощью которых строится теория алгорифмов, естественно проявлять максимальную сдержанность. Принимая сказанное во внимание, мы еще более тщательно, чем в монографии 121, следим за тем, чтобы наше изложение не содержало теоретико-множественных вкраплений и оставалось в рамках конструктивных процессов и конструктивно приемлемых способов рассуждений. Вместе с тем мы также следим и за тем, чтобы у нас не применялись специфически конструктивные„не приемлемые с теоретико-множественной точки зрения способы умозаключений, так что в итоге мы остаемся работающими „иа нейтральной почве". Такой подход к построению теории алгорифмов делает ее не зависящей от традиционной теории множеств, или даже лучше сказать — от традиционного учения о множествах (Мепдеп!е!зге*)).

И, может быть, со временем это обстоятельство, а также накапливающийся в процессе реализации такого подхода опыт будут содействовать перерастанию упомянутого учения в настоящую теорию множеств (Мепееп!)геог!е) с точным, а не вводимым на примерах определением своего основного понятия. Во всяком случае, уже на данном этапе развития оснований математики возникло понимание того, как может быть точно определено хотя и стандартизованное, но все-таки достаточно гибкое понятие множества: множествами мы можем условиться считать однопараметрические условия, формулируемые в рамках какого-либо точного языка, имеющего точную семантику '*).