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

• Автор: Журков, Сергей Валерьевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Иркутск
• Количество страниц: 96 с.

Оглавление
Введение

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

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

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

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

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

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

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

Литература

Введение
Одной из возможных прикладных трактовок понятий универсальной алгебры и терма сигнатуры этой алгебры является следующая - на некоторой совокупности объектов, основном множестве универсальной алгебры, заданы некоторые стандартные (будем далее называть их простейшими) программы преобразований, вычислений, соответствующие сигнатурным функциям данной универсальной алгебры. Тогда понятие терма сигнатуры этой алгебры можно рассматривать как некоторую программу преобразований, вычислений на основном множестве, составленную из простейших (сигнатурных) программ с помощью лишь оператора суперпозиции. Однако в программировании используется еще целый ряд принципов композиции более сложных программ из подпрограмм, в том числе и так называемый условный оператор. А.Г.Пинусом |4] было предпринято рассмотрение абстрактного понятия условного оператора в рамках теории универсальных алгебр, и на основе этого понятия было предложено понятие условного терма. Интуитивно концепция условного терма соответствует понятию программы вычислений, преобразований на основном множестве универсальной алгебры, составленной из простейших (сигнатурных) программ с помощью оператора суперпозиции и условного оператора. В целом ряде дальнейших работ А.Г.Пинуса было продолжено изучение условных термов и получен ряд интересных приложений результатов в универсальной алгебре. Обзор полученных результатов можно найти в работах [11]-[13].
Для любой алгебры 21 = (Л;<7) через СТ(Щ обозначим далее сово-
купность всех условно термальных (программно вычислимых) функций алгебры 21. В работе А.Г.Пинуса [5) было доказано, что для конечных алгебр 21 = (А; су), 23 = {В <Хг) и для биекции п множества А на множество В следующие условия эквивалентны:
а). Имеет место равенство (включение):
7г'1С,Г(23)тг = СТ (21)
(7г-1СГ('В)тг С ст{21) ).
б). Имеют место равенства (включения):
тг(5иЬ(Я)) = 5иЬ(<В),7г-'/5о(23)тг = /зо(Я)
(тг(5и6(Я)) С 5иЬ(23),7г_1/5о(®)7Г Э 1во{Щ ).
Здесь 5и6(21) - совокупность всех подалгебр алгебры Я, 1зо{Я) - совокупность всех внутренних (между подалгебрами) изоморфизмов алгебры Я. Алгебры Я и 23. удовлетворяющие данным условиям, называются условно рационально эквивалентными. В силу замеченного выше, условно рационально эквивалентные алгебры Я и 23 (то есть алгебры, для которых совокупности функций СГ(Я) и СТ(23) совпадают по модулю их сопряжения некоторой биекцией 7Г между основными множествами алгебр Я и 23) естественно рассматривать как алгебры, обладающие одинаковым вычислительным потенциалом. Таким образом, пара (£иЬ(Я); /ао(Я)) выступает в роли инварианта вычислительного потенциала конечной универсальной алгебры Я. Это позволяет ставить вопрос о числе потенциалов вычислимости п-элементных алгебр (п 6 ш) и изучать сравнительную силу подобных вычислительных потенциалов.
Будем далее считать, что рассматриваемые п-элементные алгебры заданы на основном множестве {0,— 1}. На совокупности СТ(п) = {СТ(Я)|Я - п-элементная алгебра} введем отношение эквивалентности ~: СТТЯ]) ~ СТ'(Яг) тогда и только тогда, когда алгебры 21 ( и
Рассмотрим алгебру 21 = (A: U, П,Д 0, т, дт~). Если
® = {С U, П,~ 0, т, /, • ■ ■ > дт-) - подалгебра алгебры 21, то С ПВ(т) образует подалгебру булевой алгебры В(т), и для любого 0 < г < т следующие условия эквивалентны:
1. СП А, ф 0;
2. Ai С С;
3. i° = ге С.
Наличие циклов {Ai, f) и функций д0,.. .,дт-1 очевидным образом влечет то, что любой внутренний изоморфизм алгебры 21 суть тождественное отображение некоторой ее подалгебры самой на себя. Кроме того, отображение <р, определенное как <р(С) = С П В(тп), является изоморфизмом решетки Sub(21) на решетку Sub(B(m)). Заметим так же, что Sub(B(m)) = Part*(m), где Part*{m.) - решетка, двойственная решетке Part(rn).
Для любого разбиения г/ € Part(m) пусть {&*,..., Ь^} - разбиение единицы (множества m) булевой алгебры В{пг), соответствующее разбиению д. Через <т,( обозначим обогащение сигнатуры <7 - (и,П,-1, 0,т,/, местных функций gj,..., д'ц^у определенных на А следующим образом:
(b; если х =
ft W = 1 J , „
10, если X Ф
Пусть 21т, = (Л; (7^). Тогда подмножество С С Л, образующее подалгебру алгебры 21, будет образовывать подалгебру алгебры 2Ц в том и только в том случае, когда С включает Вп - подалгебру булевой алгебры В(гп), порожденную разбиением (öj,..., Ь^}.
В силу этих замечаний отображение ф : Part*(m) —> СТ(п), где п = |П|, определенное как ф{т]) = СТ{%,), является изоморфным вложением решетки Part*{m) в интервал [СТ{21,ot); СТ(21,,0,)], решетки клонов