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

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

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

Формирование А. А. Маркова как математика происходило на фоне триумфальных успехов созданной Г. Кантором и Р. Дедекиндом теории множеств. Эти успехи привели к формированию и чрезвычайно широкому распространению теоретико-множественного способа мышления, основанного на специфических актах воображения, составляющих в целом абстракцию актуальной бесконечности. Небольшое замешательство, вызванное выявлением некоторых антиномий в так называемой "наивной" теории множеств, было быстро преодолено посредством уточнения "правил игры". В результате интенсивной работы многих исследователей фундамент математики был оформлен в виде четких аксиоматических систем теории множеств. Это предоставило возможность строить важнейшие конкретные разделы математики (алгебру, топологию, математический анализ, теорию вероятностей и др.) чисто дедуктивным путем и достичь высокого, до этого в большинстве областей математики немыслимого уровня отчетливости архитектуры математических теорий, достичь нового уровня "строгости", столь высоко ценимой математиками. Все это способствовало росту престижа теории множеств и появлению у большинства математиков чувства удовлетворенности создавшимся положением, передаваемого каждому новому контингенту молодежи, готовящей себя к профессии математика.

Этот общий фон математической жизни первой половины текущего столетия длительное время определял научные интересы А. А. Маркова и формировал направления его творческой деятельности. В статье Ю. В. Линника и Н. А. Шанина "Андрей Андреевич Марков. К пятидесятилетию со дня рождения" (Успехи математических наук 9, вып. 1(59) (1954), стр. 145-149) приводится краткий обзор исследований А. А. Маркова, опубликованных до 1953 г. (Первая из опубликованных в печати научных работ А. А. Маркова [1] вышла в свет в 1927 г.). Там же приводятся основные биографические данные, относящиеся к этому периоду. Имея в виду этот обзор, мы в дальнейшем изложении сконцентрируем все внимание на новом, самом замечательном этапе научной деятельности А. А. Маркова - на его исследованиях в области конструктивной математики, начало которым было положено в конце 40-х годов и которые чрезвычайно плодотворно продолжаются им и в настоящее время.

Ограничиваясь в настоящей статье обзором работ этого нового этапа, мы хотим подчеркнуть тот факт, что развитие науки в полной мере удостоверило фундаментальное значение вклада, сделанного и не рассматриваемыми здесь более ранними работами А. А. Маркова, непреходящее значение этих работ и их выдающуюся роль во многих областях современной математики. В особенности это относится к работам А. А. Маркова по общей теории динамических систем и теории меры, по топологии и по теории топологических групп (см. упомянутую выше статью Ю. В. Линника и Н. А. .Шанина).

Переход А. А. Маркова к проблемам конструктивного направления в математике, происшедший, как уже упоминалось, в конце 40-х годов, связан с некоторыми давно назревавшими глубинными процессами в области исследований оснований математики. Еще в начале XX столетия были высказаны (в развернутом виде - Л. Э. Я. Брауэром и Г. Вейлем) сомнения в удовлетворительности теории множеств в качестве логической основы математики. В критическом анализе, с которым выступили Брауэр и Вейль, речь шла не о каких-либо дефектах теории множеств, связанных с ее формальным развертыванием по заданным "правилам игры", а совсем о другой стороне дела. Брауэр и Вейль формулировали свои сомнения, апеллируя к требованию интуитивной ясности. По их мнению, представления об "актуально бесконечных множествах" и некоторые связанные с этими представлениями логические средства не соответствуют математической интуиции. Конечно, если бы все дело сводилось к особенностям человеческой интуиции, то критика Брауэра и Вейля не имела бы тех последствий, которые она фактически вызвала. В действительности же Брауэр и Вейль в субъективистских терминах поставили чрезвычайно сложную и принципиальную методологическую проблему, основное содержание которой Д. Гильберт сформулировал следующим образом: "Раньше мы уже выяснили, что какие бы опыты и наблюдения и какую бы отрасль науки мы ни рассматривали, нигде в действительности мы не находим бесконечности. Должны ли мысли о вещах быть столь непохожими на то, что происходит с вещами, должны ли они сами по себе идти другим путем, совершенно в стороне от действительности?"(cм. Д. Гильберт "О бесконечном" (1925 г.). Русский перевод опубликован в виде добавления VIII к книге: Д. Гильберт, Основания геометрии, М. -Л., Гостехиздат, 1948. В приведенной цитате (см. стр. 350 русского перевода) Гильберт, применяя термин "бесконечность", имеет в виду "актуальную бесконечность". Этой цитате в работе Гильберта предшествует анализ данных физики и астрономии, относящихся как к проникновению в глубь материи, так и к исследованию строения вселенной в целом. 14 Успехи матем. наук, т. XIX, вып. 3).

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

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

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

