Шкалы потенциалов вычислимости n-элементных алгебр тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

Журков Сергей Валерьевич

Шкалы потенциалов вычислисмости п-элементных алгебр

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

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

Иркутск-2003

Работа выполнена в Новосибирском государственном техническом университете

Научный руководитель:

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

Официальные оппоненты:

доктор физико-математических наук, профессор Перязев Николай Алексеевич

кандидат физико-математических наук, доцент Дулатова Зайнеп Асаналиевна

Ведущая организация:

Московский государственный университет им. М.В.Ломоносова

Защита состоится 19 сентября 2003 г. в 16 часов на заседании диссертационного совета Д 212 074.01 в Иркутском государственном университете по адресу: 664003, г.Иркутск, бульвар Гагарина, 20.

С диссертацией можно ознакомиться в библиотеке Иркутского государственного университета (бульвар Гагарина, 24).

Автореферат разослан 11 2003 г.

Ученый секретарь

диссертационного совета, Аргучинцева

к.ф.-м.н., доцент /у^Г ' Маргарита Александровна

2-0 05- д

Общая характеристика работы

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

Для любой алгебры 21 = (Л; а) через 6Т(21) обозначим да-

'Пинус А Г. Об условных термах и тождествах на универсальных алгебрах // Вычислительные системы. - 1996 - Вып. 156 - С.59-78.

^Пинус А Г. Условные термы и их применение в алгебре и теории вычислений // Успехи матем. наук. - 2001. - Т56, №4. - С.35-72, Пинус А Г. Условные термы и их применение в алгебре и теории вычислений. - Новосибирск, Иэ-во НГТУ, 2002; Пинус А.Г. Программно вычислимые функции на универсальных алгебрах // Математические вопросы кибернетики. - М., Физматлит, 2001. -

рос. национальная

БИБЛИОТЕКА С.Петербург ¡га п

оэ зом акУ/С 7

лее совокупность всех условно термальных функций алгебры Я. В работе А.Г.Пинуса было доказано, что для конечных алгебр Я = (А; сгх), 93 = (В;сг2) и для биекции 7Г множества А на множество В следующие условия эквивалентны3:

а). Имеет место равенство (включение):

тг-1СТ(«8)тг = СТ(Я) (тг-'стх»)* С ст(я)).

б). Имеют место равенства (включения):

т(5«6(Я)) = 5чЬ(®), тГ1/«^»)» = /яо(Я) (тг(5ы6(Я)) С 5иЬ(«), *_1/во(!В)1г Э /во(Я)).

Здесь 5'г4Ь(21) - совокупность всех подалгебр алгебры 21, ./зо(Я) - совокупность всех внутренних (между подалгебрами) изоморфизмов алгебры 21. Алгебры Я и удовлетворяющие данным условиям, называются условно рационально эквивалентными. В силу замеченного выше, условно рационально эквивалентные алгебры Я и Ш (то есть алгебры, для которых совокупности функций СТ(Я) и СТ(ОЗ) совпадают по модулю их сопряжения некоторой биекцией ж между основными множествами алгебр Я и 03) естественно рассматривать как алгебры, обладающие одинаковым вычислительным потенциалом. Таким образом, пара (ймЬ(Я); /во(Я)) выступает в роли инварианта вычислительного потенциала конечной универсальной алгебры Я. Это позволяет ставить вопрос о числе потенциалов вычислимости п-элементных алгебр (п е ш) и изучать сравнительную силу подобных вычислительных потенциалов.

Будем далее считать, что рассматриваемые п-элементные алгебры заданы на основном множестве {0,1,..., п— 1}. На совокупности СТ(п) = {СТ(Я)|Я - п-элементная алгебра} введем отношение эквивалентности СТ(Я}) ~ СТ(Яг) тогда

3Пинус А Г. Исчисление условных тождеств и условно рациональная эквивалентность // Алгебра и логика. - 1994. - Т.37, №4. - С 432-459.

