Проблема существования базиса в итеративных алгебрах дискретных функций тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ОРДЕНА ЛЕНИНА, ОРДЕНА. ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В.ЛОМОНОСОВА

Механико-математический факультет

ПРОБЛЕМА СУЩЕСТВОВАНИЯ БАЗИСА В ИТЕРАТИВНЫХ АЛГЕБРАХ ДИСКРЕТНЫХ ФУНКЦИЙ

01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

На правах рукописи

МАРЧЕНКОВ Сергей Серафимович

УДК 519.716

Работа выполнена в Институте прикладной математики им. М-В.Келдыша РАН

Официальные оппоненты: доктор физико-математических наук,

профессор Я.М.Барздинь,

в 16 час. 05 мин. на заседании специализированного иовета Д.053.05.05 при Московском государственном университете им. М.В.Ломоносова по адресу: 119899, ГСП, Москва, Ленинские Горы, МГУ, механико-математический факультет, аудитория 14-08 С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан ___ 1992 г.

доктор физико-математических наук, профессор М.М.Глухов, доктор физико-математических наук, профессор А.Н.Дёгтев

Ведущая организация - Институт математики Сибирского отделения РАН

Защита диссертации

Ученый секретарь специализированного Совета Д.053.05.05 при МГУ доктор физико-математических наук

В.Н.Чубариков

ГТ5ЕШ!! этаций

ОБЩАЯ ХАРАКТЕРИСТИКА. РАБОТЫ

Актуальность темы исследования. Большое число теорий в гатематике можно рассматривать как теории множества объектов ! с заданными на нём операциями А . Эта общая концепция формализуется в понятии универсальной алгебры ^Е; ! носителем Е и множеством операций Л . В конкретных ■еориях множества Е и Л могут быть весьма разнообраз-кье. В дискретной математике и математической кибернетике [случили довольно широкое распространение алгебры дискретных фикций с операцией суперпозиции (композиции) и некоторыми [ругими операциями, в состав которых могут входить частные игу чаи операции суперпозиции.

В исследованиях алгебр дискретных функций с операцией ¡уперпозиции центральное место занимает проблема полноты, которую можно сформулировать следующим образом: дня заданной иггебры дискретных функций описать все её системы образующих. 1ля одних алгебр (алгебры функций к-значннх логик, & 5 к< 00 ) •та проблема допускает эффективное решение в ввде явного опи-;ания всех максимальных подалгебр. Дня других алгебр (алгебры «курсивных и близких к ним функций) эту проблему, как прави-ю, решить эффективно невозможно.

С проблемой полноты тесно связана проблема существования г построения базисов.

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

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

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

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

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

дослическая перестановка аргументов, 'С - транспозиция 1ервых двух аргументов, А - отождествление первых двух аргументов, V - введение первого фиктивного аргумента,

- подстановка первой из двух функций на место первого аргумента второй функции, которые с содержательной точки зрели эквивалентны общей операции суперпозиции. Алгебры функций вдда Р^ , А, V, -к > получили название итеративных алгебр.

Цусть /N/ = {0,1,2,... и Ек = (ОД.....к-1 }

при К > 2 ( к £ // ). "срез Р- обозначим множество всех функций ^ "• А/ -> /V, п "1,2..... Аналогичным образом при к ? 2 ( к // ) определяем множества РК. Все иногообразие дискретных функций, встречающихся в дискретной математике и математической кибернетике, нетрудно свести к двум типам: множеству Р^ и множествам Рк. Множество Рд/ отвечает вдее дискретных функций, заданных на бесконечном множестве; функции из Рд, иногда называют функциями счёнозначной логики. Дискретным функциям, определённым на конечных множествах, соответствуй- классы Рк функций к-значной логики.

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

2, < к < «> .

Необходимо отметить, что в соответствии со сложившейся традицией вопросы существования и построения базисов рассматривается не для подалгебр итеративной алгебры Й?^ , а для подалгебр так называемой предытеративной алгебры - К "Р^

Д^ * У, которая отличается от алгебры фд/ отсутствием операции V введения фиктивного аргумента. Однако все результаты (включая результаты диссертации) без труда переносятся с алгебры на алгебру •

е

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

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

Научная новизна. Впервые вопросы существования конечных базисов быни рассмотрены в 1921 г. Э.Постом СшЗ дош подалгебр предытеративной ^алгебры . Э.Пост описал все подалгебры алгебры и указал конечные системы образующих в каадой из них. Аналогичные вопросы для некоторых классов

£> примитивно рекурсивных функций (в диссертации им отвечают подалгебры алгебры ^/у ) были сформулированы А.Гжегорчшсом £14] в 1953 г. Классы §> образуют линейную иерархию множества всех примитивно рекурсивных функций. В 1964 г. Д.Рёдршг С20З доказал существование конечных систем образующих в классах ё> при 3. Впоследствии его решение в качественном отношении было значительно улучшено Ч.Пар-сонсом [дт] .

Таким образом, к началу 70-х годов в предытеративной алгебре были выделены достаточно богатые подалгебры

примитивно рекурсивных функций и найдены конечные системы образующих в них. Довольно очевидно, что получить скодько-нибуд^ удовлетворительное описание всех подалгебр алгебры (и даже всех подалгебр рекурсивных функций

алгебры ), имеющих конечные базисы, невозможно.

Поэтому в проблеме описания подалгебр алгебры "^д, , имеющих конечные базисы, исследования ориетироваось прежде всего на подалгебры с достаточно широкими и содержательно интересными носителями, подалгебры, наиболее часто встречавшиеся в математической практике. Реально речь здесь шла, конечно, об алгебрах рекурсивных или относительно рекурсивных функций. Довольно быстро определились требования на объём подобных алгебр: в них должны бьши входить простейшие рекурсивные функции 0 3 х+1, х+у, % и канторовские нумерационные функции Cix,^"), ttac).» t£xV Дш получения нетривиальных результатов по существованию конечных базисов носгтелн этих алгебр должны, разумеется, определяться в терминах, выходящих за рамка сигнатуры алгебры . При изучении алгебр рекурсивных функций таким пунктом определения естественным образом может служить какая-либо фохма рекурсии. Эти соображения в совокупности с результатами А.Гжегорчика Cl<G почти однозначно приводят к алгебрам, подобным алгебре . К этому ещё следует добавить, что в работе СнЗ вопрос о существовании конечного базиса был сформулирован, в частности, для класса

• г

Класс £ можно определить как наименьший класс функций, содержащий функции 0, €(«, 4) * эс, tx*-L)z замкнутый относительно операций суперпозиции и ограниченной рекурсии. Последнюю возьмем в следующей конструктивной форме В (исходная функция S здесь зависит от п + 2, переменных):