А. А. Марков на протяжении многих лет своей научной деятельности применял классическую теорию множеств в качестве основы многих своих исследований. Однако с первых шагов становления общей теории алгорифмов его отношение к классической теории множеств стало меняться. В теории алгорифмов он увидел не только мощные технические, но и богатые общелогические возможности и начал изучать их с пристальным вниманием. Работа С. К. Клини "Об истолковании интуиционистской теории чисел" (1945г.), уточнившая намеченный Л. Э. Я. Брауэром и развитый А. Н. Колмогоровым подход к конструктивному пониманию суждений, внесла значительную ясность в принципиальные основы нового (конструктивного) направления в математике. Эта работа и достигнутые к тому времени успехи в теории алгорифмов, открывая перед математикой новые перспективы развития в конструктивном направлении, создали такое положение, когда сомнения в удовлетворительности абстракции актуальной бесконечности в качестве основы математического мышления уже невозможно было снять с обсуждения посредством того аргумента, который был упомянут выше: ведь становилось все более и более ясно, что для построения содержательных математических теорий без использования абстракции актуальной бесконечности уже создается подходящая база.

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

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

Существенную роль в подходе А. А. Маркова к основаниям математики играет мысль о том, что различные идеализации, фактически применяемые в современной математике, далеко не одинаковы с точки зрения возможности содержательного истолкования математических теорем, в основе которых лежат эти идеализации. А. А. Марков говорит об этом, в частности, следующее: "Основы современной теории действительных чисел были заложены Кантором и Дедекиндом. Формулированные ими определения действительного числа имеют, однако, ярко выраженный неконструктивный характер: в них говорится о некоторых множествах и последовательностях рациональных чисел при полном игнорировании вопроса о возможности построения таких множеств и последовательностей. Неконструктивность основных определений теории действительных чисел обусловливает неконструктивность всей этой теории, проявляющуюся, например, в теореме о сходимости возрастающей ограниченной сверху последовательности действительных чисел. Теорема утверждает существование действительного числа, удовлетворяющего некоторым условиям, без всякого указания способа вычисления такого числа. Это есть, как говорится, "чистая теорема существования"- в ней утверждается "существование" некоего "объекта", но не сообщается, как сделать этот "объект" сколько-нибудь осязаемым. Непонятно поэтому, в каком же смысле "существует" этот "объект", т. е. что собственно утверждает теорема. Такой же характер имеют и многие другие теоремы теории действительных чисел. Этим положением дел, конечно, нельзя удовлетвориться. Абстракции необходимы в математике, однако они не должны проводиться ради них самих и заводить туда, откуда нет спуска на "землю". Мы всегда должны помнить о переходе от абстрактного мышления к практике, как о необходимом этапе познания человеком объективной действительности,. В тех случаях, когда возможность такого перехода оказывается очень сомнительной, следует пересмотреть применяемые абстракции и постараться их переделать. Такой пересмотр основ необходим, по нашему мнению, в теории действительных чисел и в базирующейся на ней теории функций действительной переменной. В настоящее время имеется реальная возможность осуществлять пересмотр основ анализа. Она обеспечивается разработанностью теорий, связанных с точными определениями таких понятий, как "вычислимая арифметическая функция" и "алгорифм". Мы имеем в виду теорию рекурсивных функций и родственные теории, на основе которых удается определить понятия вычислимого или конструктивного действительного числа и конструктивной функции действительной переменной" (см. [59], стр. 315-316).

