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

• Журков, Сергей Валерьевич
• кандидат физико-математических наук
• 2003

Оглавление диссертации кандидат физико-математических наук Журков, Сергей Валерьевич

Введение.

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

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

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

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

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

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

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

Введение диссертации (часть автореферата) на тему «Шкалы потенциалов вычислимости n-элементных алгебр»

Одной из возможных прикладных трактовок понятий универсальной алгебры и терма сигнатуры этой алгебры является следующая - на некоторой совокупности объектов, основном множестве универсальной алгебры, заданы некоторые стандартные (будем далее называть их простейшими) программы преобразований, вычислений, соответствующие сигнатурным функциям данной универсальной алгебры. Тогда понятие терма сигнатуры этой алгебры можно рассматривать как некоторую программу преобразований, вычислений на основном множестве, составленную из простейших (сигнатурных) программ с помощью лишь оператора суперпозиции. Однако в программировании используется еще целый ряд принципов композиции более сложных программ из подпрограмм, в том числе и так называемый условный оператор. А.Г.Пинусом |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 - жесткая п-элементная алгебра }.

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

Список литературы диссертационного исследования кандидат физико-математических наук Журков, Сергей Валерьевич, 2003 год

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.