01 =

= min (Si, -К*«......У)))-

_ к

После данных определений вопрос о подалгебрах алгебры ^ , имепцих конечные базисы, естественно ставить лишь для подалгебр, носители которых содержат функции 0, ab С*)(£.) и замкнуты относительно операции В ограниченной рекурсии.

Такие носители мы называем & -замкнутыми, а соответствующие алгебры - & -алгебрами. -алгебры формально можно рассматривать также в виде Д , В где носитель ё> содержит функции (ас+4.)С у-Ч) (последнее "неалгебраическое" условие можно исключить, добавив в сигнатуру £ -алгебры три нульыестных операции).

В конце 60-х - начале 70-х годов несколькими авторами £2,21,7,223 было замечено, что при условии ё2, -замкнутости множества ё> для конечной порождаемое™ предытеративной алгебры ^ Д, достаточно, чтобы в ё> входила

"почти универсальная" функция XI (. п, эс, у ) .в работе С? 3 она была названа максимально универсальной. Более точно, пусть - множество всех одноместных функций из 6 . УГ — £ . Функция называется максимально уни-

версальной для множества относительно множества ^,

если дал любой функции из найдутся такие чис-

ло 1г и функция из . что дая любой функции

\гСх> из Р^/- из соотношения Ь(=с) "г- ^СэО следует, что

1/( гг, = Кэс).

В работе С.7^ было доказано, что если в ё> -замкнутом множестве ё содержится такое конечное множество 'УГ одноместных функций и такая функция Т/ , что 17 является максимально универсальной для множества относительно

замыкания £ множества У?' по суперпозиции, то ал-

гебра ^ Д, является конечно порожденной. Нако-

нец, в работе £35.} автора исследования в этом направлении получили логическое завершение: был сформулирован и доказан критерий конечной порождаемое™ (теорема 4 главы I диссертации). Отметим, что в вопросах существования конечных базисов в подалгебрах алгебры этот критерий пока является единственным.

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

е

версальных функций. Сам метод построения максимально универсальных функций для предытеративных алгебр с £ -замкнутым носителем был. предложен авторш в работах £21,22^ . В отличие от работ Д.Рёддинга Ц20] и Ч.Ларсонса ^173 . где использовалась идея некоторых "производящих" функций, метод работ