Рассматривая абстракцию потенциальной осуществимости (в литературе в близком, но менее четко охарактеризованном смысле применяется термин "потенциальная бесконечность), А. А. Марков характеризует ее как отвлечение "от реальных границ наших конструктивных возможностей, обусловленных ограниченностью нашей жизни в пространстве и времени" ([48], стр. 15). Эта абстракция представляет собой определенную идеализацию, определенный "полет воображения", и она порождает свои трудности содержательного истолкования суждений. Однако, по мнению А. А. Маркова, она основана на существенно меньшем, чем в случае абстракции актуальной бесконечности, произволе нашего воображения, и трудности истолкования, связанные с абстракцией потенциальной осуществимости, имеют более простую природу. А. А. Марков обратился к выкристаллизовывавшемуся в то время конструктивному направлению в математике как к возможной альтернативе классической математики, альтернативе, в которой снимаются или существенно смягчаются возражения, возникающие против математики "актуально бесконечных множеств". Он самым энергичным образом включился в разработку конкретных теорий этого направления. Конструктивное направление в математике А. А. Марков характеризует следующими словами: "В последнее время в математике получило значительное развитие конструктивное направление. Его суть состоит в том, что исследование ограничивается конструктивными объектами и проводится в рамках абстракции потенциальной осуществимости без привлечения абстракции актуальной бесконечности; при этом отвергаются так называемые чистые теоремы существования, поскольку существование объекта с данными свойствами лишь тогда считается доказанным, когда указывается способ потенциально осуществимого построения объекта с этими свойствами... Таким образом, конструктивисты и "классики" по-разному понимают самый термин "существование" в связи с математическими объектами. Впрочем, есть все основания думать, что "классики" вообще не вкладывают в этот термин смысла, поскольку они никогда не поясняют его. Конструктивному пониманию существования математического объекта соответствует конструктивное понимание дизъюнкций - предложений вида "Р или Q". Такое предложение тогда считается установленным, когда хотя бы одно из предложений Р, Q установлено как верное. Это понимание дизъюнкции не дает оснований считать верным закон исключенного третьего: "Р или не верно, что Р" (см. [64], стр. 8-9).

Роль А. А. Маркова в разработке конкретных теорий конструктивной математики исключительно велика. Его первые работы в этом направлении были выполнены в 1946 г. (см. [34]) и опубликованы в печати в 1947 г. (см. [30], [32J, [34], [35]). Эти работы посвящены построению примера ассоциативной системы с неразрешимой проблемой тождества и примера ассоциативной системы с неразрешимой проблемой односторонней делимости. Заметим, что в первых публикациях по этим вопросам с понятиями конструктивной математики еще соседствуют теоретико-множественные понятия классической математики; в дальнейшем, в монографии [48], эти результаты были изложены на строго конструктивной основе.

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

а) Разработано понятие нормального алгорифма, оказавшееся очень удобным для многих целей. Построен развернутый аппарат теории нормальных алгоритмов; в частности, обстоятельно разработан аппарат построения по заданным алгорифмам новых алгорифмов, обладающих заданными свойствами (см. [48], гл. I-IV). Установлена неразрешимость некоторых массовых проблем теории нормальных алгорифмов, играющих роль исходных массовых проблем при доказательствах неразрешимости разнообразных массовых проблем алгебры (см. [48], гл. V). Разработан существенный для построения конкретных теорий конструктивной математики (в частности, конструктивной топологии) специальный аппарат теории алгорифмов, связанный с оперированием над системами слов (см. [67]).

б) Существенно дополнена имеющая принципиальное значение теорема С. К. Клини о представлении частично рекурсивных функций через примитивно рекурсивные, а именно, дана исчерпывающая характеризация примитивно рекурсивных функций, допустимых в качестве внешней функции в формуле С. К. Клини, и как следствие из этой характеризации установлена возможность использования в роли внешней функции весьма простых примитивно рекурсивных функций (см. [39]).

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

а) Осуществлен тщательный анализ логических основ тех теорий, которые имеют дело с конструктивными объектами, и отчетливо сформулированы основные черты конструктивного направления в математике (см. [64]). Сформулирован логический критерий применимости алгорифма к исходному данному, и на его основе сформулирован и обоснован новый логический принцип конструктивной математики - принцип конструктивного подбора, оказавший весьма существенное влияние на конструктивную математику в целом; доказана невыводимость в традиционном конструктивном исчислении предикатов формулы, выражающей принцип конструктивного подбора (см. [64], [49], [51-1).

б) Исследованы особенности конструктивной логики с так называемым "сильным отрицанием", введенным в семантической форме Д. Нельсоном (см. [40]).

