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

• Калимуллин, Искандер Шагитович
• доктор физико-математических наук
• 2009

Оглавление диссертации доктор физико-математических наук Калимуллин, Искандер Шагитович

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. Купер), логическом семинаре математического факультета Висконсинского университета (США, рук. проф. С. Лемпп), семинаре по теории вычислимости Чикагского университета (США, рук. проф. Р. Соар), логическом семинаре математического факультета университета Ватерлоо (Канада, рук. - Р. Виллард). В целом работа доложена на семинаре по теории вычислимости на механико-математическом факультете Казанского государственного университета (рук. - проф. М.М. Арсланов).

Автор выражает глубокую благодарность М.М. Арсланову за постоянное внимание к работе и плодотворные беседы, способствовавшие улучшению диссертации.

Список литературы диссертационного исследования доктор физико-математических наук Калимуллин, Искандер Шагитович, 2009 год

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