и только тогда, когда алгебры 21х и 21г условно рационально эквивалентны, то есть существует перестановка тг множества {0,1,..., п— 1}, которая сопрягает совокупности функций СТ(91\) и СТ(ркъ). Через СТп обозначим фактор-множество СТ(п)/ Таким образом, мощность множества СТп соответствует числу попарно условно рационально не эквивалентных п-элементных алгебр, то есть числу п-элементных алгебр, имеющих различный вычислительный потенциал. Обозначим \СТп\ через 5(п). На СТп введем отношение порядка индуцированное отношением теоретико-множественного включения между элементами из СТ{п) при факторизации по отношению Частично упорядоченное множество (СТ„; назовем шкалой потенциалов вычислимости п-элементных алгебр.

Заметим, что изучение шкалы потенциалов вычислимости п-элементных алгебр определенным образом связано с изучением решетки клонов функций на п-элементном множестве п — {0,...,п — 1}. Действительно, пусть Т(21) является совокупностью всех термальных функций п-элементной алгебры. Тогда отображение <р(Т(Щ) = СТ(Ш)/ ~ является монотонным отображением решетки клонов функций на множестве п на шкалу {СТп\ Хорошо известно также равенство СТ(Щ = Т(И<<), где 21^ есть обогащение алгебры 21 добавлением в ее сигнатуру функции трехместного дискриминатора ¿(х, у, г). Таким образом, если Д, = Т(2^), где 21^ = (п; й), то указанное выше отображение разлагается в суперпозицию двух монотонных отображений <р' и </>", где <р'{Т(21)) = Т(21й) есть монотонное отображение решетки клонов функций на множестве п на фильтр [Д,; этой решетки (здесь Рп - совокупность всех функций на множестве п), а </э"(Т(21<')) = СТ(21)/~ - монотонное отображение фильтра [/)п; /у на шкалу {СТ„; <). Заметим также, что в отличие от классификации п-элементных алгебр, основанной на совпаде-

нии клонов их термальных функций (напомним, что в силу результата Е. Поста число таких различных клонов на двухэлементном множестве счетно4, а, в силу результата Ю.И.Янова и A.A.Мучника, на n-элементном множестве при п > 3 - континуально5), классификация n-элементных алгебр по их вычислительным потенциалам конечна (число различных вычислительных потенциалов таких алгебр не превышает числа попарно не сопряженных полугрупп внутренних изоморфизмов алгебр, заданных на множестве {0,..., п — 1}).

А.Г.Пинусом была получена следующая оценка числа S(n) попарно условно рационально не эквивалентных п-элементных алгебр: для любого натурального п ^ 4

А.Г.Пинусом также были посчитаны числа S(n) для малых п: S(2) = 5, 5(3) = 53. В приватном сообщении П.Джипсена указано, что им с помощью компьютера получено равенство 5(4) = 22610.

В силу сказанного изучение строения шкалы потенциалов вычислимости n-элементных алгебр определенным образом близко к изучению решеток клонов функций на конечных множествах, результаты исследования которых можно найти в целом ряде работ. См., в частности, работы Е.Поста, Ю.И.Янова и А.А.Мучника, С.В.Яблонского, Г.П.Гаврилова, В.Б.Кудрявцева, И.Розенберга, С.С.Марченкова, А.СендреЙ и др. В то же время изучение шкал потенциалов вычислимости п-элементных алгебр по сравнению с изучением решеток клонов имеет более естественное обоснование с точки зрения изучения программных вычислений и более продуктивный подход в виде наличия довольно обозримого инварианта (Sub(%1); /бо(21))

<Post EL. The Two-Valued Iterative Systems of Mathematical Logic // Princeton, Princeton Univ. Press, 1941

5 Я мои Ю И., Мучник A.A. О существовании Л-значных замкнутых классов, не имеющих конечного базиса // Докл. АН СССР. - 1959 - Т.127, №1. - С.44-46.

для потенциала вычислимости алгебры 21. Исследование строения шкал (СТп; и представляет предмет исследования диссертации.

Цели исследования.

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

- нахождение параметров шкал потенциалов вычислимости га-элементных алгебр.

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

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

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

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

Апробация работы. Результаты диссертации были представлены на международной конференции "Соответствия Га-луа" (Потсдам, 2001), 4-й международной школе "Пограничные вопросы универсальной алгебры и теории моделей" (Эрла-гол, 2001), международной конференции "Мальцевские чтения" (Новосибирск, 2002), международной конференции "65 рабочая встреча по общей алгебре" (Потсдам, 2003), семинаре МГУ "Математические вопросы кибернетики", семинаре ИрГУ по дискретной математике, 5-й международной школе "Пограничные вопросы универсальной алгебры и теории моделей" (Эрлагол, 2003).

Публикации. По теме диссертации опубликованы работы {1]-[6], отражающие ее основные результаты.

Структура и объем работы. Диссертационная работа изложена на 95 страницах и состоит из введения, пяти глав, а также списка литературы, содержащего 30 наименований, включая работы диссертанта.

Содержание работы

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

В первой главе определяются базовые понятия и терминология, принятая при изложении результатов, а также приводится обзор основных результатов универсальной алгебры и, в частности, теории условных термов, необходимых при доказательстве основных результатов диссертации. Пусть =* обозначает обычное равенство, а =° - его отрицание. Условием сигнатуры сг будем называть конечную совокупность Т(ж) равенств и неравенств вида

'«К®) ='' *?(*)

где Ц(х) - термы сигнатуры <т, а ^ € {0,1}. Полной системой

условий сигнатуры а будем называть набор {1\(х),...,

к

условий данной сигнатуры такой, что формула Ух(\/&%(х))

»=1

является тождественно истинной и для различных 1,тп ^ к формулы к.%{(¿с)&&Хт(ж) невыполнимы.

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

а) любая переменная или константа сигнатуры а является условным термом;

б) если ¿1(5),... - условные термы сигнатуры а и /(®1, • • ■ ,х„) - функциональный символ, входящий в а, то /(¿[(т),..., 1п(х)) - также условный терм сигнатуры

в) если ^(х),..., ^,(5) - условные термы сигнатуры а, а {Т1 (ж),..., 1п(х)} - полная система условий этой сигнатуры, то

,%г{х) tn{x) также является условным термом сигнатуры а\

г) любой условный терм сигнатуры а строится за конечное число шагов по правилам а)-в).

Определим теперь семантику условных термов сигнатуры а, то есть функции на алгебрах данной сигнатуры, вычислимые с помощью условных термов; при этом не будем делать формальных различий в обозначениях условного терма и соответствующей ему функции на алгебре 21 сигнатуры а. Для правил а), б) из определения условного терма предполагаем стандартные интерпретации, имеющие место при интерпретации термов сигнатуры а на алгебрах этой сигнатуры. Если же условный терм t(x) построен по правилу в), то для любых элементов а из алгебры 21 (соответствующих переменным х условного терма t(x)) положим 211= <(а) = 6, если для некоторого i ^ п имеет место Ш (== 2J,(a) и 21 (= i,(a) = b. Функции, определимые на алгебре 21 с помощью условных термов, будем называть условно термальными функциями.

Кроме того, в первой главе определяются основные объекты исследования диссертации: шкалы потенциалов вычислимости и потенциалов элементарной вычислимости n-элементных алгебр.

Вторая глава посвящена выяснению основных свойств шкал потенциалов вычислимости n-элементных алгебр и нахождению основных параметров этих шкал.

Выше уже отмечалось, что шкала (СТ„; есть конечное частично упорядоченное множество, являющееся монотонным образом решетки клонов функций на множестве п. Прежде всего доказывается

Утверждение 2.1. Элементарная теория класса Зк — {{СТп\ € и>} неразрешима.

Это утверждение является обоснованием постановки всех последующих рассмотренных в диссертации вопросов. В случае разрешимости элементарной теории класса вк все дальнейшие вопросы строения любой из шкал {СТп\ решались бы одним алгоритмом, разрешающим истинность предложений логики первого порядка на классе 5/г.

Следующее утверждение указывает на возрастание сложности строения шкалы {СТп\ с ростом параметра п:

Утверждение 2.2. Для любых тп < п шкала {СТт; является регпрактом шкалы (СТ„\ Более того, существуют интервал [а; ¿>] гикалы (СТп; и эпиморфизм (р шкалы (СТ„; на интервал [а; 6] такие, что (р тождественен на [а; 6], и интервал [а;Ь] изоморфен гикале (С'Гт\

Для п = 2,3 найдено явное строение шкал (СТ?, и (СТ3; Приведенное выше равенство \СТ^\ — 22610 указывает на невозможность подобного подхода к описанию строения шкал (СТп-, при п ^ 4.

Выше уже указывалось, что шкала (СТ„; является монотонным образом решетки клонов функций на множестве п. Однако сама шкала {СТп; решеткой не является.

Утверждение 2.3. При п > 3 гикала {СТп; <) не является ни верхней, ни нижней полурешеткой.

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

Теорема 2.1. Для любой конечной решетки Ь существует натуральное п и элементы шкалы (СТп; та-

кие, что Ь как решетка вложима в интервал шкалы {СТ„; являющийся решеткой.

О сложности строения шкал (СТп; говорит и следующий результат:

Утверждение 2.4. Графы, соответствующие диаграммам Хассе шкал {СТ„; не являются плоскими при п ^ 3.

К важным характеристикам шкал (СТп\ относятся числа их атомов и коатомов:

Теорема 2.2. Число атомов шкалы {СТп\ равно [|] + 1 + где Л(п) - число максимальных транзитив-

ных на п подгрупп полной симметрической группы па п, попарно не сопряженных в этой группе. Число коатомов равно (п — 1) + К(п), где К(п) - число различных простых делителей числа п, отличных от единицы.

Найдены также длины шкал (СТп\ (максимальные длины цепей в частично упорядоченных множествах (СТ„;

Теорема 2.3. Длина шкалы потенциалов вычислимости п-

элементных универсальных алгебр равна

п

£C^m + 2n+1-2n-2,

т=2

где 1п — — £ ((?] m°d 2). В частности,

d((CT2- <)) = 3,d«CT3; 13, d{(CTi\ О) = 40.

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

Следствие 2.1. Длина интервала [Д,; Fn] в решетке клонов функций на п-элементном множестве равна

п

]TC™Zm + 2"+1-2n-2

m=2

Следствие 2.2. Длина максимальной цепи инверсных подполугрупп инверсной полугруппы Bi(n) (полной инверсной полугруппы биекций между подмножествами п-элементпого множества) равна

п m=2

В третьей главе ставится вопрос об автоморфизмах шкал {СТп\ и доказывается неподвижность относительно автоморфизмов естественным образом выделяемого фильтра I шкалы (СТп; Алгебру 51 назовем жесткой, если ее единственными внутренними изоморфизмами являются тождест-

венные отображения ее подалгебр на себя. Совокупность потенциалов вычислимости всех п-элементных жестких алгебр образует фильтр I = {СТ(21)/~ |21 - жесткая п-элементная алгебра} в шкале (СТ„;

Для любой п-элементной алгебры 21 через 2( обозначим точку СТ{Щ/ ~ шкалы (СТ„; «$).

Теорема 3.1. Для любого автоморфизма ■ф шкалы (СТп; для любой точки 21 € I имеет место равенство € /.

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

Утверждение 4.1. Для любой конечной алгебры 21 существует алгебра 21' сигнатуры, состоящей из одной функции, такая, что СГ(21) = СТ(21')-

В связи с этим естественно рассмотрение ограничений на местность сигнатурных функций. Дальнейший материал четвертой главы посвящен изучению строения шкал потенциалов вычислимости алгебр, сигнатура которых включает лишь одноместные функции, (унаров) (СТ^;^). Здесь СТ,\ = {СТ(21)/~ |21 - п-элементный унар}. Найдено явное строение шкал (СТ^1; <) и (СТ%\<}:

Утверждение 4.2. Любой двухэлементный унар условно рационально эквивалентен одной из четырех попарно условно рационально не эквивалентных алгебр ®х,..., 2$4. Любой трехэлементный унар условно рационально эквивалентен од-

ной из четырнадцати попарно условно рационально не эквивалентных алгебр 12(1,..., 21м-

Найдены числа атомов и коатомов шкал {СТ

Теорема 4.1. а). Количество коатомов шкалы (СТ„\ равно

К(п) + п- 1,

где К(п) - количество простых делителей п, отличных от единицы.

б). Количество атомов шкалы (СТ.¡|; равно ¿=1 1=1

где И (г) - число делителей числа г, отличных от единицы, Т- - количество представлений числа г в виде не более чем ненулевых натуральных слагаемых.

Доказан ряд утверждений о сложности строения шкал

Утверждение 4.3. При п > 3 шкала (СТ*; не является ни верхней, ни нижней полурешеткой.

Утверждение 4.4. Для любых т < п шкала (СГД; является ретрактом шкалы (СТ*;

Утверждение 4.5. Для п ^ 3 шкала (СТ„\ не может быть представлена в виде планарного графа.

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

риации понятия условия в определении условного терма - замена конечной системы равенств и неравенств между термами нй формулы логики 1-го порядка. Подобный подход к так называемым элементарным условным термам изложен А.Г.Пи-нусом6. В частности, А.Г.Пинус доказал, что роль инварианта для совокупности 2?СТ(21) элементарно условно термальных функций алгебры 21 играет роль пара (5и6(21); 21)), где АЫ(21) - группа автоморфизмов алгебры 21. Аналогично определению шкалы {СТ„; на основе совокупности функций СТ(21) определяется шкала потенциалов элементарной вычислимости п-элементных алгебр на основе совокупности функций ЕСТ(21). В главе 5 найдено явное строение шкал (ЕСТг;^) и (ЕСТз\ Доказана правомерность рассмотрения частных вопросов строения шкал {ЕСТп\

Утверждение 5.1. Элементарная теория класса ЕБк неразрешима.

Здесь ЕБк = {(ЕСТп; € и>}.

Показано возрастание сложности строения шкал {ЕСТп\ с ростом п.

Утверждение 5.2. Для любых тп < п шкала (ЕСТт; является ретрактом шкалы (ЕСТп; Более того, существует интервал [а; Ь] шкалы (ЕСТп\ и эпиморфизм (р шкалы (ЕСТп\ на интервал [а; 6] такие, что <р тождественен на [а;£>], и интервал [а; 6] изоморфен шкале (ЕСТт\

Имеет место ряд аналогий в строении шкал {СТп\ и (ЕСТп;^):

вПинус А.Г п-элементная вложнмость и н-условные термы // Изв. вузов Математика. - 1999. - №1. - С 36-40.

Утверждение 5.3. При п ^ 3 шкала (ЕСТп\ не является ни верхней, ни нижней полурешеткой.

Теорема 5.1. Для любой конечной региетки Ь существует натуральное п и элементы и Р^/~ шкалы (ЕСТп;

такие, что Ь как решетка вложима в интервал шкалы (ЕСТп\ являющийся решеткой.

Утверждение 5.4. Графы, соответствующие диаграммам Хассе шкал (ЕСТп\ не являются плоскими при п ^ 3.

Теорема 5.2. Число атомов и коатомов шкал (СТп; и (ЕСТп-, совпадает.

Теорема 5.3. Длина шкал (ЕСТп\ равна 1п + 2" — 2.

Для любой п-элементной алгебры 21 через 21 обозначим точку ЕСТ{21)/ ~ шкалы (ЯСГП;

Теорема 5.4. Для любого_ автоморфизма ф шкалы (ЕСТпдля любой точки 21 6 Е1 имеет место включение ф(Щ е Е1.

Здесь фильтр Е1 шкалы (ЕСТп; определяется точно так же, как и фильтр I шкалы (СТ„\ а именно: Е1 = {ЕСТ(21)| 21 - жесткая п-элементная алгебра }.

Основные результаты работы

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

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

3. Исследованы вопросы, связанные с автоморфизмами шкал потенциалов вычислимости п-элементных алгебр. Доказана неподвижность фильтров жестких алгебр шкал потенциалов вычислимости п-элементных алгебр.

4. Исследовано строение шкал потенциалов вычислимости п-элементных унаров.

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

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

1. Журков C.B. О шкалах потенциалов вычислимости п-эле-ментных унаров / С.В.Журков // Препринт. - Новосибирск: из-во НГТУ, 2003. - №1. - 14 с.

2. Журков C.B. О неподвижности фильтров жестких алгебр шкал потенциалов вычислимости п-элементных алгебр / C.B.Журков // Препринт. - Новосибирск: из-во НГТУ, 2003. - №2. - 23 с.

3. Журков С.В. Некоторые замечания о шкалах потенциалов вычислимости n-элементных алгебр / А.Г.Пинус, С.В.Журков // Алгебра и теория моделей-3. - Новосибирск: из-во НГТУ, 2001. - С.107-113.

4. Журков С.В. О длине шкал потенциалов вычислимости n-элементных алгебр / А.Г.Пинус, С.В.Журков // Сибирский матем. журнал. - 2002. - Т.43, Jf«4. - С.858-863.

5. Журков С.В. О шкалах потенциалов вычислимости универсальных алгебр / А.Г.Пинус, С.В.Журков // Математические модели в информатике: Вычислительные системы. - 2002. - Вып.169. - С.26-38.

6. Zhurkov S.V. On the scales of computability potentials of n-element unars / S.V.Zhurkov // Abstracts of 65th Workshop on General Algebra. - Potsdam, 2003. - P.36-37.

Подписано в печать 01.08.2003. Формат 60x84 1/16 Бумага офсетная. Тираж 100 экз. Печ.л. 1.25 Заказ № 420

Отпечатано в типографии Новосибирского государственного технического университета 630092, г. Новосибирск, пр К.Маркса, 20

}

fl308 1

Введение.

1 Основные понятия и необходимые сведения из универсальной алгебры

2 Строение шкал потенциалов вычислимости п-элементных алгебр

2.1 Основные свойства шкал потенциалов вычислимости г?,-элементных алгебр

2.2 Основные параметры шкал потенциалов вычислимости п-элементных алгебр.

3 Автоморфизмы шкал потенциалов вычислимости п-элементных алгебр

4 Шкалы потенциалов вычислимости гг-элементных унаров

5 Шкалы потенциалов элементарной вычислимости п-элементных алгебр

Одной из возможных прикладных трактовок понятий универсальной алгебры и терма сигнатуры этой алгебры является следующая - на некоторой совокупности объектов, основном множестве универсальной алгебры, заданы некоторые стандартные (будем далее называть их простейшими) программы преобразований, вычислений, соответствующие сигнатурным функциям данной универсальной алгебры. Тогда понятие терма сигнатуры этой алгебры можно рассматривать как некоторую программу преобразований, вычислений на основном множестве, составленную из простейших (сигнатурных) программ с помощью лишь оператора суперпозиции. Однако в программировании используется еще целый ряд принципов композиции более сложных программ из подпрограмм, в том числе и так называемый условный оператор. А.Г.Пинусом |4] было предпринято рассмотрение абстрактного понятия условного оператора в рамках теории универсальных алгебр, и на основе этого понятия было предложено понятие условного терма. Интуитивно концепция условного терма соответствует понятию программы вычислений, преобразований на основном множестве универсальной алгебры, составленной из простейших (сигнатурных) программ с помощью оператора суперпозиции и условного оператора. В целом ряде дальнейших работ А.Г.Пинуса было продолжено изучение условных термов и получен ряд интересных приложений результатов в универсальной алгебре. Обзор полученных результатов можно найти в работах [11]-[13].

Для любой алгебры 21 = (А\ а) через СТ(21) обозначим далее совокупность всех условно термальных (программно вычислимых) функций алгебры 21. В работе А.Г.Пинуса [5] было доказано, что для конечных алгебр 21 = (A; <7i), = (В; сг2) и для биекции 7Г множества А на множество В следующие условия эквивалентны: а). Имеет место равенство (включение):

7Г-1СТ(Ф)7Г = СТ(21) (7T~1CT'(tB)7r С СТ{21) ). б). Имеют место равенства (включения): ir{Sub(%)) = 5иЬ((В),^-,/б'о((В)7г = /во(21) ( тг(5иЬ(21)) С Subi^B), 7r-1/so(53)7T D /so(2l) ).

Здесь Sub($i) - совокупность всех подалгебр алгебры 21, Iso(21) - совокупность всех внутренних (между подалгебрами) изоморфизмов алгебры 21. Алгебры 21 и 25, удовлетворяющие данным условиям, называются условно рационально эквивалентными. В силу замеченного выше, условно рационально эквивалентные алгебры 21 и Ф (то есть алгебры, для которых совокупности функций СТ(21) и СТ(ОЗ) совпадают по модулю их сопряжения некоторой биекцией 7Г между основными множествами алгебр 21 и 03) естественно рассматривать как алгебры, обладающие одинаковым вычислительным потенциалом. Таким образом, пара (5u6(2l): J,so(2l)) выступает в роли инварианта вычислительного потенциала конечной универсальной алгебры 21. Это позволяет ставить вопрос о числе потенциалов вычислимости гг-элементных алгебр (п £ ш) и изучать сравнительную силу подобных вычислительных потенциалов.

Будем далее считать, что рассматриваемые n-элементные алгебры заданы на основном множестве {0,1,., п — 1}. На совокупности СТ(п) = {СТ(21)|21 - n-элементная алгебра} введем отношение эквивалентности CT(2li) ~ CT(2l2) тогда и только тогда, когда алгебры 21^ и

212 условно рационально эквивалентны, то есть существует перестановка 7г множества {0,1,., п — 1}, которая сопрягает совокупности функций СТ(2li) и СТ(212)- Через СТп обозначим фактор-множество СТ(п)/~. Таким образом, мощность множества СТп соответствует числу попарно условно рационально не эквивалентных n-элементных алгебр, то есть числу n-элементных алгебр, имеющих различный вычислительный потенциал. Обозначим \СТп\ через S(n). На СТп введем отношение порядка индуцированное отношением теоретико-множественного включения между элементами из СТ(п) при факторизации по отношению Частично упорядоченное множество (С'ТП; назовем шкалой потенциалов вычислимости п-элементных алгебр.

Заметим, что изучение шкалы потенциалов вычислимости п-элементных алгебр определенным образом связано с изучением решетки клонов функций на n-элементном множестве п = {0,., п — 1}. Действительно, пусть Т(21) является совокупностью всех термальных функций п-элементной алгебры. Тогда отображение ^р{Т{%)) = СТ(21)/~ является монотонным отображением решетки клонов функций па множестве п на шкалу (СТпХорошо известно также равенство CT(2l) = T(Qld), где <1{'1 есть обогащение алгебры 21 добавлением в ее сигнатуру функции трехместного дискриминатора d(x,y, z). Таким образом, если D — Т(01,/), где = (n;d), то указанное выше отображение р> разлагается в суперпозицию двух монотонных отображений ip' и ip", где <р'(Т(%I)) = T(2ld) есть монотонное отображение решетки клонов функций на множестве п на фильтр [Dn] Fn] этой решетки (здесь Fn - совокупность всех функций на множестве п), a <p"(T(Qld)) — СТ(21)/~ - монотонное отображение фильтра [Dn\Fn\ на шкалу (СТпЗаметим также, что в отличие от классификации n-элементных алгебр, основанной на совпадении клонов их термальных функций (напомним, что в силу результата Е.Поста [21] число таких различных клонов на двухэлементном множестве счетно, а, в сиЛУ результата Ю.И.Янова и А.А.Мучника [18], на п-элементном множестве при п ^ 3 - континуально), классификация п-элементных алгебр по их вычислительным потенциалам конечна (число различных вычислительных потенциалов таких алгебр не превышает числа попарно не сопряженных полугрупп внутренних изоморфизмов алгебр, заданных на множестве {0,., п — 1}).

В работе А.Г.Пинуса [6] получена следующая оценка числа S(n) попарно условно рационально не эквивалентных n-элементных алгебр: для любого натурального п ^ 4

S(n) < 2n+(- е )n~[v/^ + 1/2e3([^/"] + 1/2)

Для малых 7i числа S(n) посчитаны в работе [6]: 5(2) = 5, 5(3) = 53. В приватном сообщении П.Джипсена указано, что им с помощью компьютера, получено равенство 5(4) = 22610.

В силу сказанного изучение строения шкалы потенциалов вычислимости n-элементных алгебр определенным образом близко к изучению решеток клонов функций на конечных множествах, результаты исследования которых можно найти в целом ряде работ. См., в частности, работы Е.Поста [21], Ю.И.Янова и А.А.Мучника [18], С.В.Яблонского [16], С.В.Яблонского, Г.П.Гаврилова, В.Б.Кудрявцева [17], И.Розенберга [23], С.С.Марченкова [2]-[3], А.Сендрей [24] и др. В то же время изучение шкал потенциалов вычислимости n-элементных алгебр наряду с изучением решеток клонов имеет более естественное обоснование с точки зрения изучения программных вычислений и более продуктивный подход в виде наличия довольно обозримого инварианта {5ub(21); Iso(Ql)) для потенциала вычислимости алгебры 21. Исследование строения шкал (СТп; и представляет предмет исследования диссертации.

Цели исследования:

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

- нахождение параметров шкал потенциалов вычислимости п-эле-ментных алгебр.

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

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

Результаты диссертации были представлены на международной конференции "Соответствия Галуа" (Потсдам, 2001), 4-й международной школе "Пограничные вопросы универсальной алгебры и теории моделей" (Эрлагол, 2001), международной конференции "Мальцевские чтения" (Новосибирск, 2002), международной конференции "65 рабочая встреча по общей алгебре" (Потсдам, 2003), семинаре МГУ "Математические вопросы кибернетики", семинаре ИрГУ по дискретной математике.

По теме диссертации имеется 6 публикаций [25]-(30]. Результаты, представленные в работах [27]-[29], получены диссертантом в нераздельном соавторстве с А.Г.Пинусом.

Перейдем теперь непосредственно к содержанию диссертации. В первой главе определяются базовые понятия и терминология, принятая при изложении результатов, а также приводится обзор основных результатов универсальной алгебры и, в частности, теории условных термов, необходимых при доказательстве основных результатов диссертации. Кроме того, в этой главе определяются основные объекты исследования диссертации: шкалы потенциалов вычислимости и потенциалов элементарной вычислимости n-элементных алгебр.

Вторая глава посвящена выяснению основных свойств шкал потенциалов вычислимости n-элементных алгебр и нахождению основных параметров этих шкал.

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

Утверждение 2.1. Элементарная теория класса

Sk = {{СТ„; п € ш} неразрешима.

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

Следующее утверждение указывает на возрастание сложности строения шкалы {СТп \ с ростом параметра п:

Утверждение 2.2. Для любых m < п шкала (СТт; является ре-трактом шкалы {СТп; Более того, существуют интервал [а; 6] шкалы (СТп; и эпиморфизм р шкалы (СТп; на интервал [а; Ь] такие, что ср тождественен на [а; Ь], и интервал [а; Ь] изоморфен шкале {■СТт

Для п = 2, 3 найдено явное строение шкал (СТ2; и (СТ3; =0. Приведенное выше равенство \СТ$\ = 22610 указывает на невозможность подобного подхода к описанию строения шкал (СТП; при п ^ 4.

Выше уже указывалась, что шкала (СТп; является монотонным образом решетки клонов функций на множестве п. Однако сама шкала (СТп] решеткой не является.

Утверждение 2.3. При п ^ 3 шкала (СТп; пв является ни верхней, пи нижней полурешеткой.

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

Теорема 2.1. Для любой конечной решетки L существует натуральное п и элементы FjF2/~ шкалы, (СТп\ такие, что L как решетка вложима в интервал F2]^\ шкалы (СТп; являющийся решеткой.

О сложности строения шкал {СТп \ говорит и следующий результат:

Утверждение 2.4. Графы, соответствующие диаграммам Хассе шкал, (СТп; не являются плоскими при п ^ 3.

К важным характеристикам шкал {СТп; относятся числа их атомов и коатомов, найденные диссертантом:

Теорема 2.2. Число атомов шкалы (СТп; равно [§] + 1 + R{n), где R(n) - число максимальных транзитивных на п подгрупп полной симметрической группы на п, попарно не сопряженных в этой группе. Число коатомов равно (п — 1) + К{п), где К(п) - число различных простых делителей числа п, отличных от единицы.

Найдены также длины шкал {СТп \ (максимальные длины цепей в частично упорядоченных множествах {СТп\

Теорема 2.3. Длина шкалы потенциалов вычислимости п-элементных универсальных алгебр равна п

Cnlrn + 2n+1 - 2п - 2, т=2 log-2'п] где ln = - J2 [Д-] mod 2. В частности, d{(CT2; = 3, г/((С2з; = 13, d({CT\\ = 40.

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

Следствие 2.1. Длина интервала \Dn] Fn] в решетке клонов на п-эле-ментном множестве равна, п

Г C™lm + 2"+1 - 2п - 2 т=2

Следствие 2.2. Длина максимальной цепи инверсных подполугрупп инверсной полугруппы Вг(п) (полной инверсной полугруппы биекций между подмножествами п-элементного множестваJ равна п

Y, C™lm + 2n+1 - 2п - 2 т=2

В главе 3 ставится вопрос об автоморфизмах шкал (СТП; ■<'.) и доказывается неподвижность относительно автоморфизмов некоторого естественным образом выделяемого фильтра I шкалы (С"Г„; Алгебру 21 назовем жесткой, если ее единственными внутренними изоморфизмами являются тождественные отображения ее подалгебр на себя. Совокупность всех потенциалов вычислимости n-элементных жестких алгебр образует фильтр I — {СТ(21)/~ |21 - жесткая n-элементная алгебра} в шкале (СТП;

Теорема 3.1. Для любого автоморфизма 'ф шкалы, для любой точки 21 £ I имеет место равенство ф(21) € I.

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

Утверждение 4.1. Для любой конечной алгебры 21 существует алгебра 21' сигнатуры, состоящей из одной функции, такая, что СТ{21) - СТ(2Г).

В связи с этим естественно рассмотрение ограничений на местность сигнатурных функций. Материал главы 4 посвящен изучению строения шкал потенциалов вычислимости алгебр, сигнатура которых включает лишь одноместные функции, (унаров) (СТ^;^). Здесь СТ.п — {СТ(21)/~ |21 - n-элементный унар}. Найдено явное строение шкал (CXj1; и < СТ(утверждение 4.2). Найдены числа атомов и коатомов шкал (CTrJ;

Теорема 4.1. а). Количество коатомов шкалы (СТравно

К{п) + п-1, где К(тг) - количество простых делителей п, отличных от единицы, б). Количество атомов 'шкалы (СТГ\] равно

71 П—1 где D(i) - число делителей числа г, отличных от. единицы, Т- - количество представлений числа i в виде не более чем j ненулевых натуральных слагаемых.

Доказан ряд утверждений о сложности строения шкал (СТ,);

Утверждение 4.3. При п 3 шкала {С'ТГ[: не является ни верхней, ни ниэюией полурешеткой.

Утверждение 4.4. Для, любых т < п шкала (СТ}п\ является ре-трактом шкалы (СТ*;

Утверждение 4.5. Для, п ^ 3 шкала (СТ^ \ не может быть представлена в виде планарного графа.

Материал главы 5 посвящен изучению шкал потенциалов вычислимости n-элементных алгебр при естественной вариации понятия условия в определении условного терма - замена конечной системы равенств и неравенств между термами на формулы логики 1-го порядка. Подобный подход к так называемым элементарным условным термам изложен в работе А.Г.Пинуса [7]. В этой же работе доказано, что роль инварианта для совокупности ЕСТ{Щ элементарно условно термальных функций алгебры 21 играет роль пара (5иЬ(21); Awt(2l)), где Aut(21) - группа автоморфизмов алгебры 21. Аналогично определению шкалы {СТп; на основе совокупности функций СТ(21) определяется шкала потенциалов элементарной вычислимости n-элементных алгебр на основе совокупности функций ЕСТ(21). В главе 5 найдено явное строение шкал (£СТ2; и (ЕСТ^: . Доказана правомерность рассмотрения частных вопросов строения шкал (ЕСТп;

Утверждение 5.1. Элементарная теория класса ESk неразрешим,а. Здесь ESk = {(ЕСТп, е и].

Показано возрастание сложности строения шкал (ЕСТп; с ростом п.

Утверждение 5.2. Для любых m < п шкала (ЕСТт; является ре-трактом шкалы (ЕСТп; . Более того, существует интервал [а; 6] шкалы, {ЕСТп; и эпиморфизм tp шкалы (ЕСТп; на интервал, [а; 6] такие, что ip тождественен на [а; 6], и интервал [а; Ь] изоморфен шкале (ЕСТт;

Имеет место ряд аналогий в строении шкал (СТ„; и (ЕСТп;

Утверждение 5.3. При п ^ 3 шкала {ЕСТп; не является, ни верхней, ни нижней полурешеткой.

Теорема 5.1. Для любой конечной решетки L существует натуральное п и элементы Fi/~ и шкалы {ЕСТп; такие, что L как решетка, вложима в интервал [F1/~;Jf72/~] шкалы (ЕСТп;^), являющийся решеткой.

Утверждение 5.4. Графы, соответствующие диаграммам Хассе шкал (ЕСТп; не являются плоскими при п ^ 3.

Теорема 5.2. Число атомов и коатомов шкал (СТп; и (ЕСТп\ совпадает.

Теорема 5.3. Длина, шкал {ЕСТп; равна 1п + 2п — 2.

Теорема 5.4. Для любого автоморфизма ф шкалы (ЕСТп;^), для любой точки 21 € EI имеет место включение ф(Щ £ EI.

Здесь фильтр EI шкалы (ЕСТп; определяется точно так же, как и фильтр / шкалы {СТп \ а именно: EI = {ЕСТ(2l)/~ | 21 - жесткая п-элементная алгебра }.

Автор выражает глубокую признательность А.Г.Пинусу за постановку вопросов и неоценимую помощь в работе.

1. Ершов Ю.Л. Неразрешимость теорий симметрических и простых конечных групп / Ю.Л.Ершов // ДАН СССР. - 1964. - Т. 15, №4. -С.777-779.

2. Марченков С.С. Замкнутые классы булевых функций / С.С.Марченков. М.: Наука, 2000.

3. Марченков С.С. S-классификация функций трехзначной логики / С.С.Марченков. М.: Наука, 2001.

4. Пинус А.Г. Об условных термах и тождествах на универсальных алгебрах / А.Г.Пинус // Вычислительные системы. 1996. - Вып.156. - С.59-78.

5. Пинус А.Г. Исчисление условных термов и условно рациональная эквивалентность / А.Г.Пинус // Алгебра и логика. 1994. - Т.37, №4. - С.432-459.

6. Пинус А.Г. Об условно рационально эквивалентных алгебрах / А.Г.Пинус // Вычислительные системы. 1999. - №165. - С.3-30.

7. Пинус А.Г. n-элементная вложимость и n-условные термы / А.Г.Пинус // Изв. вузов. Математика. 1999. - №1. - С.36-40.

8. Пинус А.Г. Внутренние изоморфизмы и условно рациональная эквивалентность унарам и полям/ А.Г.Пинус // Алгебра и теория моделей. Новосибирск, из-во НГТУ. - 1997. - С.131-142.

9. Пинус А.Г. О функциях, коммутирующих с полугруппами преобразований алгебр/ А.Г.Пинус // Сибирский матем. журнал. 2000. -Т.41, №6. - С.1409-1418.

10. Пинус А.Г. О многообразиях, скелеты которых являются решетками / А.Г.Пинус // Алгебра и логика. 1992. - Т.31, т. - С.74-82.

11. Пинус А.Г. Условные термы и их применение в алгебре и теории вычислений / А.Г.Пинус // Успехи матем. наук. 2001. - Т.56, JVM. -С.35-72

12. Пинус А.Г. Условные термы и их применение в алгебре и теории вычислений / А.Г.Пинус. Новосибирск: из-во НГТУ, 2002.

13. Пинус А.Г. Программно вычислимые функции на универсальных алгебрах. // Математические вопросы кибернетики, т. 10,

14. Соловьев В.Д. Автоморфизмы структуры замкнутых классов к-значной логики / В.Д.Соловьев // Материалы VII Международного семинара "Дискретная математика и ее приложения". Т.1. - Москва, из-во МГУ, 2001. - С.122-123.

15. Яблонский С.В. Введение в дискретную математику / С.В.Яблонский. М.: Наука, 1979.

16. Яблонский С.В. Функциональные построения в к-значной логике / С.В.Яблонский // Труды матем. института АН СССР им.B.А.Стеклова. 1959. - Т.51. - С.5-142.

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

18. Янов Ю.И. О существовании /с-значных замкнутых классов, не имеющих конечного базиса / Ю.И.Янов, А.А.Мучник // Докл. АН СССР. 1959. - Т.127, №1. - С.44-46.

19. Cameron P. Chains of subgroups in symmetric groups / P.Cameron, R.Solomon, A.Turull // Journal of Algebra. 1989. - V.127, No.2. -P.340-352.

20. Liebeck M.W. A classification of the maximal subgroups of the finite alternating and symmetric groups / M.W.Liebeck, C.E.Praeger, J.Saxl // Journal of Algebra. 1987. - V.lll, No.2. - P.365-383.

21. Post E.L. The Two-Valued Iterative Systems of Mathematical Logic / E.L.Post // Ann. Math. Stud. V.5. - Princeton: Princeton Univ. Press, 1941.

22. Pudlak P. Every finite lattice can be embedded into a finite partition lattice / P.Pudlak, J.Tuma // Algebra Universalis. 1980. - V.10, No.l. - P.74-95.

23. Rosenberg I. Uber die Funktionale Volstandigkeit in den Mehrwertigen Logiken / I.Rosenberg // Rozpravy Ceskoslovenske Akad. Ved. Rada Math. Prir. Ved. Praha. 1970. - Bd.80. - P.3-93.

24. Szendrei A. Clones in Universal Algebra / A.Szendrei. Montreal, Les Presses de L'Universite de Montreal, 1986.Работы автора по теме диссертации

25. Журков С.В. О неподвижности фильтров жестких алгебр шкал потенциалов вычислимости n-элементных алгебр / С.В.Журков // Препринт. Новосибирск: из-во НГТУ, 2003. - №2. - 23 с.

26. Журков С.В. О шкалах потенциалов вычислимости п-элементных унаров / С.В.Журков // Препринт. Новосибирск: из-во НГТУ. -2003. - №1. - 14 с.

27. Журков С.В. О шкалах потенциалов вычислимости универсальных алгебр / А.Г.Пинус, С.В.Журков // Математические модели в информатике: Вычислительные системы. 2002. - Вып. 169. - С.26-38.

28. Журков С.В. Некоторые замечания о шкалах потенциалов вычислимости п-элементиых алгебр / А.Г.Пинус, С.В.Журков // Алгебра и теория моделей-3. Новосибирск: из-во НГТУ, 2001. - С.107-113.

29. Журков С.В. О длине шкал потенциалов вычислимости п-элементных алгебр / А.Г.Пинус, С.В.Журков // Сибирский матем. журнал. 2002. - Т.43, Ш. - С.858-863.

30. Zhurkov S.V. On the scales of computability potentials of n-element unars / S.V.Zhurkov // Abstracts of 65th Workshop on General Algebra. Potsdam, 2003. - P.36-37.