в) Подробно развит намеченный еще Г. Вейлем конструктивный подход к понятию множества конструктивных объектов. Множество при этом понимается как формулируемое в рамках некоторого логико-математического языка условие, налагаемое на конструктивные объекты. При таком подходе понятие множества становится точно формулируемым понятием и включается в сферу действия конструктивной логики. А. А. Марковым, в частности, выполнен анализ возможных при таком подходе уточнений понятия "конеч ного множества". При этом оказалось, что понятие "конечного множества" расщепляется на несколько понятий, попарно не эквивалентных друг другу с точки зрения конструктивной логики. С точки зрения классической логики эти понятия попарно эквивалентны и представляют собой лишь различные формы введения единого в классической математике понятия "конечного множества". Этому вопросу был посвящен доклад А. А. Маркова на IV Всесоюзном математическом съезде в 1961 г.

а) Еще в 1946 г. построены конкретное ассоциативное исчисление с неразрешимой проблемой эквивалентности некоторому конкретному слову и конкретное ассоциативное исчисление с разрешимой проблемой эквивалентности слов, но с неразрешимой проблемой односторонней делимости (см. [34], [35], [30], [32]). Вслед за этим было установлено, что при каждом n>6 можно построить конечную систему квадратных целочисленных матриц n-го порядка, такую, что невозможен алгорифм, узнающий для любой квадратной целочисленной матрицы n-го порядка, представима ли она с помощью операции умножения через матрицы построенной системы (см. [44])1). (Этот результат в 1958 г. был А. А. Марковым усилен. В частности, условие п .> 6 было заменено условием п ,> 4 (см. [60]).)

Эти результаты А. А. Маркова - чрезвычайно важный рубеж в развитии алгебры. Именно они положили начало новому направлению идей и исследований в этой области науки. До работ А. А. Маркова в алгебре были известны лишь результаты о существовании алгорифмов для некоторых массовых задач. В результате упомянутых исследований А. А. Маркова впервые стало известно о том, что для некоторых интересовавших алгебраистов массовых проблем разыскиваемые алгорифмы невозможны. Упомянутый результат А. А. Маркова о существовании ассоциативного исчисления с неразрешимой проблемой эквивалентности слов послужил исходным пунктом исследований других авторов в том же направлении. (Аналогичный результат одновременно и независимо получил Э. Пост. Исчисление, опубликованное А. А. Марковым в [35], [32], гораздо проще исчисления Э. Поста. Исчисление, опубликованное в [35], [32], строится в тринадцатибуквенном алфавите и имеет 33 определяющих соотношения. Кроме того, для этого исчисления А. А. Марковым доказана неразрешимость не только общей проблемы эквивалентности слов, но и проблемы эквивалентности некоторому конкретному слову.) В 1950 г. А. М. Тьюринг построил полугрупповое исчисление с сокращениями, для которого также неразрешима проблема распознавания эквивалентности слов. В 1952 г. П. С. Новиков, основываясь на работе А. М. Тьюринга, построил групповое исчисление (конечно-определенную группу) с неразрешимой проблемой распознавания эквивалентности.слов. Этот знаменитый результат П. С. Новикова, давший ответ на один из наиболее принципиальных вопросов теории конечно-определенных групп, подчеркивает значение основополагающей и пионерской роли упомянутых работ А. А.Маркова в области выявления неразрешимых массовых проблем алгебры.

б) Установлена весьма общая теорема о невозможности (при определенных условиях) алгорифма, распознающего среди всевозможных ассоциативных исчислений в заданном алфавите те исчисления, которые обладают заданным инвариантным относительно изоморфизмов свойством (см. [43] и [48], гл. VI, ? 11, теорема 7.1). Об общности и силе этой теоремы говорит, например, следующий ее частный случай:
Если И - инвариантное свойство ассоциативных исчислений, если имеется единичное исчисление со свойством И и в то же время имеется исчисление, не включаемое ни в какое исчисление с этим свойством, то, каков бы ни был алфавит, у которого число букв больше трех, невозможен алгорифм, распознающий исчисления со свойством И среди всевозможных ассоциативных исчислений в этом алфавите.

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

Упомянутая общая теорема замечательна следующей особенностью. Она представляет собой первый (не только в алгебре, но и в математике вообще) результат, говорящий не об отдельной конкретной массовой проблеме, а о неразрешимости всех массовых проблем, удовлетворяющих определенному, притом весьма широкому условию. Эта теорема охватывает почти все стоявшие в то время на обсуждении конкретные массовые проблемы, связанные с основными классификациями ассоциативных исчислений. Как содержание этой теоремы, так и разработанный А. А. Марковым метод ее доказательства, выявили общий механизм алгебраической природы, предопределяющий неразрешимость всех массовых проблем из указанного класса, раскрыли существенно новый круг фактов и возможностей, а также послужили исходными пунктами нового направления исследований. В 1958 г. С. И. Адян и М. О. Рабин получили аналогичные результаты в теории групповых исчислений.

