Введение к работе
Актуальность темы исследования. Большое число теорий в гатематике можно рассматривать как теории множества объектов і с заданными на ней операциями St . Эта общая концепция формализуется в понятии универсальной алгебры ^В; Sh / ! носителем Е и множеством операций Л . В конкретных еориях множества Е и оь могут быть весьма разнообраз-кье. В дискретной математике и математической кибернетике [случили довольно широкое распространение алгеоры дискретных фикций с операцией суперпозиции (композиции) и некоторыми [ругими операциями, в состав которых могут входить частные яучаи операции суперпозиции.
В исследованиях алгебр дискретных функций с операцией ;уперпозиции центральное место занимает проблема полноты, ко-,'орую можно сформулировать следующим образом: для заданной ілгебрн дискретных функции описать все её системы образующих. 1ля одних алгебр (алгебры функций к-значннх логик, й « k< ) та проблема допускает эффективное решение в виде явного опи-іания всех максимальных подалгебр. Для других алгебр (алгебры «курсивных и близких к ним функций) эту проблему, как прави-ю, решить эффективно невозможно.
С проблемой полноты тесно связана проблема существования г построения базисов.
Понятие базиса во многих разделах математики является щним из основных. В любой универсальной алгебре базис можно шределить как независимую (минимальнуо) систему образующих. Іаличие базиса в алгебре (и даже "хорошей" системы образующих) шедует, безусловно, отнести к важным положительным свойствам ілгебрн. Базис алгебры даёт возможность определить алгебру геизбыточным (а в случае конечного базиса - в известном смысле і эффективным) образом, во многих случаях позволяет канонизировать представление элементов алгебры через элементы базиса.
Входящие в базис элементы алгебры обладают самыми существенными свойствами, характерными для изучаемой алгебры. Поэтому часто на основе исследования термального представления элементов алгебры через элементы базиса удаётся решить ряд важных задач: указать алгоритм построения всех максимальных подалгеб] или вообще всех подалгебр, решить проблему полноты, определит] структуру и оценить сложность вычисления элементов алгебры и т.п. Только одна характеристика базиса - его мощность - позволяет сделать выводы о принципиальной возможности решения проблемы полноты в терминах максимальных подалгебр и о некоторых структурных характеристиках частично упорядоченного множества всех подалгебр. Существование конечных базисов в алгебрах рекурсивных функций с операцией суперпозиции значительно упрощает построение универсальных функций.
Решение проблемы полноты в алгебре СЬ дискретных функций с операцией суперпозиции зачастую выглядит следующим образом. В алгебре ОЬ строится "удобный" базис В . Затем определяется некоторое множество И подалгебр алгебры ОЬ . доказывается максимальность всех подалгебр из М и "критериальность" множества М (совпадение М с множества всех максимальных подалгебр алгебры ОС ). Последнее доказательство состоит в том, что устанавливается принадлежность базиса В люой подалгебре алгебры СЬ , не содержащейся целиком ни в одной из алгебр множества м".
В более сложных случаях, когда эффективное решение проблемы полноты в алгебре 0V невозможно, исследования по проблеме полноты в алгебре ОЬ обычно ограничиваются построением базисов (и даже просто систем образующих), которые удовлетворяют тем или иным требованиям.
Операция суперпозиции является, вообще говоря, неалгебра ической операцией. При изучении алгебр многоместных функций с операцией суперпозиции это обстоятельство доставляет определённые неудобства. В связи с этим А.И.Мальцевым были предло жены пять элементарных алгебраических операций : с&
иклическая перестановка аргументов, t - транспозиция іервнх двух аргументов, & - отождествление первых двух аргументов, V - введение первого фиктивного аргумента,
X - подстановка первой из двух функций на место первого аргумента второй функции, которые с содержательной точки зрели эквивалентны общей операции суперпозиции. Алгебры функций вида ( Р^ &,t, А, V, & > получили название итеративных алгебр.
Пусть /V = { 0,1,2..., J и Ек = (ОД к-1 }
при К ? 2 ( к 6 /V ). 'Ісрзз Р^» обозначим множество всех функций 5" А/ -> /V, п * 1,2.,... Аналогичным образом яри к ? 2 ( к & /У ) определяем множества РК. Все иногообразие дискретных функций, встречающихся в дискретной математике и математической кибернетике, нетрудно свести к двум типам: множеству Р^ и множествам PR. Множество Рд/ отвечает идее дискретных функций, заданных на бесконечном множестве; функции из Рд^ иногда называют функциями счёнозначной логики. Дискретным функциям, определённым на конечных множествах, соответствуй классы Рк функций к-значной логики.
Таким образом, проблема существования базиса в алгебрах дискретных функций с операцией суперпозиции может быть формализована как соответствующая проблема в подалгебрах итеративных алгебр
2, < k <
Необходимо отметить, что в соответствии со сложившейся традицией вопросы существования и построения базисов рассматривается не для подалгебр итеративной алгебры "fc^ , а для подалгебр так называемой предытеративной алгебры 1^-/^ - К "P^J ^"С, Д^ *У, которая отличается от алгебры фд/ отсутствием операции V введения фиктивного аргумента. Однако все результаты (включая результаты диссертации) без труда переносятся с алгебры "frfs на алгебру "fit/ .
Цель работы. Дія предытеративной алгебры (p/v цель состоит в определении качественной картины по проблеме существования базиса в подалгебрах алгебры ty^/ (особенно в подалгебрах рекурсивных функций). Имеется в виду исследовать вопросы существования конечных, счётных и континуальных базисов в общем случае и разработать методы построения конечных и счётных базисов для наиболее важных в прикладном отношении алгебр рекурсивных функций.
Для итеративных алгебр $к цель заклинается в том, чтобы описать важные для приложений подалгебры однородных и чётных функций и доказать существование конечного базиса в каждой из этих алгебр. На основе описания всех итеративных алгебр однородных и чётных функций дать классификацию конечных алгебр с полной симметической и знакопеременной группами автоморфизмов. Решить вопрос о существовании конечных базисов душ алгебр функций с циклической группой автоморфизмов.
Научная новизна. Впервые вопросы существования конечных базисов были рассмотрены в 1921 г. Э.Постом [jej для подалгебр предытеративной алгебры Ж^ . Э.Пост описал все подалгебры алгебры QJ. и указал конечные системы образующих в каждой из них. Аналогичные вопросы для некоторых классов
> примитивно рекурсивных функций (в диссертации им отвечают подалгебры в-п. алгебры JZ/v ) были сформулированы А.Іжегорчшсом р&З в 1953 г. Классы > образуют линейную иерархию множества всех примитивно рекурсивных функций. В 1964 г. Д.Рёддинг C20j доказал существование конечных систем образующих в классах ё> при ц,> 3. Впоследствии его решение в качественном отношении было значительно улучшено Ч.Пар-сонсом [дт] .
Таким образом, к началу 70-х годов в предытеративной алгебре 72^ были выделены достаточно богатые подалгебры %л примитивно рекурсивных функций и найдены конечные системы образующих в них. Довольно очевидно, что подучить сколько-нибудь удовлетворительное описание всех подалгебр алгебры (j^/v* (и даже всех подалгебр рекурсивных функций алгебры Тй^. ), имеющих конечные базисы, невозможно.
Поэтому в проблеме описания подалгебр алгебры "д?д, , имеющих конечные базисы, исследования ориетировались прежде всего на подалгебры с достаточно широкими и содержательно интересными носителями, подалгебры, наиболее часто встречавдиеся в математической практике. Реально речь здесь шла, конечно, об алгебрах рекурсивных или относительно рекурсивных функций. Довольно быстро определились требования на объём подобных алгебр: в них должны были входить простейшие рекурсивные функции 0 j х+1, х+у, ас- ур и канторовские нумерационные функции ССос,у"), tt*), t(xV Дш получения нетривиальных результатов по существованию конечных базисов нооиіели этих алгебр должны, разумеется, определяться в терминах, выходящих за рамка сигнатуры алгебры ^^ . При изучении алгебр рекурсивных функций таким пунктом определения естественным образом может служить какая-либо форма рекурсии. Эти соображения в совокупности с результатами А.Гжегорчика ЙО почти однозначно приводят к алгебрам, подобным алгебре (Л . К этому ещё следует добавить, что в работе СнЗ вопрос о существовании конечного базиса был сформулирован, в частности, для класса
Класс можно определить как наименьший класс функций, содержащий функции 0, («,«j) »х, O^OOj-t^ и замкнутый относительно операций суперпозиции и ограниченной рекурсии. Последнюю возьмем в следующей конструктивной форме В (исходная функция $ здесь зависит от п + 2, переменных):
= mln C*i, K*t «и, &, CB$X*i."vr*i, а)))-
_ к После данных определений вопрос о подалгебрах алгебры g< f/ ,
имеющих конечные базисы, естественно ставить лишь для подалгебр, носители которых содержат функции О, ЄС«,ЯЬ Сос-»*|(у+.) и замкнуты относительно операции В ограниченной рекурсии.
Такие носители мы называем & -замкнутыми, а соответствующие алгебры - -алгебрами, (р -алгебры формально можно рассматривать также в виде (_ $; *&,Х, Д ,%, В >., где носитель ё> содержит функции О, еС.Х/Й'», С^+^ОС Ч*0 (последнее "неалгебраическое" условие можно исключить, добавив в сигнатуру -алгебры три нульыестных операции).
В конце 60-х - начале 70-х годов несколькими авторами 2,21,7,22^ было замечено, что при условии Ь -замкнутости множества е> для конечной порождаемости предытеративной алгебры ^ $} 'Jj'TjA,^^ достаточно, чтобы в ё> входила "почти универсальная" функция V(. п, эс, у ) .В работе 7 3 она была названа максимально универсальной. Более точно, пусть fca. - множество всех одноместных функций из & , УГ — ~ &L' Функция Т/С^зс, ^) называется максимально универсальной для множества ^i относительно множества Tf, если для любой функции $-(^0 из $. найдутся такие число 1г и функция С^О из У , что для любой функции КС*-") из Р^/- из соотношения Ь(=с) * gC^^ следует, что
17(п, ж, A(x)J = Кэс).
В работе С.73 было доказано, что если в ё -замкнутом множестве S содержится такое конечное множество "УГ одноместных функций и такая функция "XT , что XT' является максимально универсальной для множества $>f_ относительно замыкания tyj множества If" по суперпозиции, то алгебра К. S } ^, fj Д, ^ является конечно порожденной. Наконец, в работе 35j автора исследования в этом направлении получили логическое завершение: был сформулирован и доказан критерий конечной порождаемооти (георема 4 главы I диссертации). Отметим, что в вопросах существования конечных базисов в подалгебрах алгебры $, этот критерий пока является единственным.
Полученный критерий не позволяет доказывать существование конечных базисов в конкретных алгебрах, он лишь переносит основные трудности в этом вопросе на построение максимально уни-
версальных функций. Сам метод построения максимально универсальных функции для предытеративных алгебр с 6 -замкнутым носителем бнл предложен автором в работах C2I.22]] . В отличие от работ Д.Рёддинга Ого] и Ч.Парсонса l73 , где использовалась идея некоторых "производящих" функций, метод работ
С21,221 можно назвать "машинным", поскольку он основан на арифметизации вычислений на некотором варианте машин Тьюринга. "Машинный" метод по области действия шире методов Рёдпинга-Парсонса; обязательным условием применения последних является наличие функций экспоненциального роста.
В теореме 5 главы I диссертации для произвольной конечно порожденной Ь -алгебры С &' S.t, Л1 %, В^> машинным методом устанавливается существование максимально универсальной функции (и подходящего конечного множества 'ЧГ ). Тем самым соответствующая предытеративная алгебра ( >> ,1, А, Я-*? также оказывается конечно порожденной. Вместе с теоремой 4 теорема 5 полностью решает вопрос о существовании конечных базисов в предытеративных алгебрах с ё> -замкнутыми носителями.
Какова связь между существованием конечного базиса в алгебре (|; «S.tj ^,^)1 и алгебре К. ё± і #^> ? Какое минимальное число функций может быть в базисах этих алгебр и от какого числа переменных (в первой из этих алгебр)? Ответы на эти вопросы были получены автором в публикациях C2I,22,35j . В диссертации данным вопросам посвящены теоремы I и 2 главы I.
В упомянутых выше результатах по построению конечных базисов в подалгебрах алгебры ^/у по существу эксплуатировались две идеи: идея "производящих" функций и идея универсальных функций. Вторая идея оказалась с более широкой областью применения, однако "явные" примеры конечных базисов основаны на первой идее. Методы построения конечных базисов до "качеству" получаемых базисов особенно удобно сравнивать на примере алгебры fa , носитель которой - класс функций, элементарных по Кальмару.
Класс 6 имеет большое число эквивалентных определений
и содержит практически все всюду определённые вычислимые функции, встречающиеся в реальной математической практике. Он интересен и с прикладной точки зрения, поскольку в нём легко ариф-метизируотся многие процессы, распространённые в дискретной математике и математичксой кибернетике: нумерация схем и формул, построение схем и формул с заданными свойствами, проверка конечных систем функций из Рк на полноту и т.д. В связи с этим получение конечного базиса в алгебре ^ имеет не только чисто теоретическое значение, но может быть использовано, например, для получения сложностных характеристик указанных процессов (см. по этому поводу работу зЗ ).
Первый результат Д.Рёддинга (j20j о конечной породдаемос-ти алгебры д представляет собой по существу чистую теорему существования. В явном виде система из 19 функций, порождающих алгебру &ь , была предложена Ч.Парсонооы ClTJ . Эта система не является базисом и, кроме того, половина функций системы имеет громоздкое, "многоэтажное" строение с одним или двумя операторами Zji$=t э Пі«а
Новые возможности в построении простых базисов в алгебре ^а открыло применение диофантовых и экспоненциально диофан-товых представлений рекурсивно перечисадашх предикатов. А. К. Виноградовым, Н.К.Косовским l3 и Л.Эддименом, К.Мандерсом СпЗ было замечено, что в диофантовых и экспоненциально диофантовых представлениях предикатов из класса ? переменные под кванторами существования можно ограничить подходящими функциями из того же класса & . Более того, эти функции можно выбрать среда суперпозиций функции Z * *~ Данные соображения вместе с некоторыми результатами теоретико-числового характера позволили автору трансформировать сравнительно несложные технические средства, используемые в диофантовых и экспоненциально диофантовых представлениях, в простые системы образующих алгебры #3 24,343 . Так, в работе [24 Д было доказано, что алгебру & з порождает система функций
{ x + i, ос*, эс— У, 'РСэс.Ч') Iv где при ас>1 значение ф(.х> ^) равно наименьшему номеру нулевого разряда в представлении ^ в позиционной системе с основанием X . Там же было установлено, что для порождения всех функций из & , принимающих лишь значения 0,1 ("предикаты" класса ) достаточно взять систему функций
$ ={ x+i, ос*, ж-*, CYij] J.
В работе СібЗ Дж.Джонса и Ю.В.Матиясевича найден ещё ряд ::cne*22tx систем функций, аналогичных по порожнаацим свойствам системе S
Продолжая далее развивать идеи работы 24 3 , автор в работе С343 доказал, что алгебру %ъ порождает каждая из систем функций
где <5(=0-число единиц в двоичном представлении 2С , а X С"*-*) равно показателю числа 2 в разложении X на простые множители, если эс > О , и ТСо") « С (теорема 6 и следствие I главы I диссертации).В доказательствах использовались результаты Ю.В.Матиясевича С5,бЗ об однократных экспоненциально диофантовых представлениях рекурсивно перечислимых предикатов. Полученные в работах lj24,34j результаты позволяют высказать гипотезу о том, что система 5 может служить некоторым естественным "пределом" для базисов алгебры &з Стоит также отметить, что конструкции и результаты работ С24, 343 свидетельствуют о глубокой всязи, имеющейся между "простотой" базиса алгебры &э и некоторыми логическими и теоретико-числовыми проблемами.
Переходя к алгебрам с бесконечными базисами, заметим, что уже сам вопрос о построении в алгебре ^F/v содержательно интересной подалгебры с бесконечным базисом является далеко не тривиальным. В 1959 году С.В.Яблонским СвЛ был указан пример
счётного множества » одноместных неограниченных функций, для которого алгебра <С > Л-^> имеет бесконечный базис. Подалгебру алгебры jjj^ со счётным базисом можно также получить, "спроектировав" из $з в ??ы известный пример Ю.И.Янова и А.А.Мучника СюЛ . Другой путь построения алгебр с бесконечными (и даже континуальными) базисами состоит в использовании конструкций из теории степеней неразрешимости. Все эти подходы, однако, приводят к искусственным примерам пре-.дытерагивных алгебр с бесконечными базисами. Они не позволяют ответить на вопрос о существовании бесконечных базисов в реально изучаемых в теории алгоритмов алгебрах рекурсивных функций.
Впервые построить бесконечный базис в некоторых хорошо известных алгебрах одноместных рекурсивных функций удалось автору в работе _25j . В дальнейшем существенно иными методами аналогичная проблема была решена автором и в алгебрах многоместных рекурсивных функций з2,35J . Было показано, что произвольная счётная подалгебра алгебры 7д/ с примитивно рекурсивно замкнутым носителем имеет счётный базис (теорема 7 главы I диссертации). Отказ от условия счётности здесь, вообще говоря, невозможен - алгебра T$-f/ > как хорошо известно, базиса не имеет. В связи с этими результатами возник естественный вопрос: а могут ли вообще несчётные подалгебры алгебры $.^ с достаточно богатыми носителями (например с примитивно рекурсивно замкнутыми) иметь базисы? Положительный ответ на этот вопрос получен автором в раооте 35Ц (теорема 8 главы I диссертации).
Таким образом, по проблеме существования базиса в подалгебрах алгебры ^2дг автором получены следующие результаты. Найдены широкие классы подалгебр алгебры ^у , в которых подалгебры имеют соответственно конечные, счётные и континуальные базисы. Установлено, что свойство иметь базис - конечный или бесконечный - для наиболее важных в прикладном отношении алгебр является скорее правилом, чем исключением. Описан широкий класс подалгебр (предытеративные редукты -алгебр),
для которых доказан единственный в этой области критерий существования конечных базисов. Предложен машинный метод построений конечных базисов в алгебрах, удовлетворяющих условиям критерия, который остаётся пока наиболее общим в данном направлении. В важной для приложений предытеративной алгебре &-3 указаны "самые простые" четырёхэлементные системы образующих, что позволяет получать, например, нетривиальные результаты о сложности вычисления некоторых арифметических функций. Впервые предложены методы построения счётных и континуальных базисов в реально встречающихся в теории алгоритмов предытеративных алгебрах рекурсивных функций. Наконец, также впервые получены некоторые общие результаты о числе функций в конечных оазисах и о количестве переменных в этих функциях, а также о связи между существованием базиса в алгебрах многоместных и одноместных функций. Все эти результаты позволяют утверждать, что в целом выявлена качественная картина по проблеме существования базиса в подалгебрах алгебры 79,у
Как отмечалось, вопросы конечной порождаемое подалгебр алгебры $ впервые начали разрабатываться Э. Постом Cl8j. В работе Ql9j завершены исследования, начатые в l8^ . описаны все подалгебры алгебры ~$ъ и доказана их конечная порождаемость. Современное изложение результатов Поста можно найти в книгах э,4J .
Та, во многом уникальная ситуация, которая имеет место для алгебры 7j2jj, , совершенно меняется при переходе к алгебрам gZk , к ?чЗ . Как установили Ю.И.Янов и А.А.Мучник, уже алгебра Q2j содержит континуальное число подалгебр, среди которых имеются как подалгебры со счётным базисом, так и подалгебры, не имеющие базисов вообще. В связи с этим для алгебр Q? у , W Ъ Z_, на первый план выдвинулась задача описания конечно порожденных подалгебр. К настоящему времени никакого удовлетворительного описания таких подалгебр не получено. Известно лишь несколько серий подалгебр с конечными базисами. Среди них часть максимальных подалгебр (при 3 * k s ? ~ все максимальные подалгебры, но уже при к = 8 - нет), алгебры
линейных ло простому модулю функций, алгебры, содержащие полиномы по модулю к , часть алгебр квазилинейных, самодвойственных и "предикатных" функций в Рд и некоторые другие.
На этом фоне заметно выделяются алгебры однородных функций. Б отличие от .других алгебр исследования по проблемам существования базиса и полноты для алгебр однородных фушащй по существу удалось довести до конца.
Согласно Е.Марчевскому Cl6j , алгебра ^Е; иУ называется однородной, если её группа автоморфизмов является полной симметрической группой подстановок на множестве Е. В частности, функция '. Еп-> Б называется однородной, если однородна алгебра ^Ъ; { 5 І У .В другой терминологии функция называется однородной, если она самодвойственна относительно любой подстановки множества Е.
В универсальной алгебре однородным алгебрам посвящена довольно обширная литература. Отметим лишь один результат Б.Ча-каня: если нетривиальная (содержащая неселекторные операции) конечная однородная алгебра не эквивалентна ни одной из восьми фиксированных однородных алгебр, то при соотвествупцем к её операции вместе с константами ОД,..., к-I порождают всю алгебру ^ic . Этот результат открывает большие возможности при построении различных базисов в алгебре ^2^ .
Итеративные алгебры однородных функций естественным образом появляются при классификации алгебр с заданной группой автоморфизмов, в частности, с полной симметрической группой. Именно, классифицировать алгебры ^Е; 1>У с группой автоморфизмов Г можно, например, по типам изморфизма. Однако уже в самом простейшем случае ( | Е | =2, Г - полная симметрическая группа) число таких типов оказывается континуальным. Поэтому Г.Гретцер предложил считать алгебры
{Е; йі{) , ^Ejt&^ эквивалентными, если совпадают клоны, порождённые множествами операций Sit и Slj . Иными словами, если 2 = и Є(=^) = tc , то алгебры
< Е; Лі) , ^ E; Ла) эквивалентны, если совпадают подалгебры, порождённые в предытеративной алгебре ^J?k = = ^Р ; ,Т, Д, *У множествами At u^e$
Л а о {ej . Таким образом, классифицировать алгебры ( Ej^; Л ^ о точностью до введённого отношения эквивалентности - значит описывать подалгебры алгебры $? ^ , содержащие селекторную функцию 6 . После небольшого обобщения мы приходим к следующей проблеме для итеративных алгебр
Пусть Г - группа подстановок на Ед, Иг - множество всех таких функций из Р„, что Г содержится в группе
, /„ *!г1Ч „_ „__. .
аВТОМОрфИЗМОВ алгеоры \ IX.; I 1 J f ±1±ллишма uuonmj. a
описании всех подалгебр итеративной алгебры Чдг =-
Если Л - единичная группа, то /т^ = Рк. Случай к = 2, как отмечалось выше, полностью исследован Э.Постом.
Пусть О ^ — полная симметрическая группа подстановок на Ejj. Тогда %Su; - итеративная алгебра однородных функций из Р„. В связи изучением замкнутых классов самодвойственных функций к-значной логики в работе 22~] автора были полностью описаны все подалгебры алгебры ySx Почти одновременно Б.Чакань и Т.Гавалцова [^I2j начали исследования по классификации конечных однородных алгебр. При этом всё по существу свелось к описанию подалгебр итеративной алгебры *Д$ь В работе JJCJJ путём построения базисов было указано 6 подалгебр в. алгебре ^ Sa > 8 подалгебр в алгебре %$± и 2к-1 подалгебр в алгебре ^sjc Ч?и к 5 5. Однако даже в случае к = 3 исследования в {jzj не были доведены до конца. Более того, одно из основных утверждений работы [Д23 - теорема 2 содержала ошибку. Полное описание всех подалгебр итеративных алгебр %$± ^ к*к, с указанием конечных базисов принадлежит автору П"26,27Д .
Доказано, что алгебра %$л содержит, включая саму алгебру % g3 , ровно 8 подалгебр, алгебра ^ g4 - 14 подалгебр и алгебра $f.. ПРИ к ^ 5 - ровно 4к-3 подалгебр (теорема 2 главы П диссертации). Каждая из подалгебр
алгебры % &ь ' ^ * ^* охарактеризована некоторым свойством. Во всех алгебрах однородных функций указаны конечные базисы и определены порядки алгебр (минимальное число Z , для которого существует базис, состоящий из функций от не более чем Ъ аргументов). Таким образом, оказалось, что для любого к, к ^ 3, любая однородная алгебра вида К ^g} SL У (вообще говоря, с бесконечным множеством операций St ) эквивалентна одной из конечного числа (при данном k ) конечных однородных алгебр. Тем самым решена проблема классификации однородных алгебр с конечными носителями.
Следующий шаг по изучению итеративных алгебр вида % г был сделан автором для знакопеременной подгруппы Ад группы
Sk 28,29,33j Во-первых, с помощью построения алгебр со счётным базисом удалось доказать, что алгебра %АЛ со~ держит континуальное число подалгебр 28,29J . Сднако гораздо более важный факт заключается в том, что при любом к, к > ? 4, алгебра %Aw содержит лишь конечное число подалгебр 28,33 J . Именно, при к = 4 отличных от алгебр однородных функций их имеется ровно 20, а при к? 5 - 8к-П В каждой подалгебре алгебры % д h , к > &, был найден конечный базис и вычислен порядок алгебры (теорема 3 главы П диссертации). Таким образом, при к > 4 эффективно решена проблема классификации алгебр ^ Ej^; h У со знакопеременной группой автоморфизмов.
При дальнейшем продвижении в этом направлении возникает
естественный вопрос: для каких подгрупп f группы о fc
возможно такое же описание всех подалгебр алгебры ъ^р ,
какое получено для алгебр %tk и %Ак 7В частности, для каких подгрупп Г итеративная алгебра Ц*г содержит конечное число подалгебр ? Полного решения указанной проблемы пока не найдено. Примерно в одно и то же время Я.Деметровичем, Л.Ханнаком l3J и автором 23J были получены близкие результаты по алгебрам %р с циклической группой Г В них для ряда групп получалось, что итеративная алгебра
%„ содержит континуальное число подалгебр. Окончательно этот вопрос для итеративных алгебр %г с циклической
группой Г был решён автором С^эЛ : для любой циклической подгруппы Г группы Sk . к > 3, итеративная алгебра ду содержит континуальное число подалгебр (теорема 4 главы П диссертации). В частности, как отмечалось выше, континуальное число подалгебр будет содержать алгебра ^А3 Доказательство этих утверждений опирается на построение подалгебр со счётным базисом.
Результаты автора из Г29Д завершают цикл исследований ещё по одной проблеме, изучавшейся в литературе. Речь идёт об определении числа "9((?И всех подалгебр итеративной алгебры
Л7 . , (Ті --- - "Л.
Дело в том, что, как хорошо известно Cl3 » значение ^CTpV^ континуально при любом к, к > 3. В связи с этим возник вопрос о распределении "континуума" среди максимальных подалгебр алгебры ~$\z . Усилиями цояого ряда исследователей (Я.Бадышский, Я.Демтрович, Д.Лау, А.Саломаа, А.Сендрей, Л.Хан-нак) величина ^(.ОЪ) была определена для всех типов максимальных подалгебр алгебры "^р w за исключением типа У^г , когда Г есть циклическая группа. Как доказал автор С*29Х в этом, технически самом сложном случае, $( %р) также есть континуум.
Результаты по итеративным алгебрам gs^ и %Лк позволили выдвинуть гипотезу о том, что наличие в итеративной алгебре неселектороной однородной функции может обеспечить конечную порождаемость соотвествувдей алгебры. Впервые в общей постановке этот вопрос исследовался автором в работе СзіЗ Оказалось (теорема 5 главы II диссертации), что для подалгебр алгебры із это так: всякая подалгебра алгебры ^fj , содержащая неселекторную однородную функцию, имеет конечный базис. Напротив, при любом к, к 3 4, в итеративной алгебре
$2 к имеется континуальное число подалгебр, кавдая из которых содержит фиксированную однородную функцию Efc . Среди этого континуального множества алгебр есть как алгебры со счётным базисом, так и алгебры без базиса.
Методы исследований. Для предытеративкой алгебры 1$t/ и итеративных алгебр ф? к методы исследований существенно различны.
Для подалгебр алгебры ^2^ характерны методы теории рекурсавных функций. Методы, которые используются в диссертации, можно разбить на четыре группы: метод универсальных функций, метод производящих функций, метод быстрорастущих функций и методы теории степеней неразрешимости.
Метод универсальных функций широко используется в теории рекурсивных функций. Нередко он выглядит как метод (равномерного) моделирования одних вычислительных устройств другими вычислительными устройствами. При этом обычно моделирующие вычислительные устройства оказываются мощнее моделируемых вычислительных устройств. Б диссертации при построении конечных базисов в предытератавных алгебрах с & -замкнутыми носителями рассматривается иная ситуация: классы моделирующих и моделируемых устройств совпадают. Чтобы для всюду определённых функций не получить противоречия, моделирование проводится не "до конца". Это позволяет получившейся вариант универсальной функции использовать в качестве основного элемента в конечном базисе алгебры. Данный подход, впервые предложенный автором, и составляет суть "машинного" метода построения конечных базисов в подалгебрах алгебры ~$# с ё> -замкнутыми носителями. Отметим, что до настоящего времени "машинный" метод построения конечных базисов остаётся самым общим по области применения.
Идея применения производящих функций при построении базисов в алгебре з принадлежит Д.Рёдпингу С^оЗ и Ч.Парсон-су С^^З Автор при исследовании алгебры fc-*, объединил эту идею с диофантовыми и особенно с экспоненциально диофанто-выми представлениями рекурсивно перечеслшшх предикатов.
Идея быстрорастущих функций в теории рекурсивных функций применяется, как правило, для доказательства невхождения одного класса функций в другой. В диссертации быстрорастущие функции используются при построении бесконечных базисов как счётных, так и континуальных. Основная задача, решаемая с помощью
быстрорастущих функций, - обеспечить независимость счётного базиса и меньшей степени - независимость континуального базиса. Эта цель достигается специальным выбором "скоростей" возрастания быстрорастущих функций, чтобы ни одна из содержащихся в базисе быстрорастущих функций в целом не мажорировала никакую другую. Такой подход в построении бесконечных базисов в подалгебрах алгебры Q?^ впервые предложен автором.
Методы, применяемые в диссертации при изучении подалгебр итеративных алгебр ^Pfc , довольно характерны для этой области. Основная часть исследований здесь проводится по следующей схеме: в рассматриваемой подалгебре OL алгебры fi?tc строится базис, затем определяется конечное множество собственных попарно не сравнимых по включению подалгебр и доказывается теорема о полноте: система функций алгебры №> порождает алгебру Ol/ , если она целиком не содержится ни в одной из определённых подалгебр алгебры Ob . Тем самым указанные подалгебры алгебры 01* оказывается всеми её максимальными подалгебрами. Далее описанный процесс применяется к каждой из максимальных подалгебр алгебры Ob .
Иной подход используется лишь при изучении алгебр, имеющих циклическую группу автоморфизмов. Основная трудность здесь заключается в построении счётного базиса в некоторой подалгебре алгебры QJw , все функции которой самодвойственны относительно подстановок заданной циклической группы. В построении применяются некоторые приёмы, характерные для дизъюнктивных нормальных форм булевых функций.
Апробирование и публикации. Результаты диссертации излагались на Международном конгрессе математиков (Варшава, 1983), международной конференции по универсальной алгебре и многозначной логике (Сегед, 1979), на советско-германский семинарах по дискретной математике и математичкекой кибернетике (Йена, 1982 и 1986), в Международном математическом центре им. С.Банаха (Варшава, 1987), на У и УІ Всесоюзных конференциях до математи-
ческой логике (Новосибирск, 1979 и Тй<илиси, 1982), на I и П Всесоюзных конференциях до прикладной логике (Новосибирск, 1985 и 1988), на УП Всесоюзной конференции по теоретической кибернетике (Иркутск, 1985), на Всесоюзном семинаре по дискретной математике (Москва, 1984), на семинарах до кибернетике под руководством члена-корреспондента АН СССР С.В.Яблонского в МГУ, на семинарах по теории алгоритмов под руководством члена-корреспондента АН СССР Ю.Л.Ершова в Институте математики СО АН СССР, а также на некоторых других конференциях и семинарах.
Результаты диссертации опубликованы в работах *2I-35j .
Структура и объём работы. Диссертация состоит из введения, двух глав, заключения и списка литературы. Первая глава разбита на 5 параграфов, вторая - на 4. Объём работы 231 страница, включая 8 страниц цитированной литературы. В списке литературы 81 наименование.