Алгоритмические сводимости счетных алгебраических систем тема автореферата и диссертации по математике, 01.01.06 ВАК РФ
|
Калимуллин, Искандер Шагитович
АВТОР
|
||||
|
доктора физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Казань
МЕСТО ЗАЩИТЫ
|
||||
|
2009
ГОД ЗАЩИТЫ
|
|
01.01.06
КОД ВАК РФ
|
||
|
|
||||
/
. / -
/
1
На правах рукописи
КАЛИМУЛЛИН ИСКАНДЕР ШАГИТОВИЧ
АЛГОРИТМИЧЕСКИЕ СВОДИМОСТИ СЧЕТНЫХ АЛГЕБРАИЧЕСКИХ СИСТЕМ
01 01 06 - математическая логика, алгебра, и теория чисел
АВТОРЕФЕРАТ
диссертации на соискание ученой степени доктора физико-математических наук
1 7 Г17''
Казань - 2009
003476612
Работа выполнена в отделе алгебры и математической логики НИИММ им Н Г Чеботарева Государственного образовательного учреждения высшего профессионального образования «Казанский государственный университет им В И Ульянова-Ленина»
Защита состоится 8 октября 2009 г в 14 часов 30 минут на заседании диссертационного совета Д 212 081 24 в конференц-зале библиотеки Казанского государственного университета (2-е здание) по адресу 420008, г Казань, ул Кремлевская, 18
С диссертацией можно ознакомиться в библиотеке Казанского государственного университета
Научный консультант доктор физико-математических наук,
профессор
Арсланов Марат Мирзаевич
Официальные оппоненты доктор физико-математических наук,
член-корреспондент РАН Гончаров Сергей Савостьянович
доктор физико-математических наук, профессор
Морозов Андрей Сергеевич
доктор физико-математических наук, член-корреспондент РАН Семенов Алексей Львович
Ведущая организация ГОУВПО «Курскии государственный
университет»
Автореферат разослан
ч
2009 г
Ученый секретарь диссертационного совета кандидат физико-математиче< доцент
А И Еникеев
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
В диссертации исследуются алгебраические системы с точки зрения их алгоритмической сложности с помощью двух взаимозвязанныч подходов Первый подход заключается в расширении сводимости по перечислимости па алгебраические системы, а второй основывается на понятие спектра степеней алгебраической системы Оба подхода могут быть успешно формализованы на языке сводимостей массовых проблем, введенных Медведевым [3] в 1955 году
Актуальность темы Сводимость по перечислимости (е-сводимость) была введена Роджерсом [17] как расширение тьюринговой сводимости всюду определенных (тотальных) функций на частичные функции, определенные лишь на подмножествах натуральных чисел Степенями по перечислимости (е-степенями) были названы классы эквивалености относительно отношения взаимо-е-сводимости двух множеств друг к другу Роджерсом было введено понятие тотальной е-степени — это в точности образы тьюринговых степеней, относительно канонического вложения верхней полурешетки тьюринговых степеней в полурештку степеней по перечислимости Роджерсом [17] была поставлена фундаментальная проблема инвариантности класса тотальных е-степеней в полурештке степеней по перечислимости Эта проблема до сих пор остается нерешенной
Другое фундаментальное понятие, связанное со сводимостью по перечислимостью, операция скачка, было введено Розинасом [5] и Купером [8] Данная операция также является обобщением (расширением) операции скачка в тьюринговых степенях Поскольку областью значений операции скачка являются только тотальные е-степени, с проблемой инвариантности класса тотальных е-степеней тесно связана проблема инвариантности оператора скачка в полурешетке степеней по перечислимости Купером [8] и Сорби [20] была поставлена проблема определимости класса тотальных е-степеней и проблема определимости операции скачка на языке первого порядка упорядочения е-сгепеней В диссертации получено частичное решение первой проблемы и полное решение второй
Понятия степени и спектра степеней алгебраической системы было введено Рихтер [16] в 1981 году Цель введения степени алгебраической системы заключалась в попытке классифицировать сложность неконструктивизиру-
емых алгебраических систем с помощью тьюринговых степеней, структура которых была к тому времени достаточно хорошо изучена Однако самой же Рихтер [16] было обнаружено, что не каждый спектр степеней алгебраической системы имеет наименьший элемент, то есть не каждая алгебраическая система имеет степень Более того, остается до сих пор не решенной задача описания возможных спектров степеней алгебраических систем В этом направлении работали и работают много российских и зарубежных исследователей (см например [9], [И],[12],[13],[14], [19],[21],[22])
В настоящей диссертации предпринята попытка систематизации полученных сведений о спектрах степеней на языке сводимостей массовых проблем, введенных Медведевым [3] и Мучником [4] На этом языке формулируются полученные автором новые результаты, составляющие содержательную часть диссертации В качестве массовых проблем здесь рассматриваются проблемы представимости алгебраических систем В качестве сводимости этих проблем используется как равномерная сводимость Медведева (сильная сводимость), так и неравномерная сводимость Мучника (слабая сводимость) Данная трактовка позволяет, с другой стороны, рассматривать сводимость по перечислимости, как сводимость проблем представимости алгебраических систем специального вида Отметим, что при таком рассмотрении тотальные е-степени соответствуют алгебраическим системам, имеющим степень (в смысле Рихтер [16])
Объектом исследования в диссертации являются счетные алгебраические системы, их степени относительно алгоритмических сводимостей (в частности, степени по перечислимости), верхние полурешетки этих степеней, а также спектры степеней алгебраических систем
Целями исследования данной диссертации являются теоретико-порядковое описание операции скачка в степенях по перечислимости, описание тотальных степеней по перечислимости, построение алгебраических систем с заданным спектром степеней, описание соотношений между различными алгоритмическими сводимостями алгебраических систем
Методы исследования. Результаты диссертации получены с использованием стандартных методов математической логики и теории вычислимости метод вынуждения (оракульное построение) и метода приоритета (с конечными нарушениями и с бесконечными нарушениями) Кроме того, был
использован метод кодирования семейств в алгебраические системы из работ [11] и [22] На его основе автором создан метод построения алгебраической системы заведомо неравномерно сводящейся к заданной системе
Научная новизна На защиту выносятся следующие результаты
• Решение проблемы определимости операции скачка е-степеней, поставленной Купером [8] и Сорби [20]
• Определимость класса тотальных е-степеней, расположенных выше 0'е, что частично решает проблему Роджерса об инвариантности класса тотальных е-степеней Характеризации класса тотальных е-степеней посредством предиката относительной квазиминимальности, а также на языке сильных и слабых сводимостей алгебраических систем
• Решение проблемы Миллера [15] об отделимости несравнимых степеней спектрами степеней линейных порядков
• Построение алгебраических систем, спектр степеней которых имеет вид {х|х ^ Ь}, где Ь — низкая или вычислимо перечислимая степень
• Построение степени Ь < 0" такой, что совокупность {х|х ^ Ь} не является спектром степеней никакой алгебраической системы
• Вложимость произвольной счетной дистрибутивнои решетки в слабые степени алгебраических систем с сохранением точных верхних и нижних граней Нерешеточность верхних полурешеток сильных и слабых степеней алгебраических систем
• Полное описание всех возможных соотношений между сильной сводимостью, слабой сводимостью, сильной е-сводимости, слабой е-сводимостью и отношения Е-опредлимости
Все результаты, выносимые на защиту, являются новыми и получены автором самостоятечьно
Практическая и теоретическая ценность. Работа носит теоретический характер Результаты могут найти применение в дальнейших исследованиях степеней по перечислимости и спектров степеней алгебраических систем, а также могут быть использованы в учебном процессе и при чтении спецкурсов
Связь работы с крупными научными программами Работа была поддержана следующими грантами Российского фонда фундаментальных исследований 96-01-00830-а, 99-01-00174-а, 02-01-00169-а, 02-01-01108-мас, 03-01-06291-мас, 05-01-00605-а, 97-01-71000-а (РФФИ-ИНТАС), а также грантом Президента РФ МК-4314 2008 1
Апробация результатов диссертации Результаты диссертации по мере их получения докладывались на следующих конференциях Logic Colloquium 2001, Вена, Австрия, 6-11 августа 2001 г Computability and Models, Алматы, Казахстан, 24-28 июня 2002 Logic Colloquium 2002, Мюнстер, Германия, 3-10 августа 2002 г British Mathematical Colloquium 2003, Бермингем, Великобритания, 7-10 апреля 2003 г
Алгебра и Анализ 2004, 2 - 9 июля 2004, Казань, Мальцевские чтения 2004, Новосибирск, 16-18 ноября 2004 г Methods of Logic in Mathematics 2005, Санкт-Петербург, 18-24 июля 2005 г Computational prospects of infinity, Сингапур, лето 2005 г Мальцевские чтения 2005, Новосибирск, 15-17 ноября 2005 г Computabilty in Europe 2006, Суонси, Великобритания, 30 июня - 5 июля 2006 г
Мальцевские чтения 2006, Новосибирск, 14-16 ноября 2006 г Computabilty in Europe 2007, Сиена, Италия, 16-18 июня 2007 г Мальцевские чтения 2008, Новосибирск, 11-13 ноября 2008 г Итоговые научные конференции Казанского университета, 2002 - 2008 Результаты докладывались на семинаре Алгебра и логика (Новосибирск, ИМ СО РАН, рук - академик Ершов ЮЛ), логическом семинаре Отделения Математики университета Лидса (Великобритания, рук - проф С Вейнер, проф С В Купер), логическом семинаре математического факультета Вис-консинского университета (США, рук проф С Лемпп), семинаре по теории вычислимости Чикагского университета (США, рук проф Р Соар), логическом семинаре математического факультета университета Ватерлоо (Канада, рук - Р Виллард) В целом работа доложена на семинаре по теории вычислимости на механико-математическом факультете Казанского государственного университета (рук - проф М М Арсланов)
Публикация результатов. Результаты диссертации опубликованы в 18
работах, из них 12 статей входят в список ВАК
Структура и объем диссертации. Диссертация состоит из введения, пяти глав, каждая из которых которых разбита на параграфы (от трех до пяти) н списка литературы Общий объем диссертации составляет 220 страниц Список литературы содержит 43 наименований
СОДЕРЖАНИЕ РАБОТЫ
Первая глава носит вводный характер В ней содержатся основные сведения о сводимости на массовых проблемах (параграф 1), о массовых проблемах представимости алгебраических систем (параграф 2), о сводимости по перечислимости (параграф 3), о е-сводимости ачгебраических систем (параграф 4) В параграфе 5 приведены обозначения и терминология, общие для всей диссертации Приведем некоторые из этих сведений, необходимые для дальнейшего изложения
1 Сводимость массовых проблем. Массовой проблемой (по Медведеву) называется произвольная совокупность всюду определенных функций на множестве всех натуральных чисел ш Элементы массовой проблемы называются также методами ее решения Сопоставляя каждое множество ХСис его характристической функцией хх
!1, если хбХ, 0, если х ф X,
будем считать, что элементами (методами) массовых проблем могут быть и подмножества множества всех натуральных чисел со
Если А и В — массовые проблемы, то сильная (или равномерная) сводимость А <5 В имеет место, если существует единая алгоритмическая процедура, порождающая методы из А по произвольному методу из В, более формально, если существует тьюринговый оператор Ф, такой, что Ф} £ А для каждого д € В
Слабая (или неравномерная) сводимость А <то В имеет место, если к каждому методу из В может быть применена некоторая алгоритмическая процедура, порожающая метод из А, то есть для каждого метода д € В существует метод /6 А, такой, что / <т д
Спектром степеней проблемы А назовем совокупность тьюринговых степеней, относительно которых хотя бы один метод из А становится вычислимым
Sp(A) = {x|(3/6A)[/ <гх]}
Если А С ш, то
Des (А) = {Хд}
называется проблемой разрешимости множества А Если А С и), то
Enum(A) = {хв I А = Pri(ß)} называется проблемой перечислимости множества А Здесь
pri(ß) = {xew\(3ye и>)[{х,у) е В)}
2 Массовые проблемы представимости алгебраических систем. Если 21 -счетная алгебраическая система с конечной предикатной сигнатурой Ц то
Pies(2l) = (xd(®) | ® = 21 & dorn (93) С w}
является проблемой представимости системы 2i Здесь через -О(ОЗ) обозначена атомная диаграмма системы ЯЗ
Определим о сильную сводимость счетных алгебраических систем
21 <5 23 Pres(2l) <s Pres(Q3),
и их слабую сводимость
21 <и <Б 44 Pres(21) <ю Pres(iB)
Сводимости <s и <ш на алгебраических системах порождают частично упорядоченные классы степеней Ds и являющиеся верхними полурешетками
Спектр степеней Sp (Pres(2l)) проблемы представимости системы 2t будет называться просто спектром степеней системы 21 и обозначаться через
Sp (21)
Если спектр степеней Sp (21) алгебраической системы 21 имеет наименьший элемент а, то говорим, что а является степенью системы 21
3 Сводимость по перечислимости Проб тема перечислимости множества А С ш сильно эквивалентна проблеме представимости неориентировал-ного графа €пиш(Л) с вершинами Оо, 01, В^ (где ; е ш), С; (где у € А) и ребрами {Оо, Во}, {ОьВ0}, {ВлВ,+1} (где ^ еш), {В,, С,} (где ; 6 Л)
Тогда проблема разрешимости множества А С и> сильно эквивалентна проблеме Ргез(2>ез(А)), где Эе$(А) = £пит(Л ® ~А)
Из результата Селмана [18] следует, что для проблем перечислимости имеет место
Епит(Л) Епит(В) Епит(Л) <5 Епит(5)
В этом случае мы говорим, что множество А сводится по перечислимости к множеству В и пишем А <е В Отметим, что А <е В эквивалентно тому, что существует в п множество IV такое, что для всех х£и> имеет место
х 6 А <=> (3п)[(х,п) е IV &сПпСВ}
Таким образом, каждое в п множество IV можно рассматривать как оператор Ф (называемый оператором перечисления), отображающий множество В в соответствующее ему множество А = Ф (В)
Степени, образованные сводимостью по перечислимости, называются степенями по перечислимости (или е-степенями) Полурешетка е-степеней обозначается через Т>е
Степень по перечислимости, содержащая график всюду определенной функции, называется тотальной Легко видеть, что е-степень а тотальна тогда и только тогда, когда спектр проблемы перечислимости множеств А имеет наименьший элемент (то есть граф (£пшп(Л) имеет степень)
Скачком е-степени а = с!е2е(Л) (Розинас [5], Купер [8]) называется е-степень а' = с1еёе^(А)), где ЦА) = К{А)®КЩ и К (А) = {х\х€ ФХ(Л)} Ясно, что скачок а' произвольной е-степени а является тотальной е-степенью 4 Е-сводимость алгебраических систем Дымент [1] было определено понятие частичной массовой проблемы как совокупности частичных функций изшви
На классе частичных массовых проблем опять можно рассмотреть две алгоритмические сводимости Если А и В — частичные массовые проблемы, то сильная (или равномерная) е-сводимость А <$е В имеет место, если суще-
ствует оператор перечисления Ф, такой, что $(graph (ф)) есть график некоторой функции из А для каждого ip € В
Слабая (или неравномерная) е-сводимостъ A <we В имеет место, если для каждой чр € В существует ф € А такая, что graph (ф) <е graph (ф)
Спектром е-степеней e-Sp (А) проблемы А назовем совокупность всех е-степеней, к которым е-сводимся график хотя-бы одной частичной функции из А
Пусть 21 — счетная алгебраическая система с конечной сигнатурой £ Тогда
Pres(2t) = {хЬ(в) | © = 21 & dorn (93) С и)
называется частичной проблемой представимости системы 21 Здесь через Xb(ш) обозначена частичная функция, равная единице на элементах атомной диаграммы £>(93), и не определенная на элементах, не принадлежащих £>(93) Ясно, что хЬ(в) 3ДССЬ можно заменить на частичную функцию, определенную только на замкнутых атомных формул расширенной сигнатуры £* = £ U и, принимающей значение 0 или 1 в зависимости от истинности атомной формулы
Теперь можем определить сильные и слабые е-сводимости е-систем А именно, счетная система 21 слабо (неравномерно) е-сводится к счетной системе 93, записываем 21 <we 03, если Pres(2l) <we Pres(93), счетная система 21 сильно (равномерно) е-сводится к счетной системе 23, записываем 21 <se 23, если Pres (21) <5е Pres (93)
Спектр е-степеней e-Sp (Pres(2l)) проблемы представимости системы 21 будет называться просто спектром е-степеней системы 21 и обозначаться через e-Sp (21) Ясно, что 21 <ше 93 тогда и только тогда, когда e-Sp (93) С e-Sp (21)
Как и в случае сводимостей <s и <w из сильной е-сводимости 2t <se 93 следует слабая е-сводимость 21 <we 23 Стукачевым [6] было установлено, что из S-определимости счетной системы 21 в конечно-наследственной надстройке системы 93 без параметров следует сильная е-сводимость 21 <se 25, из сильной е-сводимости 21 <se 23 следует сильная сводимость 2i <s 93, наконец, из слабой е-сводимости 21 <we 93 следует слабая сводимость 21 <w 93 Последний параграф последней главы данной работы посвящен доказательсву того, что никаких других соотношений между рассматриваемыми сводимо-
стями нет (включая отношение Е-определимости одной системы в конечно-наследственной надстройке другой)
Вторая глава посвящена различным описаниям класса тотальных е-сте-пеней В параграфе 1 второй главы устанавливается определимость операции скачка е-степеней инн' на языке упорядочения е-степеней (что решает проблему, поставленную Купером [8] и Сорби [20])
Следствие 2.1 10 Е-степень 0J, и отображение u i—> и' являются определимыми в частичном порядке е-степеней
Для этого, установливается, что предикат х > и' имеет место в е-степенях тогда и только тогда, когда х > и и
(Va > u)(Vb > u)(Vc > u)[(Vz > u)[(a U z) П (b U z) = z & (a U z) П (c U z) = z] —> b U x = с U x]
Кроме того, устанавливается, что предикат х < и' имеет место в е-степенях тогда и только тогда, когда
(За > u)(3b > u)(3c > u)(Vz > u)[(aüz) P, (bUz) = z & (b U z) П (c U z) = z & (a U z) П (c U z) = z & x < a U b U c]
Следовательно, операция скачка и н-► и' может быть определена в е-степенях посредством конъюнкции V3V- и 3\/3-формул в сигнатуре частичного упорядочения е-степеней
Отсюда также следует определимость класса ТОТ(> 0J.) тотальных е-степеней, расположенных выше (или равных) е-степени 0'е (что частично отвечает на вопрос Роджерса [17] об инвариантности и определимости класса всех тотальных е-степеней)
Следствие 2 1 11 Класс тотальных степеней, расположенных выше 0'е Tot(> о;) = {х G Tot I X > о;}
является определимым в частичном порядке е-степеней
А именно е-степень х является тотальной и расположена выше (или равна) е-степени 0'е тогда и только тогда, когда выполняется конъюнкция формульных пердикатов
(За > 0е)(ЗЬ > 0е)[х = а U b & (Vz)[(a U z) П (b U z) = z]]
и
(Уа > Ое)(УЬ > Ое)(Ус > Ое)[(Уг)[(а и г) П (Ь и г) = г] & (Уг)[(а и г) П (с и г) =г]-»Ьих = сих] Из определимости класса ТОТ(> 0'е) следует тождественность автоморфизмов полурешетки степеней по перечислимости на е-степенях, расположенных выше О;"
Следствие 2 1 14. Если / Юе —► Т>е — автоморфизм полурешетки степеней по перечислимости, то /(х) = х для всех х > О'"
Кроме того, параграф содержит описание множеств, е-сводящихся к е-скачку заданного множества, являющееся аналогом леммы о пределе из классической теории вычислимости
Теорема 2 1.20 Для множеств У,Х С ш следующие усыновил эквивалентны
(1) у <е 3{Х\
(и) Существует Ь <е X такое, что
00
у = - ¿(2х+1))
х=0
При этом можем считать, что 6 {0,«} для каждого х 6 ш Здесь
через у ей, обозначается множество
В параграфе 2 второй главы исследуется связь тотальности е-степени с простейшими принципами обобщенной вычислимости В частности, установлена эквивалентность тотальности арифметической е-степени а с принципами униформизации и редукции класса е-сводящихся к а множеств
Теорема 2 2 1 Из принципа редукции для арифметической е-степени а следует тотальность е-степени а
Кроме того, доказана эквивалентность принципов униформизации и редукции для произвольной е-степени
Теорема 2 2 2. Из принципа редукции для е-степени а следует принцип униформизации для е-степени а
Результаты этого параграфа получены совместно с Пузаренко (Новосибирск)
В параграфе 3 второй главы устанавливается эквивалентность проблем инвариантности и определимости класса тотальных е-степеией (проблема Роджерса) с проблемами инвариантности и определимости предиката относительной квазиминимальности
А именно, е-степень а является нетотальной тогда и только тогда, когда выполнен формульный предикат
(3u)[Q(aUu,u)],
что также эквалентно выполнению другого предиката (также являющегося формульным в силу результатов параграфа 1 второй главы)
(3u)[Q(a U u, u) & (a U и)' = и']
Здесь Q(a, b) — предикат относительной квазиминимальности, означающий, что для каждой тотальной е-степени х < а справедливо х < b
Следствие 2 3 2. для всех е-степеней а имеет место
aeTot -i (3u) [Q (a U и, и) & (a U и)' = и']
В параграфе 4 второй главы приводится достаточный критерий для того, чтобы тотальная е-степень разлагалась над заданной е-степеныо Данный результат может быть в будущем использован при решении вышеупомянутой проблемы Роджерса
Теорема 2.4 2
(г) Пусть а данная е-степень и b есть тотааьная степень такая, что а < b Тогда ромб вложим в е-степени с b как его наибольший элемент и с a как его наименьший элемент, при условии, что существует тотальная степень с такая, что а < с < b
(и) Пусть а > 0 тотальная степень Тогда ромб вложим в низкие квазиминимальние е-степепи cae качестве его наибольшего элемента и с 0 в качестве его наименьшего элемента
Используя данное утверждение можно получить уточнение результата Ар-сланова и Сорби [7] о разложении е-степени 0'е над произвольной е-степенью
Следствие 2 4 5. Для любой А^-е-степени а < 0' ромб вложим в е-степепи с сохранением 0'е и а соответственно как наибольшего и наименьшего его элементов
Результаты этого параграфа получены совместно с Арслановым (Казань) и Купером (Лидс, Великобритания)
(Отметим, что в параграфе 2 четвертой главы приведена еще одна харак-теризация тотальных е-степеней уже на языке сводимостей алгебраических систем)
Третья глава посвящена развитию методологии построения алгебраических систем спектров степеней с заданными свойствами, в частности, со спектрами степеней, имеющих вид {х | х ^ Ь} Для случая Ь = 0 такие системы были найдены Сламаном [19] и Вехнером [22] В параграфе 1 третьей главы, носящим вводный характер, излагается используемый в дальнейшем способ кодирования семейств множеств в алгебраические системы
А именно, для каждого счетного семейства 5С2" рассматривается неориентированный граф <£#(5) с вершинами О, Вхм (где г,з б ш, X б 5), Сго (где ребрами {О, Вх.г.о} (где г € и, X € 3), {ВХ,М1 В^-ц} (где г,] <Е ш, X б 5), {Вх,^, (где г б ш, з б X б £) Данный способ
аналогичен кодированиям, приведенным в работах [11] и [22]
Спектр степеней графа состоит в точности из всех степеней, относительно которых семейство 5 вычислимо перечислимо Более того,
ЕР(5) =, Ргез(<£5(5)),
где через ЕР(£) обозначена проблема перечислимости семейства 5
ЕР(5) = {хв | В С ш & {(Рг^)^' | п б а>} = £}
Здесь для каждого И С ш и п б и) используется обозначение К^ = {у б ш \ (п, у) б К}
В частности, спектр степеней массовой проблемы ЕР(5) совпадает со спектром степеней (проблемы представимости) графа 2^(5) Поэтому, этот спектр степеней называется спектром степеней семейства 5, и обозначаеся через Эр (5)
Наконец, определяются семейства вида
ЩП, р) = {{п} ®и\пеш&и еК&си^ I/(п)}, 14
где Л — некоторое семейство (как правило вычислимо перечислимое), а и — некоторая нумерация множеств и и) —> 2Ш Отметим, что если Т — семейство всех конечных подмножеств и> и е(п) = \Уп, то семейство е) совпадает
(с точностью до эквивалентности нумерации е) с семейством, построенным Вехнером [22], спектр степеней которого есть совокупность всех ненулевых степеней
В параграфе 2 третьей главы устанавливается существование алгебраических систем, имеющих спектр степеней {х | х ^ Ь}, где Ь — произвольная низкая тьюринговая степень
Следствие 3.1 6 Пусть Т — семейство всех конечных подмножеств ш, Ъ' = 0' и £в(п) = гдеВеЪ Тогда
Для этого дается удобное описание спектров семейств УУ(7£, и), где 71 — некоторое вычислимо перечислимое семейство, содержащее все конечные множества (например семейство всех конечных множеств или семейство всех вычислимо перечислимых множеств), а V — некоторая вычислимая нумерация (см теорему 312) В частности, из этого описания следует, что спектр степеней таких семейств не зависит от выбора семейства Л Кроме того, выделяются такие нумерации V (названные Сй'-нумерациями), для которых описание спектра степеней семейства УУ(7£, V) наиболее просто Нумерации ев = Лп[И^] являются простейшими примерами СБ-нумераций
Далее, потученные результаты о спектрах степеней уточняются, что приводит к описанию сильных степеней проблем перечислимости семейств УУ(71, V), где 71 — вычислимо перечислимое семейство, содержащее все конечные множества, а V — некоторая вычислимая нумерация (см следствие 3 111)
Кроме того, в данном параграфе приводится метод, позволяющий строить алгебраические системы сводящиеся друг к другу в слабом смысле, но не сводящиеся в сильном смысле, даже если позволить обагощать системы конечным числом констант
Следствие 3 1 13. Пусть и 71ч — вычислимо перечислимые семейства, содержащие все конечные множества Тогда существуют вычислимые нумерации а и /3 мноокеств такие, что
. езоад.а)) =«, ЩЩЪьЖ
. £Ъ{ЩПиа)) <в <£Ъ{ЩП2,Р)) и
. £$(ЩК2,Р)) & <£3№Пиа))
Отметим, что сильная степень системы вида €^(<5) не зависит от обогащения этой сисгемы конечным числом констант, если £ состоит только из вычислимо перечислимых множеств (как в следствии 3 1 13)
Метод получения следствия 3 1 13 находит применение как в четвертой главе (параграф 2), так и в пятой главе (параграф 3)
В параграфе 3 третьей главы доказана вложимость произвольной счетной дистрибутивной решетки в структуры слабых степеней алгебраических сисгем
Теорема 3 2 10 Для каждой счетной дистрибутивной решетки £ существует набор семейств Гд такой, что спектры степеней семейств ш Гс образуют решетку относительно объединения и пересечения изоморфную £
Другими словами, каждая счетная дистрибутивная решетка вложима в Т>ы с сохранением точных верхних и нижних граней
Кроме того, здесь найдено некоторое патологическое свойство структуры сильных и слабых степеней А именно, установлено, что существуют возрастающие цепочки алгебраических систем (относительно рассматриваемой сводимости), имеющие в качестве точной верхней грани некоторую другую алгебраическую систему При доказательстве этих результатов продолжается изучение спектров степеней семейств УУ(71, у), начатое в предыдущем параграфе В частности, рассматриваются соотношения между теоретико-множественными операциями на спектрах степеней семейств вида УУ(71, ь>) (пересечение и объединение спектров) и операциями на нумерациях (прямая сумме, и прямое произведедение) Изучаются также и бесконечные суммы нумераций
В параграфе 4 третьей главы устанавливается существование алгебраических систем, имеющих спектр степеней {х | х ^ Ь}, где Ь — произвольная вычислимо перечислимая тьюринговая степень В частности, существует алгебраическая система, спектр степеней которой есть {х | х ^ О'}
Семейства, исследованые в первых двух параграфах третей главы, не могут быть здесь использованы если Л — вычислимо перечислимое семейство, содержащее все конечные множества, и и — вычислимая нумерация Д® множеств, то спектр степеней семейства \ViJZ, и) содержит все не-низкие степени Поэтому здесь рассматриваются семейства вида И;(Р, ев), где V — семейство всех областей значений возрастающих примитивно рекурсивных функций {V состоит только из бесконечных множеств), ев — и В € Ь — вы-
числимо перечислимое множество (здесь Ь не обязательно является низкой степенью, так что ев вообще говоря не будет нумерацией Д° множеств) Устанавливается, что спектр семейства УУ^Р, ев) есть {х | х ^ Ь}
Теорема 3 3 4 Пусть А — произвольное в п множество, и V — семейство всех областей значения строго возрастающих примитивно рекурсивных функций Тогда
1) семейство
уу(Т,еА) = {{е} @и\еешки еГ & £/ ф
не является А-вычислимо перечислимым (то есть deg(Л) ^ Бр (УУ("Р, ел))),
2) существует вычислимая функция (I такая, что дая всех X ^т А имеет место
ЩТ,еА) = {\Г$п) | пей},
(то есть {х | х ^ с^(Л)},}
Четвертая глава посвящена в основном теоретическим результатам, ограничивающим методологию, развитую в третьей главе Одновременно с этим получены некоторые решения проблем, касающихся спектров степеней и различий сильной и слабой сводимости
В целом, результаты параграфа являются обобщениями следующих известных результатов
Теорема 4 0 2. (Фольклор) Если несравнимые степени а и Ь лежат в спектре степеней Бр (21) счетной алгебраической системы 21, то Эр (21) содержит также некоторую степень с такую, что а^сиЬ^с
Следствие 4 0.3. (Фольклор) Если степени а = с^(Л) и Ь = йщ(В) не сравнимы, то класс степеней
Бр (®ез(Л)) и Бр (Эез(В)) = {х | а < х} и {х | Ь < х}
не является спектром степеней ни одной счетной алгебраической системы Другими словами массовая проблема Ргез(Эе5(Л)) V Ргев(Юез(В)) не слабо эквивалентна ни одной проблеме представимости
Теорема 4 0 4 (Рихтер [16]) Если ненулевая степень а лежит в спектре степеней локально конструктивизируемой счетной алгебраической системы (например, линейного порядка), то Бр (21) содержит также некоторую степень с такую, что а ^ с
Следствие 4 0 5 (Рихтер [16]) Если локально конструктивизируемая счетная алгебраическая система (например, линейный порядок) имеет степень, то она является конструктуивизируемой
В параграфе 1 четвертой главы доказана нерешеточность верхних полурешеток сильных и слабых степеней ал1 ебраических систем
Для этого устанавливается, что если несравнимые степени а и Ь лежат в спектре степеней счетной алгебраической системы, то этот же спектр степеней должен содержать также некоторую степень с такую, что а ^ с, Ь ^ с и с' < а'
Следствие 4.1 2. Если несравнимые степени а и с лежат в спектре степеней Бр (21) счетной алгебраической системы 21, то Эр (21) содержит также некоторую степень Ь такую, что а ^ Ь, с ^ Ь и Ь' < а'
Оценка с' < а' вместе с результатом из параграфа 1 третей главы (упомянутое выше следствие 316), позволяет сделать вывод о том, что две алгебраические системы, имеющие спектры степеней {х | х > а} и {х | х > Ь}, соответственно, не имеют точной нижней грани относительно слабой сводимости, если степени а и Ь несравнимы и являются низкими Выбирая две конкретные алгебраические системы с указанными выше спектрами степеней, можно распространить данное утверждение и на сильную сводимость алгебраических систем
Следствие 4 1.3 Пусть тьюринговые степени а и с несравнимы, а' = 0', А 6 а и С 6 с Тогда сильные и слабые степени алгебраических систем 2)с5(Л) и Т)ез(С) не ичеют наибольшей нижней грани вБ5 в ТУу,, соответственно
В параграфе 2 четвертой главы дается характсризация тотальных е-степенеи как е-степеней таких алгебраических систем, сильная и слабая сво-
димости к которым не отличаются между собой (даже с точностью до конечных обогащении константами)
Для этого для каждой алгебраической системы, не имеющей степени, среди тыоринговых скачков спектра степеней которой имеется наименьший (то есть система имеет j-степень), строится другая алгебраическая система, неравномерно сводящаяся к первой, но не сводщаяся к ней равномерно, даже если разреши! ь обогащать системы конечным числом констант
Теорема 4 2 3. Если счетная алгебраическая система Ш имеет j-степень и не имеет степени, то существует счетная алгебраическая система 21, такая, что Pres(2l) <w Pres(Q3) и Pres(2l) Pres(25, b) для любого конечного набора Ь элементов из dorn (58)
Из результата Доуни, Коулза и Сламана [10] следует, что система (£пит(Л) всегда имеет j-степень Отсюда получаем, еще один критерий тотальности степени по перечислимости
Следствие 4 2 6. Для е-степени b следующие условия эквивалентны
1 b является тотальной е-степенью,
2 Для В G b и произвольной алгебраической системы 21 из 21 <w €uum(ß) следует 21 <s <£num(B)
В параграфе 3 четвертой главы приводится отрицательный ответ на вопрос Миллера [15] об отделимости несравнимых степеней спектрами степеней линейных порядков
Вопрос (Миллер [15]) Можно ли для произвольных несравнимых степеней а и b найти такой линейный порядок £, что а G Sp (£) и b ф Sp (£)?
Более того, установлено, что для каждой ненулевой степени а существует такая несравнмая с а степень b, Ь' < а', содержащаяся во всех спектрах степеней счетных линейных порядков, в которых содержится степень а
Теорема 4 3.1 Для каждой степени а > 0 существует степень Ь, не сравнимая с а, такая, что Ь' < а' и для любого линейного порядка £
а G Sp(£) b G Sp (£)
Отметим, что если линейный порядок £ поставить в начало данного утверждения, то есть от схемы «УаЗЬ\/£ » перейти к «У£\/аЭЬ », то получим более слабое утверждение, известное из работы Рихтер [16] (теорема 4 0 4) Фиксируя теперь произвольную низкую степень а > 0, получаем
Следствие 4 3 2 Существует низкие несравнимые степени а«Ь такие, что не существует линейного порядка £, для которого имеет место а € Яр(£) и Ь ^ Эр (£)
Следствие 4.3 3. Существует такая низкая степень Ь, что
8р(£)/{х|х£Ь}
для всех счетных линейных порядков £
Последний результат (вместе со следствием 316) является косвенным аргументом в пользу отрицательного ответа на вопрос Доуни [9] о существовании линейных порядков со спектром степеней {х | х > 0}
В параграфе 4 четвертой главы устанавливается существование тью-ринговой степени Ь < О'4) такой, что совокупность {х | х ^ Ь} не является спектром степеней никакой алгебраической системы (следствие 4 4 2)
Для этого, устанавливается, что для каждой пары несравнимых степеней ао и а1 существует такая степень Ь < (ад и а^4), что ао ^ Ь, ах ^ Ь, и каждый спектр степеней алгебраической системы, содержащий степени ао и ах должен содержать также степень Ь Более того, справедлива следующая
Теорема 4 4 1 Пусть А — непустая счетная совокупность степеней, в которой нет наименьшего элемента Тогда существует такая степень Ь, что а ^ Ь для всех а 6 А, и
А с Бр (21) =>■ Ь е Бр (21)
для произвольной алгебраической структуры 21
Рассматривая двух-элементную совокупность А = {а, с}, где степени а и с несравнимы, получаем
Следствие 4 4.2. Существует такая степень Ъ, что
8р(21)^{х|х^Ь} для всех алгебраических структур 21
В отличие от указанного выше результата из параграфа 1 четвертой главы (теорема 4 13) степень Ь в теореме 4 4 1 не зависит от фиксированной заранее алгебраической системы со своим спектром степеней Однако установленная ранее оптимальная оценка Ь' < а' ухудшается в теореме 4 4 1 (при А = {а, с}) до Ь < (аис)'4) (от оценки скачка степени Ь всего лишь однократным скачком одной из степеней а и с до оценки только лишь самой степени Ь четырехкратным скачком точной верхней грани степеней а и с)
Поэтому степень Ь в следствии 4 4 2 может быть оценена только степенью Отметим также, что в силу вышеупомянутого результата из второго параграфа (теорема 4 4 1 и следствие 4 4 3) оптимальные оценки сохраняются, если вместо произвольных алгебраических систем ограничится лишь линейными порядками
В параграфе 5 четвертой главы основной результат параграфа 4 усиливается, посредством построения степени Ь < 0" такой, что совокупность {х | х ^ Ь} не является спектром степеней никакой алгебраической системы
Для этого, в отличие от предыдущего параграфа, устанавливается, что для каждой ненулевой степени а существуют подходящая несравнимая степень с, с < а" такая, что для совокупности А = {а, с} степень Ь из теоремы 4 41 может быть построена с оценкой Ь < а"
Теорема 4 5.1. Для любой степени а > 0 существует степени Ь < а" и с < а", такие, что а ■¿Ъ, с ■¿Ъ, и для любой алгебраической структуры 21
{а, с} С Бр (21) Ь е Бр (21) Отсюда немедленно вытекает
Следствие 4 5 2. Существует такая степень Ь < 0", что
Зр (21) ^ {х | х Ь}
для всех алгебраических структур 21
При доказательстве теоремы 4 5 1 используется метод приоритета с бесконечными нарушениями, а также техника работы со степенями по перечислимости
Пятая глава посвящена изучению е-сводимостей алгебраических систем, основанных на сводимости частичных проблем представимости, введенных
Дымент [1] В частности, оценивается возможность применения методов, разработанных в предыдущих главах для изучения спектров е-стененей и е-сводимостеи алгебраических систем
В параграфе 1 пятой главы исследуются спектры е-степеней систем вида где <S С — счетное семейство (такие спектры называются для
краткости спектрами е-степеней рассматриваемых семейств и обозначаются через e-Sp (S))
Доказывается, что спектр е-степенеи семейсгва всех бесконечных вычислимо псречислимых множество совпадает с классом высоких е-степеней (то есть е-степеней, скачок которых ограничен снизу двойным скачком нулевой е-степени)
Следствие 5 12 Для семейства £°° всех бесконечных вычислимо перечислимых множеств справедливо e-Sp (£°°) = {х G De | х' > 0^'}
Для доказательства используется аналог леммы о пределе для сводимости по перечислимости, полученной в параграфе 1 второй главы (теорема 2 1 20) Кроме того, устанавливается, что в отличие от результатов об обычных спектрах степеней семейств из третей главы (см , например, следствие 3 16) спектр е-степенеи семейств конечных множеств не может совпадать с классом всех ненулевых е-степеней
Теорема 5 13 Если S состоит только из конечных множеств и х G e-Sp (iS) дл? каждой ненулевой е-степени х, то 0 G «S
Наконец, доказывается, что спектр е-степеней семейства W(£,e) состоит в точности из непулевых е-степеней (где £ — семейство всех вычислимо перечислимых множеств, и £ = An[W„])
Теорема 5 18 Для семейства
S — W(£, е) = {{n} (BU \ п € lu &U en kU ф\Уп)
справедливо e-Sp (<S) = {х G De | х > 0e}
Отсюда следует, что существует алгебраическая система со спектром е-степеней, совпадающим с классом всех ненулевых е-степеней То же самое оказывается верным, если вместо понятия спектра е-степеней использовать понятие расширенного спектра степеней, введенного Сосковым [21] для счетной модели Ш в вычислимой сигнатуре S (расширенный) спектр степеней
модели ЯЯ есть совокупность степеней по перечислимости
DS(im) = {dege(Z)+(0l)) | ОТ ^ 01/= & dorn (01) = ш},
где 01 пробегает все возможные модели в сигнатуре Е' = Е U {=, такие, что = является отношением конгруэнтности на 9t Здесь D+(Ol) есть подмножество атомной диаграммы 0(01), состоящее только из атомных предложений (а не их отрицании)
Следствие 5,1 9 Существует такие счетные модели fUli и что
DS(OTi) = e-Sp (Ж2) = {х е De | х > 0е}
В параграфе 2 пятой главы исследуется важный частный случай е-сво-димости алгебраических систем вида <£$(S), связанный с Е-определимостью в допустимых множествах А именно, говорим, что семейство <So Е-сводится к семейству <Si (и обозначать как So Се 5i), если для любого допустимого множества А, вычислимость <Si в А влечет вычислимость Sq в А, что эквивалентно тому, что система <£3(So) является Е-определимой в HF(£3"(<Si))
Если^о Се Si и Si Es <So то говорим, что семейства Sq и <Sj эквивалентны и пишем «So >Si
Установлены следующие Е-эквивалентности естественных семейств вычислимо перечислимых множеств (см предложения 5 2 2 и 5 2 4)
1 Семейство CF графиков вычислимых функций Е-эквивалентно семейству CF2 графиков вычислимых {0,1}-значных функций
2 Семейство £ — Inf СЕ бесконечных вычислимо перечислимых множеств Е-эквивалентно семейству CFL){lo}, которое в свою очередь Е-эквивалентно семейсту CF2 U {w}
Следующие результаты описывают семейства, Е-сводящиеся к CF и CF U
м
Теорема 5 2 5 Для семейства S имеет место S CF тогда и только тогда, когда
1 все множества из S вычислимо перечислимы,
2 индексное множество I{S) = {n | Wn Е ¿>} принадлежит классу £3 арифметической иерархии, и
3 существует частично вычислимая функция "ф такая, что 5ф = -£(<5) и для всех и € 5ф имеет место Д, С € £
Теорема 5 2.9 Для семейства 5 имеет место ¿> Ее СЕ и {а>} тогда и только тогда, когда
1 все множества из ¿> вычислимо перечислимы,
2 индексное множество 1(5) = {п | ]¥п 6 5} принадлежит классу Е° арифметической иерархии, и
3 существует вычислимо перечислимое семейство 5 С 5, что для любого \У 6 5 имеет место IV СУ для некоторого V 6 ¿>
Следствие 5.2 10 СГ СР и {ш}
Кроме того, а параграфе обсуждается проблема введения операции скачка для Е-степеней семейств В частности доказано
Следствие 5.2.15 Для каждого семейства 5 существует Ег-определимое в НР(5Ш5) семейство 5' 5
Результаты этого параграфа получены совместно с Пузаренко (Новосибирск)
В параграфе 3 пятой главы полностью описываются все возможные соотношения между сильной сводимостью, слабой сводимостью, сильной е-сводимости, слабой е-сводимостью алгебраических систем, также как и отношения Е-определимости одной системы в конечно-наследственной надстройке другой (см [2])
А именно, установлено, что соотношения между рассматриваемыми сво-димостями исчерпываются нижеперечисленными
• из Е-определимости одной системы в конечно-наследственной надстройке другой без параметров следует сильная е-сводимость первой системы ко второй,
• из сильной сводимости следует слабая сводимость,
• из сильной е-сводимости следует слабая е-сводимость,
• из сильной е-сводимости следует сильная сводимость,
• из слабой е-сводимости следует слабая сводимость
Данное описание остается верным, если в определении сводимостей разрешить обогащать системы конечным числом консгант
Данный параграф завершает исследование рассматриваемых соотношений, начатое Стукачевым в работе [6] А именно, было установлено, что для системы ОТ = <£3"(7£), где
Л = У\!(£,е) = {{п} (&и \п е и>&,и вп ки ф\Уп},
справедливы следующие утверждения
• ОТ <<с ОТ и ОТ не Е-определима в НГ(ОТ) для некоторой системы ОТ (теорема 5 31) Здесь в качестве ОТ можно взять систему
ОТ = <£5(£°°) = ££({£/ | и в п и бесконечно})
• ОТ <5 ОТ и 01 ОТ для некоторой системы ОТ (теорема 5 3 2) Здесь в качестве ОТ можно взять систему ОТ = где
5 = ЩР,е) = {{п} ®и | п е шк и конечно ки ф \¥п}
• ОТ <ше ОТ и ОТ ОТ для некоторой системы ОТ (теорема 5 3 3) Здесь ОТ = <£^(5), где
5 = Щ£, е") = {{п} ® 17 \ п € и к1/ вп ки ф
и нумерация ь> такова, что
1) нумерация е-скачков г/'(п) = ./(^(п) © 1>(п)) является вычислимой нумерацией Дг-множеств
2) (dege(í^(n) © 1у(п))) > 0е для всех п € и,
3) с^^г^п) © г/(п)) П с^е(у(т) ф 1у(т)) — 0е для всех пфт
• ОТ <ш ОТ, ОТ ОТ и ОТ ОТ для некоторой системы ОТ (теорема 5 3 4) Здесь ОТ = £$(8), где
<5 = ЩТ, е") = {{п} © V | п е ш к г/ конечно & {/ ф
и нумерация ^ такая же как и в предыдущем пункте
• 9Я, <8 9Л и ЯЛ для некоторой системы (теорема 5 3 5)
т = да), где
8 = = {{п}®и\пеики вп ки^-р{п)},
а нумерация @ задается специальным пошаговым построением
Так как семейства 72. и 5 состоят только из в п множеств, системы Ш = <£3(Л) и 91 = £5(5) в приведенных выше утверждениях можно заменить любыми их конечными константными обогащениями
При доказательстве этих утверждений используются результаты из параграфа 1 второй главы, параграфа 1 третьей главы и первых двух параграфов пятой главы
Автор выражает глубокую благодарность М М Арсланову за постоянное внимание к работе и плодотворные беседы, способствовавшие улучшению диссертации
Литература
[1] Дымент Е 3 О некоторых свойствах решетки Медведева//Матем сборник - 1976 - Т 101 - С 360-379
[2] Ершов Ю JI Определимость и Вычислимость - Новосибирск Научная книга, Новосибирск, 2000
[3] Медведев Ю Т Степени трудности массовых проблем // ДАН СССР -1955 -Т 104 - С 501-504
[4] Мучник А А О сильной и слабой сводимости алгоритмических проблем // Сиб матем журнал - 1963 - X'- 4 - С 1328-1341
[5] Розинас М Г Полурешетка е-степеней // Рекурсивные функции - Иваново Ивановский гос университет, 1978 - С 71-84
[6] Стукачев А И О степенях представимости моделей I // Алгебра и логика - 2007 - .V 6 - С 763-788
[7] Arslanov М М , Sorbi A Relative splittings of Oj, in the enumeration degrees // Logic Colloquium '98, Buss S and Pudlak P editors, -Benin Springer-Verlag, 1999
[8] Cooper S В Enumeration reducibility, nondetermmistic computations and relative computability of partial functions // Lecture Notes m Mathematics -1990 -V 1432 -P 57-110
[9] Downey R On presentations of algebraic structures // Complexity, Logic, and Recursion Theory, Sorbi A editor - New York Dekker, 1997 - P 157205
[10] Coles R J , Downey R G , Slaman T A Every set has a least jump enumeration // J London Math Soc - 2000 - V 62 - P 641-649
[11] Goncharov S S , Harizanov V S , Knight J F , McCoy C , Miller R G , Solomon R Enumerations in computable structure theory // Ann of Pure and Applied Log - 2005 - V 136, № 3 - P 219-246
12] Harizanov V S , Miller R Spectra of structures and relations //J Symbolic Logic - 2007 - V 72 - P 324-348
13] Hirschfeldt D R, Khoussamov B , Shore R A , Slmko A M Degree spectra and computable dimensions m algebraic structures // Ann of Pure and Applied Log - 2002 - V 115 - P 71-113
14] Knight J F Degrees coded m jumps of ordermgs //J Symbolic Logic -1986 -V 51 -P 1034-1042
15] Miller R G The A^spectrum of linear order //J Symbolic Logic - 2001
- V 66 - P 470-486
16] Richter L J Degrees of structures //J Symbolic Logic - 1981 - V 46 -P 723-731
17] Rogers H Jr Theory of Recursive Functions and Effective Computability -New York McGraw-Hill, 1967
18] Selman A L Arithmetical reducibihties I // Z Math Logik Grundlag Math - 1971 - V 17 - P 335-350
19] Slaman T Relative to any nonrecursive set // Proc Amer Math Soc -1998 - V 126 - P 2117-2122
20] A Sorbi, Open problems m the enumeration degrees // Contemporary Mathematics - 2000 -V 257 -P 839-848
21] Soskov I N Degree spectra and co-spectra of structures // Ann Umv Sofia
- 2003 - V 96 - P 45-68
22] Wehner S Enumerations, countable structures, and Turing degrees // Proc Amer Math Soc - 1998 - V 126 - P 2131-2139
СПИСОК ОПУБЛИКОВАННЫХ РАБОТ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ
[1] Арсланов М М , Калимуллин И Ш , Купер С Б Свойства разложения тотальных степеней по перечислимости // Алгебра и Логика - 2003 -Т 42, № 1 - С 3-25
[2] Калимуллин И Ш , Пузаренко В Г О принципах вычислимости на допустимых множествах // Мат Труды - 2004 - Т 7, № 2, - С 35-71
[3] Калимуллин И Ш Спектры степеней некоторых алгебраических структур // Алгебра и Логика - 2007 - Т 46, Л* 6 - С 729-744
[4] Калимуллин И Ш , Почти вычислимо перечислимые семейства множеств //Матем сборник -2008 -Т 199, № 10 - С 33-40
[5] Калимуллин И Ш , Ограничения на спектры степеней алгебраических структур // Сибирский мат журнал - 2008 - Т 49, №6 - С 1296-1309
[6] Калимуллин И Ш , Пузаренко В Г О сводимости на семействах // Алгебра и логика - 2009 - Л"? 1 - С 33-51
[7] Калимуллин И Ш Равномерность сводимостей алгебраических систем // Сибирский мат журнал - 2009 - № 2 - С 334-343
[8] Калимуллин И Ш Соотношения между алгоритмическими сводимостя-ми алгебраических систем // Известия ВУЗов Математика - 2009 -№6 - С 71-72
[9] Kalimulllm I Sh Splitting properties of n- с e enumeration degrees //J Symbolic Logic - 2002 - V 67 - P 537-546
[10] Kalimulllm I Sh Definability of the jump operator in the enumeration degrees //J Mathematical Logic - 2003 - № 2 - P 257-267
[11] Kalimullm I Sh Elementary differences between the (2p)-c e and the (2p + 1)-c e enumeration degrees //J Symbolic Logic - 2007 - V 72, № 1 - P 277-284
[12] Kalimullin I Sh , Enumeration degrees and enumerability of familes // Journal of Logic and Computation - 2009 - V 19 - № 1 - P 151-158
[13] Арсланов M M , Калимуллин И Ш Исследования по теории вычислимости //В книге "На рубеже веков НИИММ Казанского университета" - Казань, изд-во Казан матем общества - 2003 - С 50-68
[14] Kahmullm I Sh On primitive recursive permutations // Cooper S В , Goncharov S S eds Computability and models New York, NY Kluwer Academic/Plenum Publishers - 2003 - P 249-258
[15] Kahmullm I Sh On the problems of definability m the enumeration degrees // Lecture Notes m Computer Science - 2005 - V 3526 - P 221-222
[16] Kahmullm I Sh The Dyment reducibihty on the algebraic structures and on the families of subsets of omega // Proceedings of the Second Conference on Computability m Europe (CiE 2006), University of Wales Swansea - 2006 -№ CSR 7-2006 - P 150-159
[17] Kalimullm I Sh Some notes on degree spectra of the structures // Lecture Notes m Computer Science - 2007 - V 4497 - P 389-398
[18] Arslanov M M , Cooper S В , Kahmullm I Sh , Soskova M I, Total degrees and nonsphtting properties of E^ enumeration degrees // Lecture Notes m Computer Science - 2008 - V 4978 - С 568-578
Подписано в печать 19 06 09 Формат 60 х 84 1/16 Печать ризографическая Печ л 1,8 Тираж 130 экз Заказ 61/6
Отпечатано с готового оригинала-макета в типографии издательства Казанского государственного университета
420008, ул Профессора Нужина, 1/37 тел 231-53-59,292-65-60
1 Массовые проблемы представимости алгебраических систем
1.1 Массовые проблемы и решетка Медведева
1.2 Проблемы представимости алгебраических систем и их спектры степеней.
1.3 Сводимость по перечислимости.
1.4 Е-сводимости алгебраических систем.
1.5 Обозначения и терминология.
2 Тотальные степени по перечислимости
2.1 Тотальные е-степени и операция скачка в е-степенях
2.2 Тотальные е-степени и простейшие принципы теории вычислимости.
2.3 Тотальные е-степени и относительная квазимималыюсть
2.4 Свойства разложимости тотальных е-степеней.
3 Массовые проблемы перечислимости семейств
3.1 Предварительные сведения.
3.2 Новые спектры степеней.
3.3 Операции на нумерациях и спектры.
3.4 Вычислимые нумерации Е^-множеств.
4 Ограничения на спектры степеней алгебраических систем
4.1 Нерешеточность полурешеток и Бщ,.
4.2 Равномерность сводимости к алгебраическим системам и тотальные е-степени.
4.3 Случай линейных порядков.
4.4 Спектры степеней систем произвольной сигнатуры
4.5 Построение степени Ь < О" для которой совокупность х | х ^ Ь} не является спектром
5 Частичные проблемы представимости алгебраических систем
5.1 Спектры е-степеней семейств подмножеств множества натуральных чисел.
5.2 Относительная Е-определимость семейств в допустимых множествах.
5.3 Соотношения между сводимостями алгебраических систем
В диссертации исследуются алгебраические системы с точки зрения их алгоритмической сложности с помощью двух взаимосвязанных подходов. Первый подход заключается в расширении сводимости по перечислимости на алгебраические системы, а второй основывается на понятие спектра степеней алгебраической системы. Оба подхода могут быть успешно формализованы на языке сводимосгей массовых проблем, введенных Медведевым [5] в 1955 году.
Сводимость по перечислимости (е-сводимость) была введена Роджерсом [32] как расширение тьюринговой сводимости всюду определенных (тотальных) функций на частичные функции, определенные лишь на подмножествах натуральных чисел. Степенями по перечислимости (е-степенями) были названы классы эквивалености относительно отношения взаимо-е-сводимости двух множеств друг к другу. Роджерсом было введено понятие тотальной е-степени — это в точности образы тыоринговых степеней, относительно канонического вложения верхней полурешетки тыоринговых степеней в полурештку степеней по перечислимости. Роджерсом [32] была поставлена фундаментальная проблема инвариантности класса тотальных е-степеней в полурештке степеней по перечислимости. Эта проблема до сих пор остается нерешенной.
Другое фундаментальное понятие, связанное со сводимостью по перечислимостью, операция скачка, было введено Розинасом [8] и Купером [15]. Данная операция также является обобщением (расширением) операции скачка в тьюринговых степенях. Поскольку областью значений операции скачка являются только тотальные е-степени, с проблемой инвариантности класса тотальных е-степеней тесно связана проблема инвариантности оператора скачка в полурешетке степеней по перечислимости. Купером [16] и Сорби [40] были поставлены проблемы определимости класса тотальных е-степеней и операции скачка на языке первого порядка упорядочения е-степеней. В диссертации получено частичное решение первой проблемы и полное решение второй.
Понятия степени и спектра степеней алгебраической системы было введено Рихтер [31] в 1981 году. Цель введения степени алгебраической системы заключалась в попытке классифицировать сложность неконструктивизируемых алгебраических систем с помощью тьюринговых степеней, структура которых была к тому времени достаточно хорошо изучена. Однако самой же Рихтер [31] было обнаружено, что не каждый спектр степеней алгебраической системы имеет наименьший элемент, то есть не каждая алгебраическая система имеет степень. Более того, остается до сих пор не решенной задача описания возможных спектров степеней алгебраических систем. В этом направлении работали и работают много российских и зарубежных исследователей (см. например [17], [19],[21],[22],[25], [37],[41],[42]).
В настоящей диссертации предпринята попытка систематизации полученных сведений о спектрах степеней на языке сводимостей массовых проблем, введенных Медведевым [5] и Мучником [6]. На этом языке формулируются и новые результаты полученные автором, являющиеся содержательной частью диссертации. В качестве массовых проблем здесь рассматриваются проблемы представимости алгебраических систем. В качестве сводимости этих проблем используется как равномерная сводимость Медведева (сильная сводимость), так и неравномерная сводимость Мучника (слабая сводимость). Данная трактовка позволяет, с другой стороны, рассматривать сводимость по перечислимости, как частный случай сводимости проблем представимости на алгебраических системах специального вида. Отметим, что при таком рассмотрении тотальные е-степени соответствуют алгебраическим системам, имеющим степень (в смысле Рихтер [31]).
Перейдем теперь к конкретному описанию результатов, полученных в диссертации.
Диссертация разбита на пять глав. Каждая глава разбита на параграфы, количество которых варьируется между тремя и пятью.
Первая глава носит вводный характер. В ней содержатся основные сведения о сводимости па массовых проблемах (параграф 1), о массовых проблемах представимости алгебраических систем (параграф 2), о сводимости по перечислимости (параграф 3), о е-сводимости алгебраических систем (параграф 4). В параграфе 5 приведены обозначения и терминология, общие для всей диссертации.
Вторая глава посвящена различным описаниям класса тотальных е-стеиеней. В параграфе 1 второй главы устанавливается определимость операции скачка е-степеней и и и' на языке упорядочения е-стеиеней (что решает проблему, поставленную Купером [16] и Сорби [40]).
Для этого, установливается, что предикат х > и7 имеет место в е-степенях тогда и только тогда, когда х > и и
Уа > и)(УЪ > и) (Ус > и) [(Уг > и) [(а и г) П (Ь и г) - г к (а и ъ) П (с и г) = г] Ь и х = с и х].
Кроме того, устанавливается, что предикат х < и' имеет место в е-степенях тогда и только тогда, когда
За > и)(ЗЬ > и) (Зс > и) (Уг > и) [(а и г) П (Ъ и г) = г & (Ь и ъ) П (с и г) = г & (а и г) П (с и г) = г & х < а и Ь и с].
Следовательно, операция скачка ин-^и' может быть определена в е-степенях посредством конъюнкции УЗУ- и ЗУЗ-формул в сигнатуре частичного упорядочения е-степеней.
Отсюда также следует определимость класса ТОТ(> 0^,) тотальных е-степеней, расположенных выше (или равных) е-степсни 0'р (что частично отвечает на вопрос Роджерса [32]).
А именно е-степень х является тотальной и расположена выше (или равна) е-степени 0'е тогда и только тогда, когда выполняется конъюнкция формульных пердикатов
За > 0е)(ЗЬ > 0е)[х = а и Ь & (Уг)[(а и ъ) П (Ь и ъ) = г]] и
Уа > 0е) (УЬ > 0е) (Ус > 0е) [(Уг) [(а и г) П (Ь и г) = г] &
Уг)[(аиг) П (с и ъ) = г] Ь и х = с и х].
Из определимости класса ТОТ(> 0'е) следует тождественность автоморфизмов полурешетки степеней по перечислимости на е-степенях, расположенных выше 0'е".
Кроме того, параграф содержит описание множеств, е-сводящихся к е-скачку заданного множества, являющееся аналогом леммы о пределе из классической теории вычислимости для сводимости по перечислимости.
В параграфе 2 второй главы исследуется связь тотальности е-степени с простейшими принципами обобщенной вычислимости. В частности, установлена эквивалентность тотальности е-степени арифметического множества А с принципами униформизации и редукции, если класс вычислимо псречислимых множеств заменить классом е-сводящихся к А множеств. Результаты этого параграфа получены совместно с Пузаренко (Новосибирск).
В параграфе 3 второй главы устанавливается эквивалентность проблем инвариантности и определимости класса тотальных е-степеней (проблема Роджерса) с проблемой инвариантности и определимости предиката относительной квазиминимальности.
А именно, е-степень а является нетотальной тогда и только тогда, когда выполнен формульный предикат
Зи)[С^(аи и, и)], что также эквалснтно выполнению другого предиката (также являющегося формульным в силу результатов параграфа 1 второй главы)
Зи) [(2 (а и и, и) & (а и и)' = и'].
Здесь С^(а, Ь) — предикат относительной квазиминимальности, означающий, что для каждой тотальной е-степени х < а справедливо х < Ь.
В параграфе 4 второй главы приводится достаточный критерий для того, чтобы тотальная е-степень разлагалась над заданной е-степенью. Данный результат может быть в будущем использован при решении вышеупомянутой проблемы Роджерса. Результаты этого параграфа получены совместно с Арслановым (Казань) и Купером (Лидс, Великобритания).
Отметим, что в параграфе 2 четвертой главы приведена еще одна характеризация тотальных е-степеней уже на языке сводимостей алгебраических систем.)
Третья глава посвящена развитию методологии построения алгебраических систем спектров степеней с заданными свойствами; в частности, со спектрами степеней, имеющих вид {х | х ^ Ь}. В параграфе 1 третьей главы, носящим вводный характер, излагается используемый в дальнейшем способ кодирования семейств множеств в алгебраические системы.
В параграфе 2 третьей главы устанавливается существование алгебраических систем, имеющих спектр степеней {х | х ^ Ь}, где Ь — произвольная низкая тьюринговая степень.
Для этого дается удобное описание спектров семейств, имеющих вид
W(TZ, v) = {{п} ®U\neu>&U eKkU ф z/(n)}, где 7Z — некоторое вычислимо перечислимое семейство, содержащее все конечные множества (например семейство всех конечных множеств или семейство всех вычислимо перечислимых множеств), а и — некоторая вычислимая нумерация В частности, из описания следует, что спектр степеней таких семейств не зависит от выбора семейства 1Z. Кроме того, выделяются такие нумерации v (названные CS-нумерациями), для которых описание спектра степеней семейства W(7Z, v) наиболее просто. Вычислимых С ¿/-нумераций ДЦ множеств оказывается достаточно, чтобы получить спектры степеней вида {х ¡ х % Ь}, где b — произвольная низкая тьюринговая степень: если В Е Ь, то v = Xn[Wrf] будет вычислимой Сб'-нумерацией Д® множеств, и спектр степеней семейства W( 1Z, v) в точности будет иметь вид {х | х ^ Ь}.
Кроме того, в данном параграфе приводится метод, позволяющий строить алгебраические системы сводящиеся друг к другу в слабом смысле, но не сводящиеся в сильном смысле, даже если позволить обагощать системы конечным числом констант. Этот метод найдет применение как в четвертой главе (параграф 2), так и в пятой главе (параграф 3).
В параграфе 3 третьей главы доказана вложимость произвольной счетной дистрибутивной решетки в структуры слабых степеней алгебраических систем. Кроме того, здесь найдено некоторое патологическое свойство структуры сильных и слабых степеней. А именно, установлено, что существуют возрастающие цепочки алгебраических систем (относительно рассматриваемой сводимости), имеющие в качестве точной верхней грани некоторую другую алгебраическую систему. При доказательстве этих результатов продолжается изучение спектров степеней семейств \ViJZ, I/), начатое в предыдущем параграфе. В частности, рассматриваются соотношения между теоретико-множественными операциями на спектрах степеней семейств вида и) (пересечение и объединение спектров) и операциями на нумерациях (прямая сумма и прямое произведедение). Изучаются также и бесконечные суммы нумераций.
В параграфе 4 третьей главы устанавливается существование алгебраических систем, имеющих спектр степеней {х | х ^ Ь}, где Ь — произвольная вычислимо перечислимая тьюринговая степень. В частности, существует алгебраическая система, спектр степеней которой есть {х | х ^ 0'}.
Семейства, исследованые в первых двух параграфах третей главы, не могут быть здесь использованы: если 71 — вычислимо перечислимое семейство, содержащее все конечные множества, ни — вычислимая нумерация Д®, то спектр степеней семейства УУ(7^, у) содержит все не-низкие степени. Поэтому, здесь рассматриваются семейства вида УУ(7-\ £В), где V — семейство всех областей значений возрастающих примитивно рекурсивных функций {V состоит только из бесконечных множеств), ев = \п[\¥в], и В 6 Ь — вычислимо перечислимое множество (здесь Ь не обязательно является низкой степенью, так что ев вообще говоря не будет нумерацией Д<] множеств). Устанавливается, что спектр семейства УУ(Р,£В) есть {х | х ^ Ь}.
Четвертая глава посвящена в основном теоретическим результатам, ограничивающим методологию развитую в третьей главе. Одновременно с этим получены некоторые решения проблем, касающихся спектров степеней и различий сильной и слабой сводимости.
В параграфе 1 четвертой главы доказана нерешеточность верхних полурешеток сильных и слабых степеней алгебраических систем.
Для этого устанавливается, что если несравнимые степени ао и ах лежат в спектре степеней счетной алгебраической системы, то этот, же спектр степеней должен содержать также некоторую степень Ь такую, что ао ^ Ь, ах ^ Ь и Ь' < а^. Оценка Ь' < а^ вместе с результатами из параграфа 1 третей главы, позволяет сделать вывод о том, что две алгебраические системы, имеющие спектры степеней {х | х > ао} и {х | х > ах}, соответственно, не имеют точной нижней грани относительно слабой сводимости, если степени ао и а.1 несравнимы и являются низкими. Выбирая две конкретные алгебраические системы с указанными выше спектрами степеней, можно распространить данное утверждение и на сильную сводимость алгебраических систем.
В параграфе 2 четвертой главы дается характеризация тотальных е-степеней как е-степеней таких алгебраических систем, сильная и слабая сводимости к которым не отличаются между собой (даже с точностью до конечных обогащений константами).
Для этого для каждой алгебраической системы, не имеющей степени, среди тыоринговых скачков спектра степеней которой имеется наименьший, строится другая алгебраическая система, слабо сводящаяся к первой (то есть неравномерно), но несводщаяся к ней сильно (то есть равномерно), даже если разрешить обогащать системы конечным числом констант.
В параграфе 3 четвертой главы приводится отрицательный ответ на вопрос Миллера [28] об отделимости несравнимых степеней спектрами степеней линейных порядков.
Более того, установлено, что для каждой ненулевой степени а существует такая несравнимая с а степень Ь, Ь' < а', содержащаяся во всех спектрах степеней счетных линейных порядков, в которых содержится степень а.
Приводятся косвенные аргументы в пользу отрицательного ответа на вопрос Доуни [17] о существовании линейных порядков со спектром степеней {х | х > 0}.
В параграфе 4 четвертой главы устанавливается существование тьюринговой степени b < такой, что совокупность {х | х ^ Ь} не является спектром степеней никакой алгебраической системы.
Для этого, устанавливается, что для каждой пары несравнимых степеней ао и ai существует такая степень b < (aoUai)(4), что ао ^ Ь, ai ^ Ь, и каждый спектр степеней алгебраической системы, содержащий степени а0 и ai должен содержать также степень Ь. В отличие от указанного выше результата из параграфа 1 четвертой главы здесь степень b не зависит от фиксированной заранее алгебраической системы со своим спектром степеней. Однако здесь установленная ранее оптимальная оценка b' < а() ухудшается до b < (a0Uai)(4) (от оценки скачка степени b всего лишь однократным скачком одной из степеней cío и ai до оценки только лишь самой степени b четырехкратным скачком точной верхней грани степеней ао и ai). Отметим также, что в силу вышеупомянутого результата из второго параграфа оптимальная оценка сохраняется, если вместо произвольных алгебраических систем ограничится лишь линейными порядками. В параграфе 5 четвертой главы основной результат параграфа 4 усиливается, посредством построения степени b < 0" такой, что совокупность {х | х ^ Ь} не является спектром степеней никакой алгебраической системы.
Для этого, в отличие от предыдущего параграфа, устанавливается, что для каждой ненулевой степени ао существуют такие степени ai < а'о и b < а'о, что ао ^ b, ai Ь, и каждый спектр степеней алгебраической системы, содержащий степени ао и ¿i, должен содержать также степень Ь. При доказательстве этого утверждения используется метод приоритета с бесконечными нарушениями, а также техника работы со степенями по перечислимости.
Пятая глава посвящена изучению е-сводимостей алгебраических систем, основанных на сводимости частичных проблем представимости, введенных Дымент [1]. В частности, оценивается возможность применения методов, разработанных в предыдущих главах для изучения спектров е-степеней и е-сводимостей алгебраических систем.
В параграфе 1 пятой главы исследуются спектры е-степеней семейств множеств, натуральных чисел. Доказывается, что спектр е-степеней семейства всех бесконечных вычислимо перечислимых множество совпадает с классом высоких е-степеней (то есть е-степеней, скачок которых ограничен снизу двойным скачком нулевой е-степени). Для доказательства используется аналог леммы о пределе для сводимости по перечислимости, полученной в параграфе 1 второй главы.
Кроме того, устанавливается, что в отличие от результатов об обычных спектрах степеней семейств из третей главы спектр е-степеней семейств конечных множеств не может совпадать с классом всех ненулевых е-стеиеней.
Наконец, доказывается, что спектр е-степеней семейства б") состоит в точности из ненулевых е-степеней (где Е — семейство всех вычислимо перечислимых множеств, иг = Лп[Ж„]). Откуда следует, что существует алгебраическая система со спектром е-степеней, совпадающим с классом всех ненулевых е-степеней. То же самое оказывается верным, если вместо понятия спектра е-степеней использовать понятие расширенного спектра степеней, введенного Сосковым [41].
В параграфе 2 пятой главы исследуется важный частный случай е-сводимости алгебраических систем, связанный с £-определимостью в допустимых множествах. Здесь проводится сравнительный анализ выразительной мощности Е-определений относительно простейших не вычислимо переслимых семействах вычислимо перечислимых множеств (семейство графиков всюду определенных функций, семейство бесконечных вычислимо перечислимых множеств и проч.). Обсуждается проблема введения операции скачка для Е-степеней семейств. Результаты этого параграфа получены совместно с Пузаренко (Новосибирск).
В параграфе 3 пятой главы полностью описываются все возможные соотношения между сильной сводимостью, слабой сводимостью, сильной е-сводимости, слабой е-сводимостью алгебраических систем, также как и отношения Е-определимости одной системы в конечно-наследственной надстройке другой (см. [2]).
А именно, установлено, что соотношения между рассматриваемыми сводимостями исчерпываются нижеперечисленными:
• из Е-определимости одной системы в конечно-наследственной надстройке другой без параметров следует сильная е-сводимость первой системы ко второй;
• из сильной сводимости следует слабая сводимость;
• из сильной е-сводимости следует слабая е-сводимость;
• из сильной е-сводимости следует сильная сводимость;
• из слабой е-сводимости следует слабая сводимость.
Данное описание остается верным, если в определении сводимостей разрешить обогащать системы конечным числом констант.
Данный параграф завершает исследование рассматриваемых соотношений, начатое Стукачевым в работе [10]. При доказательстве используются результаты из параграфа 1 второй главы, параграфа 1 третьей главы и первых двух параграфов пятой главы.
На защиту выносятся следующие результаты:
• Решение проблемы определимости операции скачка е-степеней, поставленной Купером [16] и Сорби [40].
• Определимость класса тотальных е-степеней, расположенных выше 07е, что частично решает проблемы Роджерса об определимости класса тотальных е-степеней. Характеризации класса тотальных е-степеней посредством предиката относительной квазиминимальности, а также на языке сильных и слабых сводимо-стей алгебраических систем.
• Решение проблемы Миллера [28] об отделимости несравнимых степеней спектрами степеней линейных порядков.
• Построение алгебраических систем, спектр степеней которых имеет вид {х|х ^ Ь}, где b — низкая или вычислимо перечислимая степень.
• Построение степени b < О" такой, что совокупность {х|х ^ Ь} не является спектром степеней никакой алгебраической системы.
• Вложимость произвольной счетной дистрибутивной решетки в слабые степени алгебраических систем с сохраниением точных верхних и нижних граней. Нерешеточность верхних полу решеток сильных и слабых степеней алгебраических систем.
• Полное описание всех возможных соотношений между сильной сводимостью, слабой сводимостью, сильной е-сводимости, слабой е-сводимостыо и отношения Е-опредлимости.
Результаты главы 2 опубликованы в работах автора [1],[2], [9], [10], [11], [13], [15], [18] (см. список публикаций автора по теме диссертации в конце диссертации), главы 3 - в работах [3], [4], [14], [17], главы 4 -в работах [5], [7], [17], главы 5 - в работах [6], [8], [12], [16].
Результаты диссертации по мере их получения докладывались на следующих конференциях:
Logic Colloquium 2001, Вена, Австрия, 6-11 августа 2001 г.
Computability and Models, Алматы, Казахстан, 24-28 июня 2002
Logic Colloquium 2002, Мюнстер, Германия, 3-10 августа 2002 г.
British Mathematical Colloquium 2003, Берингем, Великобритания, 7-10 апреля 2003 г.
Алгебра и Анализ 2004, 2 - 9 июля 2004, Казань;
Мальцевские чтения 2004, Новосибирск, 16-18 ноября 2004 г.
Methods of Logic in Mathematics 2005, Санкт-Петербург, 18-24 июля 2005 г.
Computational prospects of infinity, Сингапур, лето 2005 г.
Мальцевские чтения 2005, Новосибирск, 15-17 ноября 2005 г.
Computabilty in Europe 2006, Суонси, Великобритания, 30 июня -5 июля 2006 г.
Мальцевские чтения 2006, Новосибирск, 14-16 ноября 2006 г.
Computabilty in Europe 2007, Сиена, Италия, 16-18 июня 2007 г.
Мальцевские чтения 2008, Новосибирск, 11-13 ноября 2008 г.
Итоговые научные конференции Казанского университета, 2002 -2008.
Результаты докладывались на семинаре Алгебра и логика (Новосибирск, ИМ СО РАН, рук. - академик Ершов Ю.Л.), логическом семинаре Отделения Математики университета Лидса (Великобритания, рук. - проф. С. Вейнер, проф. C.B. Купер), логическом семинаре математического факультета Висконсинского университета (США, рук. проф. С. Лемпп), семинаре по теории вычислимости Чикагского университета (США, рук. проф. Р. Соар), логическом семинаре математического факультета университета Ватерлоо (Канада, рук. - Р. Виллард). В целом работа доложена на семинаре по теории вычислимости на механико-математическом факультете Казанского государственного университета (рук. - проф. М.М. Арсланов).
Автор выражает глубокую благодарность М.М. Арсланову за постоянное внимание к работе и плодотворные беседы, способствовавшие улучшению диссертации.
1. Е. 3. Дымент; О некоторых свойствах решетки Медведева, Ма-тем. сборник, 101 (1976), 360-379.
2. Ю.Л. Ершов; Определимость и Вычислимость, Научная книга, Новосибирск, Экономика, Москва, 2000.
3. И.Ш. Калимуллин; Об элементарных теориях п-в.п. степеней по перечислимости, Известия Вузов. Математика, № 4 (2001), 24-27.
4. И.Ш. Калимуллин, В.Г. Пузаренко; О сводимости на семействах, Алгебра и логика, № 1 (2001), 33-51.
5. Ю.Т. Медведев; Степени трудности массовых проблем, ДАН СССР, 104 (1955), 501-504.
6. A.A. Мучник; О сильной и слабой сводимости алгоритмических про- блем, Сиб. матем. журнал, 4 (1963), 1328-1341.
7. A.C. Морозов, В.Г. Пузаренко; О Е-подмножествах натуральных чисел, Алгебра и логика, 43, №3(2004), 291 320.
8. М.Г. Розинас; Полурешетка е-степеней, Рекурсивные функции, Ива- ново, Ивановский гос. университет, 71-84, 1978.
9. В. Л. Селиванов; Об индексных множествах вычислимых классов конечных множеств, Алгориты и Автоматы, под ред. М.М. Арсланова, Казань, 1978, 95-99.
10. А.И. Стукачев; О степенях представимости моделей. I, Алгебра и логика, 6 (2007), 763-788
11. S. Ahmad; Embedding the diamond in the E2 enumeration degrees, J. Symbolic Logic, 50 (1991), 195-212.
12. S. Ahmad, A.H.Lachlan; Some special pairs of E2 e-degrees properties of E2— enumeration degrees, Math. Logic Quarterly, 44 (1998) ,431-449.
13. M.M. Arslanov, A. Sorbi; Relative splittings of 0'e in the enumeration degrees, In Buss S. and Pudlak P., editors, Logic Colloquium '98. Springer-Verlag, 1999.
14. H.G. Carstens; Д^-mengen, Arch.Math. Log. Grundlag., 18 (1978), 55 65.
15. S.B. Cooper; Partial degrees and the density problem. Part 2: The enumeration degrees of the E2 sets are dense, J. Symbolic Logic, 49 (1984), 503-513.
16. R. Downey; On presentations of algebraic structures, Complexity, Logic, and Recursion Theory, ed. A. Sorbi (New York: Dekker, 1997), 157-205.
17. Richard J. Coles, R.G. Downey, T.A. Slaman; Every set has a least jump enumeration. J. London Math. Soc., 62(2000), 641-649.
18. S.S. Goncharov, V.S. Harizanov, J.F. Knight, C. McCoy, R.G. Miller, R. Solomon; Enumerations in computable structure theory, Annals of Pure and Applied Logic, 136, 3 (2005), 219-246.
19. L. Gutteridge; Some results on enumeration reducibility, PhD thesis, Simon Fraser University. 1971.
20. V.S. Harizanov, R. Miller; Spectra of structures and relations, Journal of Symbolic Logic, 72 (2007), 324-348.
21. D.R. Hirschfeldt, B. Khoussainov, R.A. Shore, A.M. Slinko; Degree spectra and computable dimensions in algebraic structures, Annals of Pure and Applied Logic, 115 (2002), 71-113.
22. C.G. Jockusch, Jr.; Semirecursive sets and positive reducibility, Trans. Amer. Math. Soc., 131 (1968), 420-436.
23. C.G. Jockusch, Jr.; Degrees in which the recursive sets are uniformly recursive, Canad. J. Math., 24 (1972), 1092-1099.
24. J.F. Knight; Degrees coded in jumps of orderings, J. Symbolic Logic, 51 (1986), 1034-1042.
25. K. McEvoy; Jumps of quasi-minimal enumeration degrees, J. Symbolic Logic, 50 (1985), 839-848.
26. K. McEvoy, S.B. Cooper; On minimal pairs of enumeration degrees, J. Symbolic Logic, 50 (1985), 983-1001.
27. R.G. Miller; The Ail-spectrum of a linear order, J. Symbolic Logic 66 (2001), 470-486.
28. A. Nies; Lowness properties and randomness, Advances in Mathenatics, 197 (2005), 274-305.
29. D. Posner, R.W. Robinson; Degrees joning to 0', J. Symbolic Logic, 46 (1981), 714-722.
30. L.J. Richter; Degrees of structures, J. Symbolic Logic, 46 (1981), 723-731.
31. H. Rogers, Jr.; Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967.
32. A.L. Selman; Arithmetical reducibilities. I. Z. Math. Logik Grundlag. Math., 17(1971), 335-350.
33. R.A. Shore; Local definitions in degree structures: the turing jump, hyperdegrees and beyond, Bull. Symbolic Logic, 13 (2007), 226-238.
34. R.A. Shore, T.A. Slaman; Defining the Turing jump, Math. Research Letters, 6 (1999), 711-722.
35. T. Slaman; Degree structures, Proceedings of the international congress on mathematics, Kyoto (1990), Springer-Verlag, Tokyo, 303-316.
36. T. Slaman; Relative to any nonrecursive set, Proc. Amer. Math. Soc., 126 (1998), 2117-2122.
37. R.I. Soare; Recursively enumerable sets and degrees, Heidelberg: Springer-Verlag, 1987.
38. A. Sorbi; The enumeration degrees of £<] Complexity, Logic, and Recursion Theory, ed. A. Sorbi (New York: Dekker, 1997), 303330.
39. A. Sorbi; Open problems in the enumeration degrees //In P.A. Cholak, S. Lempp, M. Lerman, and R.A. Shore, Contemporary Mathematics 257, American Mathematical Society, Providence, 2000, C. 839-848.
40. I.N. Soskov; Degree spectra and co-spectra of structures, Ann. Univ. Sofia, 96 (2003), 45-68
41. S. Weimer; Enumerations, countable structures, and Turing degrees, Proc. Amer. Math. Soc., 126 (1998), 2131-2139.
42. C.E.M. Yates; On the degrees of index sets II, Trans. Amer. Math. Soc., 135 (1969), 249-266.Список публикаций автора по теме диссертации
43. Арсланов М.М., Калимуллин И.Ш., Купер С.Б. Свойства разложения тотальных степеней по перечислимости // Алгебра и Логика. 2003. - Т. 42, № 1. - С. 3-25.
44. Калимуллин И.Ш., Пузаренко В.Г. О принципах вычислимости на допустимых множествах // Мат. Труды. 2004. - Т. 7, № 2,- С. 35-71.
45. Калимуллин И.Ш. Спектры степеней некоторых алгебраических структур // Алгебра и Логика. 2007. - Т. 46, № 6. - С. 729-744.
46. Калимуллин И.Ш., Почти вычислимо перечислимые семейства множеств // Математический сборник. 2008. - Т. 199, № 10. -С. 33-40
47. Калимуллин И.Ш., Ограничения на спектры степеней алгебраических структур // Сибирский мат. журнал. 2008. - Т. 49, №6.- С. 1296-1309.
48. Калимуллин И.Ш., Пузаренко В.Г. О сводимости на семействах // Алгебра и логика 2009. - № 1. - С. 33-51.
49. Калимуллин И.Ш. Равномерность сводимостей алгебраических систем // Сибирский мат. журнал 2009. - № 2. - С. 334-343.
50. Калимуллин И.Ш. Соотношения между алгоритмическими сво-димостями алгебраических систем // Известия ВУЗов 2009. -№6. - С. 71-72.
51. Kalimulllin I.Sh. Splitting properties of n-c.e. enumeration degrees //J. Symbolic Logic. 2002. - V. 67. - P. 537-546.
52. Kalimulllin I.Sh. Definability of the jump operator in the enumeration degrees //J. Mathematical Logic. 2003. - № 2. -P. 257-267.
53. Kalimullin I.Sh. Elementary differences between the (2p)-c.e. and the (2p+ l)-c.e. enumeration degrees. //J. Symbolic Logic. 2007.- V. 72, № 1. P. 277-284.
54. Kalimullin I. Sh., Enumeration degrees and enumerability of familes // Journal of Logic and Computation. 2009. - V.19. - № 1. - P. 151-158.
55. Арсланов M.M., Калимуллии И.Ш. Исследования по теории вычислимости //В книге "На рубеже веков. НИИММ Казанского университета". Казань, изд-во Казан, матем. общества. - 2003.- С. 50-68.
56. Kalimullin I.Sh. On primitive recursive permutations // In: Cooper S.B., Goncharov S.S. eds. Computability and models. New York, NY: Kluwer Academic/Plenum Publishers 2003. - P. 249-258.
57. Kalimullin I.Sh. On the problems of definability in the enumeration degrees // Lecture Notes in Computer Science. 2005. - V. 3526. -P. 221-222.
58. Kalimullin I.Sh. The Dyment reducibility on the algebraic structures and on the families of subsets of omega // Proceedings of the Second Conference on Computability in Europe (CiE 2006), University of Wales Swansea 2006. - № CSR 7-2006. - P. 150-159
59. Kalimullin I.Sh. Some notes on degree spectra of the structures // Lecture Notes in Computer Science. 2007. - V. 4497. - P. 389-398.
60. Arslanov M. M., Cooper S.B., Kalimullin I.Sh., Soskova M.I., Total degrees and nonsplitting properties of enumeration degrees //1.cture Notes in Computer Science. 2008. - V. 4978. - C. 568-578