в) Создана капитальная монография "Теория алгорифмов" [48], суммирующая основные результаты А. А. Маркова по теории нормальных алгорифмов и упомянутые выше результаты по алгорифмическим проблемам алгебры. Ее фактическая роль в современной математике далеко выходит за рамки суммарного изложения научных достижений автора. Ввиду того, что-изложение носит систематический и целостный характер, монография в целом дает последовательное и чрезвычайно содержательное построение теории алгорифмов и аппарата теории ассоциативных исчислений, а также систематическое изложение разработанного автором тонкого аппарата сведения одних массовых проблем алгебры к другим. При этом теория ассоциативных исчислений строится (по-видимому, впервые в литературе) как теория конструктивных объектов, независимо от теоретико-множественного понятия ассоциативной системы. Тем самым здесь заложены основы методики постро?ения алгебры на базе строго конструктивных понятий.

Эта монография уже послужила и продолжает служить источником новых идей и новых постановок проблем, она вызвала к жизни много новых работ различных авторов и новые направления исследований. В настоящее время "Теория алгорифмов" А. А. Маркова стала настольной книгой как у специалистов, так и у научной молодежи. Ее перевод на английском языке издан в Соединенных Штатах Америки.

г) В области исследования алгорифмических проблем алгебры особенно значительные и особенно принципиальные результаты получены А. А. Марковым в 1962 г. Они связаны с введенным А. А. Марковым понятием вычислимого инварианта. Роль инвариантов в математике очень велика. Этим определяется важность в теориях конструктивного характера тех проблем,, которые касаются свойств вычислимых инвариантов.

Пусть R - рефлексивное, симметричное и транзитивное бинарное отношение, определенное для конструктивных объектов какого-либо типа. Вычислимым инвариантом отношения R для объекта Р А. А. Марков назы?вает всякий алгорифм, применимый к каждому объекту рассматриваемого типа и перерабатывающий в один и тот же объект все объекты, связанные с Р отношением R. Объекты Р и Q А. А. Марков называет неотличимыми по инвариантам отношения R, если I(Р) = I(Q) всякий раз, когда I есть вычислимый инвариант отношения R как для Р, так и для Q. В работе [63] (более подробное изложение - в [68]) устанавливаются следующие основные результаты об ассоциативных исчислениях и групповых исчислениях (последние в цитируемых работах называются инверсивными исчислениями; групповые (инверсивные) исчисления в литературе также часто называются конечно-определенными группами.)

Теорема 1. Могут быть построены инверсивное исчисление G© и слово А в его алфавите такие, что, во-первых, А не эквивалентно в G© пустому слову и, во-вторых, А и пустое слово неотличимы по инвариантам эквивалентности слов в G©.

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

Следствие теоремы 2. Каковы бы ни были ассоциативные исчисления A и C, можно построить ассоциативные исчисления D и F в одном и том же алфавите такие, что, во-первых, A включаемо в D, во-вторых, F изоморфно C и, в-третьих, D и F неотличимы по инвариантам взаимной преобразуемости. При этом, если алфавит исчисления C содержит q букв, то D и F можно построить как ассоциативные исчисления в (q+4)-буквенном алфавите.

Теорема 3. Каково бы ни было инверсивное исчисление G, можно построить инверсивное исчисление H с восьмибуквенным положительным алфавитом такое, что, во-первых, G© включаемо в H и, во-вторых, H неотличимо по инвариантам взаимной переводимости от явно единичного исчисления с таким же положительным алфавитом, как у H.

Следствие теоремы 3. Каковы бы ни были инверсивные исчисления G и K, можно построить инверсивные исчисления M и N в одном и том же алфавите такие, что, во-первых, G© включаемо в M, во-вторых, N изоморфно K и, в-третьих, M и N неотличимы по инвариантам взаимной переводимости. При этом, если положительный алфавит исчисления K содержит q букв, то M и N можно построить как инверсивные исчисления с (q+8)-буквенным положительным алфавитом.