[[21,223 можно назвать "машинным", поскольку он основан на арифметизации вычислений на некотором варианте машин Тьюринга. "Машинный" метод по области действия шире методов Рёддинга-Парсонса; обязательным условием применения последних является наличие функций экспоненциального роста.

В теореме 5 главы I диссертации для произвольной конечно порожденной -алгебры С Зь'С', А, машинным

методом устанавливается существование максимально универсальной функции (и подходящего конечного множества 'ЧГ ). Тем самым соответствующая предытеративная алгебра {ё' также оказывается конечно порожденной. Вместе с теоремой 4 теорема 5 полностью решает вопрос о существовании конечных базисов в предытеративных алгебрах с ё> -замкнутыми носителями.

Какова связь меаду существованием конечного базиса в алгебре С £ ; и алгебре К. * ? Какое минимальное число функций может быть в базисах этих алгебр и от какого числа переменных (в первой из этих алгебр)? Ответы на эти вопросы были получены автором в публикациях £.21,22,353 . В диссертации данным вопросам посвящены теоремы I и 2 главы I.

В упомянутых выше результатах по построению конечных базисов в подалгебрах алгебры /у по существу эксплуатировались две идеи: идея "производящих" функций и идея универсальных функций. Вторая идея оказалась с более широкой областью применения, однако "явные" примеры конечных базисов основаны на первой идее. Методы построения конечных базисов до "качеству" получаемых базисов особенно удобно сравнивать на примере алгебры , носитель которой - класс § функций, элементарных по Кальмару. е-3

Класс Ъ имеет большое число эквивалентных определений

ю

и содержит практически все всюду определённые вычислимые функции, встречающиеся в реальной математической практике. Он интересен и с прикладной точки зрения, поскольку в нём легко ариф-ыетизируются многие процессы, распространённые в дискретной математике и математичксой кибернетике: нумерация схем и формул, построение схем и формул с заданными свойствами, проверка конечных систем функций из Рк на полноту и т.д. В связи с этим получение конечного базиса в алгебре ^ имеет не только чисто теоретическое значение, но может быть использовано, например, для получения сложностных характеристик указанных процессов (см. по этому поводу работу £зЗ ).

Первый результат Д.Рёдцинга £203 о конечной порсвдаемос-ти алгебры ^ представляет собой по существу чистую теорему существования. В явном ввде система из 19 функций, порождающих алгебру , была предложена Ч.Парсонсом £17,3 • Эта система не является базисом и, кроме того, половина функций системы имеет громоздкое, "многоэтажное" строение с одним или двумя операторами эс . П { $ а •

Новые возможности в построении простых базисов в алгебре открыно применение диофантовых и экспоненциально диофан-товых представлений рекурсивно пере числимых предикатов. А. К. Виноградовым, Н.К.Косовским £13 и Л.Эдаименом, К.Мандерсом Си] было замечено, что в диофантовых и экспоненциально диофантовых представлениях предикатов из класса переменные под кванторами существования можно ограничить подходящими функциями из того же класса ё3 . Более того, эти функции можно выбрать среда суперпозиций функции Ц . Данные соображения шесте с некоторыми результатами теоретико-числового характера позволили автору трансформировать сравнительно несложные технические средства, используемые в диофантовых и экспоненциально диофантовых представлениях, в простые системы образующих алгебры ¡£3 £24,343 . Так, в работе £24 Д было доказано, что алгебру & 3 порождает система функций

\ х + 1, ос*, эс— У, Ч) 1, где при зс>1 значение »?(.*> равно наименьшему номеру нулевого разряда в представлении ^ в позиционной системе с основанием X . Там же было установлено, что для порождения всех функций из &3 , принимающих лишь значения 0,1 ("предикаты" класса &3 ) достаточно взять систему функций

е! ■= { 1, ос*, ж-*, С%] 3 •

В работе С153 Дж.Джонса и Ю.В.Матиясевича найден ещё ряд конечных систем функций, аналогичных по порождающим свойствам системе 5

Продолжая далее развивать идеи работы £24} , автор в работе С343 доказал, что алгебру порождает каждая из

систем функций

{г**4, С^З.^Ь -I **. ъШ,

где <5(=0-число единиц в двоичном представлении зс , а X (Л*-") равно показателю числа 2 в разложении X на простые множители, если зс > О ,и ТСо") « О (теорема 6 и следствие I главы I диссертации).В доказательствах использовались результаты Ю.В.Матиясевича Сб.б] об однократных экспоненциально диофантовых представлениях рекурсивно перечислимых предикатов. Полученные в работах С24,343 результаты позволяют высказать гипотезу о том, что система 5 может служить некоторым естественным "пределом" для базисов алгебры Стоит также отметить, что конструкции и результаты работ С24, 343 свидетельствуют о глубокой всязи, имеющейся мевду "простотой" базиса алгебры £3 и некоторыми логическими и теоретико-числовыми проблемами.

Переходя к алгебрам с бесконечными базисами, заметим, что уже сам вопрос о построении в алгебре ^Рлл содержательно интересной подалгебры с бесконечным базисом является далеко не тривиальным. В 1959 году С.В.Яблонским С83 был указан пример

счётного множества & одноместных неограниченных функций, для которого алгебра <С £ ; имеет бесконечный базис.

Подалгебру алгебры со счётным^базисом можно также полу-

чить, "спроектировав" из в 13-ы известный пример

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

Впервые построить бесконечный базис в некоторых хорошо известных алгебрах одноместных рекурсивных функций удалось автору в работе £.253 . В дальнейшем существенно иными методами аналогичная проблема была решена автором и в алгебрах многоместных рекурсивных функций £32,35.3 . Было показано, что произвольная счётная подалгебра алгебры с примитивно рекурсивно замкнутым носителем имеет счётный базис (теорема 7 главы I диссертации). Отказ от условия счётности здесь, вообще говоря, невозможен - алгебра фр/ ■ как хорошо известно, базиса не имеет. В связи с этими результатами возник естественный вопрос: а могут ли вообще несчётные подалгебры алгебры ^^ с достаточно богатыми носителями (например с примитивно рекурсивно замкнутыми) иметь базисы? Положительный ответ на этот вопрос получен автором в работе £353 (теорема 8 главы I диссертации).

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

подалгебры имеют соответственно конечные, счётные и континуальные базисы. Установлено, что свойство иметь базис - конечный шш бесконечный - для наиболее важных в прикладном отношении алгебр является скорее правилом, чем исключением.^Описан широкий класс подалгебр (предытеративные редукты <= -алгебр),

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

Как отмечалось, вопросы конечной порождаемое™ подалгебр алгебры 32£ впервые начали разрабатываться Э.Постом £18 В работе [1.19.3 завершены исследования, начатые в ¡^18^ . описаны все подалгебры алгебры и доказана их конечная

порождаемость. Современное изложение результатов Поста можно найти в книгах Сэ,4Д .

Та, во многом уникальная ситуация, которая имеет место для алгебры , совершенно меняется при переходе к алгеб-

рам дЗк , к > «3 . Как установили Ю.И.Янов и А.А.Мучник, уже алгебра содержит континуальное число подалгебр,

среди которых имеются как подалгебры со счётным базисом, так и подалгебры, не имеющие базисов вообще. В связи с этим для алгебр у , \с ^ на первый план выдвинулась задача описания конечно порожденных подалгебр. К настоящему времени никакого удовлетворительного описания таких подалгебр не получено. Известно лишь несколько серий подалгебр с конечными базисами. Среди них часть максимальных подалгебр (при 3 < к 5 ? -все максимальные подалгебры, но уже при к = 8 - нет), алгебры

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

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

Согласно Е.Марчевскому [ДбЗ , алгебра ^Е; назы-

вается однородной, если её группа автоморфизмов является полной симметрической группой подстановок на множестве Е. В частности, функция : Еп-» В называется однородной, если однородна алгебра Е; { 5 ^ ^ .В другой терминологии функция называется однородной, если она самодвойственна

относительно любой подстановки множества Е.

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

Итеративные алгебры однородных функций естественным образом появляются при классификации алгебр с заданной группой автоморфизмов, в частности, с полной симметрической группой. Именно, классифицировать алгебры ^Е; ^ с группой автоморфизмов Г можно, например, по типам изморфизма. Однако уже в самом простейшем случае ( | Е | = 2, Г - полная симметрическая группа) число таких типов оказывается континуальным. Поэтому Г.Гретцер предложил считать алгебры

{Е; Й1{ ) , ( Е.; Л г эквивалентными, если сов-

падают клоны, поровдённые множествами операций Л и . Иными словами, если Е = Ед и е ас. , то алгебры

< Е; А*.} , ^ Е; Лл ^ эквивалентны, если совпадают подалгебры, порсадённые в предытеративной алгебре = = ^ Рк; Д, множествами и Л а о { е 3 . Таким образом, классифицировать алгебры ( Е^ Л ^ о точностью до введённого отношения^ эквивалентности - значит описывать подалгебры алгебры ^ , содержащие селекторную функцию 6 . После небольшого обобщения мы приходим к следующей проблеме для итеративных алгебр

Пусть Г - группа подстановок на Е^, Иг - множество всех таких функций из Р„, что Г содержится в груше

/„ г1 Ч „__. . _______

автоморфизмов алгеоры \ Е^; [ и ^ . цриилсма ииихшх а описании всех подалгебр итеративной алгебры

= < IV й.хл,

Если Г - единичная группа, то Нг = Рк. Случай к = 2, как отмечалось выше, полностью исследован Э.Постом.

Пусть ~ полная симметрическая группа подстановок

на Ек. Тогда % - итеративная алгебра однородных функций из Рк. В связи изучением замкнутых классов самодвойственных функций к-значной логики в работе СйзЗ автора были полностью описаны все подалгебры алгебры ^¡в^ • Почти одновременно Б.Чакань и Т.Гавалцова \123 начали исследования по классификации конечных однородных алгебр. При этом всё по существу свелось к описанию подалгебр итеративной алгебры ^г^ • В работе [12З путём построения базисов было указано 6 подалгебр в. алгебре ^ ,8 подалгебр в алгебре ^ в $ и 2к-1 подалгебр в алгебре при к 5 5. Однако даже

в случае к = 3 исследования в £12 3 не были доведены до конца. Более того, одно из основных утверждений работы [Д23 - теорема 2 содержала ошибку. Полное описание всех подалгебр итеративных алгебр ^ ^ •> ^ ? ^ с указанием конечных базисов принадлежит автору С26,27Д .

Доказано, что алгебра Уд содержит, включая саму

алгебру Чу , ровно 8 подалгебр, алгебра ^ - 14 подалгебр и алгебра ПРИ к ^ 5 - ровно 4к-3

подалгебр (теорема 2 главы П диссертации). Каждая из подалгебр

алгебры , W > охарактеризована некоторым свойством.

Во всех алгебрах однородных функций указаны конечные базисы и определены порядки алгебр (минимальное число Z , для которого существует базис, состоящий из функций от не более чем Ъ аргументов). Таким образом, оказалось, что для любого к, к £ ^ 3, любая однородная алгебра вида Ек; SL У (вообще говоря, с бесконечным множеством операций Л ) эквивалентна одной из конечного числа (при данном к ) конечных однородных алгебр. Тем самым решена проблема классификации однородных алгебр с конечными носителями.

Следующий шаг по изучению итеративных алгебр вида ^ г был сделан автором для знакопеременной подгруппы Ад группы

Sic £28,29,33j . Во-первых, с помощью построения алгебр со счётным базисом удалось доказать, что алгебра Ч^Дд содержит континуальное число подалгебр [j28,29^ • Однако гораздо более важный факт заключается в том, что при любом к, к 2? 4, алгебра Чд д w содержит лишь конечное число подалгебр £28,333 . Именно, при к = 4 отличных от алгебр однородных функций их имеется ровно 20, а при к ? 5 - 8к-П В каждой подалгебре алгебры д h , к >■ k, был наеден конечный базис и вычислен порядок алгебры (теорема 3 главы П диссертации). Таким образ мл, при к > 4 эффективно решена проблема классификации алгебр ^ Ej^; Л У со знакопеременной группой автоморфизмов.

При дальнейшем продвижении в этом направлении возникает естественный вопрос: для каких подгрупп Г группы $ fc возможно такое же описание всех подалгебр алгебры ^ р , какое получено даш алгебр и 7 в частности,

для каких подгрупп Г итеративная алгебра содержит

конечное число подалгебр ? Полного решения указанной проблемы пока не найдено. Примерно в одно и то же время Я.Деметровичем, Л.Ханнаком £1зД и автором £23J были получены близкие результаты по алгебрам Ч^р с циклической группой Г В них для ряда групп получалось, что итеративная алгебра

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

группой Г бал решён автором С^эЛ : дая любой циклической подгруппы Г группы 5>|< , к > 3, итеративная адгебра содержит континуальное число подалгебр (теорема 4 главы П диссертации). В частности, как отмечалось выше, континуальное число подалгебр будет содержать алгебра ^д3 . Доказательство этих утверждений опирается на построение подалгебр со счётным базисом.

Результаты автора из Г^эД завершают цикл исследований ещё по одной проблеме, изучавшейся в литературе. Речь идёт об определении числа "9 (всех подалгебр итеративной алгебры

Л7 _______(Т1 __________________________- -«'>

, ¿ъил^а V V с^ла шало*1м<ал_ьпсги иидсии/ещде а •

Дело в том, что, как хорошо известно СгоД , значение

континуально при любом к, к > 3. В связи с этим возник вопрос о распределении "континуума" среди максимальных подалгебр алгебры . Усилиями целого ряда исследователей

(Я.Бадышский, Я.Демтрович, Д.Лау, А.Саломаа, А.Севдрей, Л.Хан-нак) величина ^С <Ж>) была определена для всех типов максимальных подалгебр алгебры ^рк за исключением типа ^^ , когда Г есть циклическая группа. Как доказал автор С"2эХ в этом, технически самом сложном случае, ■$( ^р) также есть континуум.

Результаты по итеративным алгебрам и 4 к

позволили выдвинуть гипотезу о том, что наличие в итеративной алгебре неселектороной однородной функции может обеспечить конечную порождаемость соотвествувдей алгебры. Впервые в общей постановке этот вопрос исследовался автором в работе С31Л . Оказалось (теорема 5 главы И диссертации), что для подалгебр алгебры это так: всякая подалгебра алгебры , со-

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

к имеется континуальное число подалгебр, каздая из которых содержит фиксированную однородную функцию Е^ . Среди этого континуального множества алгебр есть как алгебры со счётным базисом, так и алгебры без базиса.

Методы исследований. Для предытеративной алгебры ^ и итеративных алгебр ^ методы исследований существенно различны. ^

Для подалгебр алгебры характерны методы теории

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

Метод универсальных функций широко используется в теории рекурсивных функций. Нередко он выглядит как метод (равномерного) моделирования одних вычислительных устройств другими вычислительными устройствами. При этом обычно моделирующие вычислительные устройства оказываются мощнее моделируемых вычислительных устройств. Б диссертации при построении конечных базисов в предытератавных алгебрах с & -замкнутыми носителями рассматривается иная ситуация: классы моделирующих и моделируемых устройств совпадают. Чтобы для всюду определённых функций не получить противоречия, моделирование проводится не "до конца". Это позволяет получившейся вариант универсальной функции использовать в качестве основного элемента в конечном базисе алгебры. Данный подход, впервые предложенный автором, и составляет суть "машинного"^метода построения конечных базисов в подалгебрах алгебры с ё> -замкнутыми носителями. Отметим, что до настоящего времени "машинный" метод построения конечных базисов остаётся самым общим по области применения.

Идея применения производящих функций при построении базисов в алгебре принадлежит Д.Рёддингу £203 и Ч.Парсон-су £173 • Автор при исследовании алгебры объединил эту идею с диофантовыии и особенно с экспоненциально диофанто-выми представлениями рекурсивно перечеслимых предикатов.

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

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

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

ласти. Основная часть исследований здесь проводится по следующей схеме: в рассматриваемой подалгебре ОЬ алгебры ¡4?к строится базис, затем определяется конечное множество собственных попарно не сравнимых по включению подалгебр и доказывается теорема о полноте: система функций алгебры №> порождает алгебру 0[у , если она целиком не содержится ни в одной из определённых подалгебр алгебры ОЬ . Тем самым указанные подалгебры алгебры оказываются всеми её максимальными

подалгебрами. Далее описанный процесс применяется к каждой из максимальных подалгебр алгебры ОЬ .

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

Апробирование и публикации. Результаты диссертации излагались на Международном конгрессе математиков (Варшава, 1983), международной конференции по универсальной алгебре и многозначной логике (Сегед, 1979), на советско-германский семинарах по дискретной математике и математичкской кибернетике (Йена, 1982 и 1986), в Международном математическом центре им. С.Банаха (Варшава, 1987), на У и У1 Всесоюзных конференциях до математи-

ческой логике (Новосибирск, 1979 и Тй<илиси, 1982), на I и П Всесоюзных конференциях до прикладной логике (Новосибирск, 1985 и 1988), на УН Всесоюзной конференции по теоретической кибернетике (Иркутск, 1985), на Всесоюзном семинаре по дискретной математике (Москва, 1984), на семинарах по кибернетике под руководством члена-корреспондента АН СССР С.В.Яблонского в МГУ, на семинарах по теории алгоритмов под руководством члена-корреспондента АН СССР Ю.Л.Ершова в Институте математики СО АН СССР, а также на некоторых других конференциях и семинарах.

Результаты диссертации опубликованы в работах £2I-35J .

Структура и объём работы. Диссертация состоит из введения, двух глав, заключения и списка литературы. Первая глава разбита на 5 параграфов, вторая - на 4. Объём работы 231 страница, включая 8 страниц цитированной литературы. В списке литературы 81 наименование.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В § I главы I даются основные определения. В § 2 доказываются общие теоремы,о базисах в подалгебрах предытеративной алгебры . Термин "общие" в данном случае говорит о том, что вопросы существования базисов изучаются в самой общей постановке при минимуме условий, налагаемых на исследуемые подалгебры. Главное из этих условий - наличие канторовских нумерационных функций С, Е, Ъ .в теореме I установлена связь между существованием конечных базисов в алгебре 'Зг * ^ >

и алгебре «Зг* = < > *> .где -мно-

жество всех одноместных функций из ^ . Именно, если

{ С, 1 3 С "51, то алгебра § имеет конечный базис в том и только том случае, когда конечный базис имеет алгебра

От .В качестве следствия теоремы I из существования бесконечного базиса в алгебре § выводится существование бес-

конечного базиса в алгебре

В теореме 2 решается вопрос о числе функций и числе переменных у функций в конечных базисах алгебр Т и С? * Если { С, Е, 1Л С то в случае существования конечного Зазиса в алгебре в алгебре ^ будет существовать

Зазис, состоящий из двух функций, но не может быть базиса, со-зтоящего из одной функции. Если дополнительно множеству "3? принадлежат функции сс.V-1, ~ то в алгебре 5г имеется базис, состоящий из одной двуместной функции.

Пусть { С, С ? и ачгебра не иглсст конеч-

ного базиса. В теореме 3 доказывается, что в случае счётности множества в каддой из алгебр 'Зг ? ^ содержится

гакая (счётная) система образующих, из которой невозможно вцде-(шть базис.

Теорема 4 содержит критерий существования конечного бази-за в алгебрах с -замкнутым носителем: .для того чтобы алгебра 5 о ^ -замкнутым носителем имела конечный базис, необходимо и достаточно, чтобы в входили такие функция

V и конечное множество функций 'У? , что 17" является лаксимально универсальной для 9? относительно множества

СУЗ . _

|сли \г - конечно порождённая предытеративная алгебра з ё> -замкнутым носителем, то ё -алгебра К. ЗР-1 З^Т» 4 >

очевидно, также является конечно порождённой. Обрат-юе утверждение представляет собой нетривиальный факт, доказа-гельству которого посвящен § 3 главы I. Здесь устанавливается [теорема 5), что из конечной пороздаемости ё> -алгебры & зледует конечная порождаемость её предытеративного редукта

£ . Доказательство проводится ари^метизацией средствами алгебры £ относительных вычислений на специальных несгира-яцих многоленточных машинах Тьюринга - машинах Минского.

В § 4 строятся конечные системы образующих в алгебре . Показывается (теорема 6 и следствие из неё), что предытератив-ную алгебру £3 породдает каждая из уже приводившихся выше

систем функций ч ,

[У,], г"*', 1.1 **С« » •1 ■

В следствии 2 теоремы 6 устанавливается, что все функции из & с конечными множествами значений порождаются (в алгебре ) системой функций { эс+-£, ос*, С5 •

§ 5 главы I посвящен подалгебрам алгебры /V • имеющим бесконечные базисы. Доказывается, во-первых (теорема 7), что всякая счётная подалгебра алгебры ^^ с примитивно рекурсивно замкнутым носителем имеет (счётный) базис. С применением следствия из теоремы I аналогичный результат устанавливается для соответствующих алгебр одноместных функций. Иней, заложенные в доказательстве теоремы 7, переносятся в теореме 8 на континуальные алгебры: любое счётное множество функций из содержатся в носителе подходящей континуальной подалгебры алгебры • имещ^ей (континуальный) базис.

В § I главы П исследуются итеративные алгебры однородных функций.. Центральный результат параграфа I (теорема 2) состоит в описании для любого к, к 3, всех подалгебр итеративной алгебры * < Н > А, V, К"}, где Н - множество всех однородных функций из Рк. Подалгебры алгебры ^ 5 ^ задаются подходящими свойствами, которыми обладают все функции носителя соответствующей подалгебры. Для каждой из определённых подалгебр строится конечный базис. Доказывается, что алгебра содержит ровно 8 подалгебр (включая саму алгебру ^ 5 3 ), алгебра Щ5 ^ - 14 подалгебр и при к ? 5 алгебра к ~ 4х_3 подалгебр. Для любого к, к ? 3,

определяются порядки всех подалгебр алгебры ^¡ц, ■ которые оказываются равными порядкам построенных в этих подалгебрах базисов. На основе описания подалгебр алгебры строится

диаграмма включений. Из неё и из описания подалгебр алгебры ^ $к видно, что все алгебры однородных функций делятся на четыре примерно равные серии, которые отвечают четырём основным свойствам однородных функций.

В § 2 главы Д исследуются итеративные алгебры Ч*] чётных функций. Функция из Рк называется в диссертации

чётной, если группа автоморфизмов алгебры К содер-

жит знакопеременную подгруппу А^ группы б £ . Согласно этому определению, все однородные функции также являевтся чётными. Идя любого к, к >4, в теореме 3 перечисляются все подалгебры алгебры ^ А к • Подалгебры определяются с помощью подходящих свойств, которые задают носители этих подалгебр. В каждой из определённых подалгебр строится конечный базис. Устанавливается, что в алгебре ^А^ содержится ровно 20 подалгебр, экшчных от Алгебр однородных функций (вклсчая саму алгебру

^ А ц ), а при к > 5 в алгебре А к - ровно Зк-11 подалгебр, отличных от алгебр однородных функций. Так ке, как и в § Г, для всех исследуемых алгебр чётных функций эпределён порядок алгебры, который оказывается равным порядку построенного в ней базиса. Для любого к, к 4, приводится диаграмма включений подалгебр алгебры • отличных от

юдалгебр алгебры ^ § ^ . Из диаграмм и описаний подалгебр зледует, что все подалгебры алгебры > содержащие неод-

*ороднне функции, разбиваются на восемь примерно равных по мощности серий, которые соответствуют восьми основным свойствам неоднородных чётных функций.

§ 3 главы П посвящён алгебрам с циклической группой авто-лорфизмов. В нём доказывается следующий основной результат (теорема 4). Пусть к > 3, Г - циклическая группа подстановок га множестве £к, Н^ - множество всех функций ^ из Рк, %пя которых груша автоморфизмов алгебры <( Е„; ^ вклю-

тает группу Г . Тогда итеративная алгебра ч| р = <" Нр-5 ^ Г, Д, V, * "> содержит континуальное число подалгебр. Доказательство этого результата получается построением счётного ба-шса в некоторой подалгебре алгебры Ч^р . Отметим, что \3 - циклическая группа. Поэтому алгебра также содер-

жит континуальное число подалгебр.

В заключительном § 4 главы П исследуется вопрос о конечной юрождаемости подалгебр алгебры ^ , к "9- 3, содержащих

нетривиальные (неселектоные) однородные функции. Доказано (теорема 5), что в ^з имеется в точности счётное число подалгебр, содержащих нетривиальные однородные функции. Каждая из этих подалгебр имеет конечный базис. Напротив, для любого к, к > 4, в алгебре |с имеется континуальное число подалгебр, каждая из которых содержит фиксированную нетривиальную однородную функцию.

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

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

1. Доказательство критерия существования конечных базисов в предытеративных алгебрах с ¿> -замкнутыми носителями. Машинный метод построения конечных базисов в предытеративных алгебрах, удовлетворяющих условиям критерия.

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

3. Доказательство существования счётных базисов в счётных предытеративных алгебрах с примитивно рекурсивно замкнутыми носителями. Доказательство существования континуальных базисов в некоторых предытеративных алгебрах с примитивно рекурсивно замкнутыми носителями.

4. Описание для любого к, к ? 3, в итеративной алгебре

V. всех подалгебр однородных функций с указанием их базисов и порядков. Классификация однородных алгебр с носителем Ек, к 5 3,

5. Описание для любого к, к >4, в итеративной алгебре всех подалгебр чётных функций с указанием их базисов и порядков. Классификация алгебр с носителем Ек, к 4, и знакопеременной группой автоморфизмов.

6. Для любого к, к 3, и любой циклической группы Г подстановок на множестве Ед определение мощности

множества попарно не эквивалентных алгебр ^ с

группой автоморфизмов Г

7. Решение вопроса о конечной порождаемое™ подалгебр алгебр ф \: . к > 3, содержащих нетривиальные однородные функции.

ЛИТЕРАТУРА

1. Виноградов А.К., Косовский Н.К. Иерархия диофантовых представлений примитивно рекурсивных предикатов // Вычислительная техника и вопросы кибернетики. - Ленинград, 1975. -12. - С. 99-107.

2. Козмвдиади В.А., Ыарченков С.С. О многогсловочных автоматах // Проблемы кибернетики, вып. 21. - 1969. - С. 127-158.

3. Марченков С.С. О сложности вычисления экспоненты // Матем. заметки. - 1982. - 31, № 3. - С. 457-463.

4. Марченков G.G., Угольников А.Б. Замкнутые классы булевых функций. - М.: Из-во ИПМ АН СССР, 1990.

5. Матиясевич Ю.В. Существование неэффекгивизируемых оценок в теории экспоненциально диофантовых уравнений // Записки научн. семинаров Ленинград, отделения математич. ин-та АН СССР. - 1974. - 40. - С. 77-93.

6. Матиясевич Ю.В. Новое доказательство теоремы об экспоненциально диофантовом представлении перечислимых предикатов. Записки научн. семинаров Ленинград, отделения математич. ин-та АН СССР. - 1976. - 60. - С. 75-92.

7. ручник A.A. О двух подходах к классификации рекурсивных функций. - В кн. "Проблемы математической логики", М.: Мир, 1970. - С. 123-138.

8. Яблонский C.B. О некоторых свойствах счётных замкнутых классов из РКо, П ДАН СССР. - 1959. - 124, № 5. - С. 990-993.

9. Яблонский C.B., Гаврилов Т.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста. - М.: Наука, 1966.

10. Янов ю.И., (Лучник A.A. 0 существовании к-значных замкнутых классов, не имеодих конечного базиса // ДАН СССР. - 1959. -127, Jí I. - С. 44-46.

11. Adleraan X., Handera К. Computational complexity of decision procedures for polynomials // 16th Annual oy.Tip. Pound. Comput. Sei., 1975, Ilevv-íork, Ii.J. - 1975. - P. 169-177.

12. Csákány В., Gavalcová Т. .finite homogeneous algebras I // Acta Sei. Math. - 1980. - 42.- P. 57-65.

13. Demetrovics J.f Hannák L. The cardinality of closed sets in pre-cornplete classes in k-valued logics // Acta Cybernet. - 1979. - 4, I¡ 3. - P. 273-277.

14. Grzegorczyk A. Some classes of recursive functions // Inst. Idat. Polsk. Akad. Haul:, Rozprawy Matenatyczne, IV, '.Varszawa, 1953.

15. J ones J.P., '.Iatijasevic Ju. V. A new representation for the symmetric binomial cosfficien and its applications // Ann. Sc. Hath. Quebec. - 1982. - IV, Ii I. - P. «i-97.

16. Marczewski E. Homogeneous algebras and hoaogeneous operations // fund. Math. - 1964. - P. 81-103.

17« Parsons Ch. Hierarchies of primitive recursive functions // Zeitschr. math. Logik und Grundla.;. I,lath. - I960. - 14, II 4. - S. 357-376.

18. Poot E. Introduction to a general theory of elementary proposition // Amar J. Math. - 1921. - 43. И 3. - P. 163-185.

19. Post E. The two-valued iterative systems of mathematical logic // Ann. Math. Studies, Princeton, 1941.

20. Rödding D. Uber die Eliminierbarlceit von Definitionschemata in der Therie der rekursivsn Punktionen // Zeitschr. math. Logik und Grundlag. Math. - 1964. - 10, H 4. -

S. 315-330.

Работы автора по теме диссертации

21. Марченков С.С. Устранение схем рекурсий в классе &

Гжегорчика // Матем. заметки. - 1969. - 5,№ 5. - С. 561568.

22. Марченков С.С. Об ограниченных рекурсиях // Mathe^atica Ballcanica,BeoSrad, 1972. - 2. - С. 124-142.

23. Марченков С.С. О замкнутых классах самодвойственных функций многозначной логики // Проблемы кибернетики, вып. 36.

- 1979. - С. 5-22.

24. Марченков С.С. Об одном базисе по суперпозиции в классе функций, элементарных по Кальмару // Матем. заметки. -1980. - 27, » 3. - G. 321-332.

25. Марченков С.С. Существовало базисов по суперпозиции п счётных примитивно рекурсивно замкнутых классах одноместных функций Ц Матем. заметки. - 1980. - 27, № 6. - С. 877-883.

26. Марченков С.С. Об однородных алгебрах // Доклады АН СССР.

- 1981. - 256, № 4. - С. 787-790.

27. Марченков С.С. Однородные алгебры // Проблемы кибернетики, вып. 39. - 1982. - С. 85-106.

28. Марченков С.С. О классификации алгебр со знакопеременной группой автоморфизмов // Доклады АН СССР. - 1982. - 265, ЯЗ. - С. 533-536.

29. Марченков С.С. О замкнутых классах самодвойственных функций многозначной логики J J Проблемы кибернетики, вып. 40.

- 1983. - С. 261-266.

30. Марченков С.С. О классификации алгебр с данной группой автоморфизмов п International congress of mathematicians, Warszawa, 1983, Short communications,' II, p. 32.

31. Марченков С.С. О замкнутых классах в Рк, содержащих однородные функции // Препринт ШМ АН СССР № 35 за 1984 г.

32. Марченков С.С. Существование базисов по суперпозиции в счётных примитивно рекурсивно замкнутых классах // Матем. заметки. - 1986. - 39, № 2. - С. 268-276.

33. Марченков С.С. Классификация алгебр со знакопеременной группой автоморфизмов // Математические вопросы кибернетики, вып. 2. - 1989. - С. 100-122.

34. Марченков С.С. Простые примеры базисов по суперпозиции в классе функций, элементарных по Кальмару // Banach Center iublicatiorw - 1989.- 25. - P. II9-I26.

35. Марченков С.С. Базисы по суперпозиции в классах рекурсивных функций // Математические вопросы кибернетики, вып. 3. - 1991. - С. II5-139.

Марченхов Сергей Серафимович г Проблема существования базиса в нтеративньх алгебрах дискретных функций'« Специальность 01.01.09 ~ математическая кибернетика.

Подписано в печать OS.03.92г. Заказ № 55, Тираж lOO экз.

Отпечатано на ротапринтах в Институте прикладной математики АН