Эти теоремы представляют собой первые в математической литературе результаты о существовании (точнее, о возможности построения) конкретных конструктивных объектов, не связанных заданным бинарным отношением и в то же время неотличимых по инвариантам рассматриваемого отношения. Таким образом, эти теоремы кладут начало существенно новому и чрезвычайно важному направлению исследований. При этом перечисленные теоремы делают весьма эффективный почин в новом направлении, они дают ответы на наиболее важные из возникающих в теории ассоциативных и инверсивных (т. е. групповых) исчислений вопросов указанного характера. Кроме того, перечисленные теоремы обладают большой силой обобщения. Дело в том, что из неотличимости по инвариантам отношения R некоторых конкретных объектов Р и Q, не связанных этим отношением, следует невозможность алгорифма, распознающего для любого конструктивного объекта S рассматриваемого типа, находится ли он в отношении R к Р. Поэтому теорема 1 представляет собой усиление известной теоремы П. С. Новикова о существовании конечно-определенной группы с неразрешимой проблемой эквивалентности слов, из следствия теоремы 2 сразу вытекает упомянутая выше общая теорема 7.1 из гл. VI, ? 11 монографии А. А. Маркова [48] о нераспознаваемости свойств ассоциативных исчислений, а следствие теоремы 3 является усилением упомянутого выше результата С. И. Адяна и М. О. Рабина.

а) Посредством единой теоремы весьма общего характера решены в отрицательном смысле знаменитые алгорифмические проблемы топологии полиэдров и замкнутых многообразий - проблема гомеоморфии, проблема гомотопической эквивалентности и проблема комбинаторной эквивалентности (см. [54]-[57J). Известно, что перечисленные проблемы возникли уже на самых первых этапах становления комбинаторной топологии и оказали чрезвычайно мощное стимулирующее воздействие на развитие ее аппарата и проблематику. Попытки решения этих проблем в положительном смысле, стимулированные их принципиальным характером, не прекращались на протяжении всей истории топологии. Поэтому перечисленные результаты А. А. Маркова представляют собой выдающееся научное достижение первостепенного значения. Общая теорема А. А. Маркова, непосредственными следствиями которой являются перечисленные результаты, состоит в следующем (см. [55]):

Для, всякого натурального числа n, большего трех, может быть построено связное замкнутое n-мерное многообразие M^n такое, что для любого бинарного отношения R, заключенного между комбинаторной эквивалентностью и родством (определение отношения "родство" см. в [55]), проблема распознавания среди всевозможных n-мерных многообразий тех, которые находятся в отношении R к М^n, неразрешима.

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

б) Установлена следующая замечательная теорема, являющаяся первым в комбинаторной топологии результатом о существовании (точнее, о возможности построения) конкретных объектов, не связанных заданным бинарным отношением и в то же время неотличимых по инвариантам рассматриваемого отношения (см. [63]):

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

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

Общая теорема А. А. Маркова, сформулированная в предыдущем пункте, непосредственно вытекает из этого следствия. Последнее является, таким образом, не только новым фактом в очень интересном направлении, но и существенным усилением теоремы А. А. Маркова о неразрешимости ряда знаменитых массовых проблем топологии.

Разработано понятие конструктивной функции действительной переменной, представляющее собой основанный на понятии алгорифма конструктивный аналог понятия функции действительной переменной, применяемого в классическом математическом анализе. Установлена следующая теорема (см. [49], [59]), сыгравшая роль чрезвычайно важного рубежа принципиального характера в разработке конструктивного математического анализа:

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

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

На протяжении ряда лет А. А. Марков уделяет большое внимание прикладным вопросам математической логики, в частности, вопросам применения математической логики к теории вычислительных машин. Им найдены (в 1957 г.) минимальные контактно-вентильные схемы, реализующие монотонные симметрические булевы функции, исследован (в 1957-1963 гг.) вопрос об инверсионной сложности систем булевых функций (см. [62], [66]). Большой теоретический и практический интерес представляет разработанный А. А. Марковым точный математический язык, предназначенный для описания работы вычислительных машин. Описание реальной вычислительной машины, выполненное на этом языке, имеет точную структуру и допускает исследование математическими средствами (в частности, с помощью вычислительных машин). Разработанный А. А. Марковым язык облегчает также решение важной методической задачи - задачи обучения программированию.

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

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

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

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