Вычислимые линейные порядки и естественные отношения на них тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

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

Бикмухаметов Равиль Ильдарович

Вычислимые линейные порядки и естественные отношения на них

01.01.06 - Математическая логика, алгебра и теория чисел

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

" ПАР 2015

005560516

Казань - 2015

005560516

Работа выполнена на Кафедре алгебры и математической логики ФГАОУ В ПО "Казанский (Приволжский) федеральный университет". Научный руководитель: Фролов Андрей Николаевич,

доктор физико-математических наук, старший научный сотрудник, ФГАОУ ВПО "Казанский (Приволжский) федеральный университет" Официальные оппоненты: Алаев Павел Евгеньевич,

доктор физико-математических наук, ведущий научный сотрудник, ФГБУН Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук, Коровина Маргарита Владимировна,

кандидат физико-математических наук, старший научный сотрудник, ФГБУН Институт систем информатики им. А.П. Ершова Сибирского отделения Российской академии наук.

Ведущая организация : ФГБУН Институт математики и механики им. Н.Н.Кра-совского Уральского отделения Российской академии наук.

Защита состоится 26 марта 2015 г. в 14.30 на заседании диссертационного совета Д 212.081.24 при ФГАОУВПО "Казанский (Приволжский) федеральный университет" по адресу: 420008, г. Казань, ул. Кремлевская, д. 35., каб. ш

С диссертацией можно ознакомиться в библиотеке и на сайте Казанского (Приволжского) федерального университета.

Автореферат разослан « ¿о ъСр1€раЛ<£л.01 я г. Ученый секретарь

диссертационного совета Д 212.081.24

к.ф.-м.н., доц. —Еникеев А.И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Более обще, теория вычислимых моделей занимается изучением вопросов эффективности алгебраических структур и моделей. История изучения подобных структур обширна и берет начало с работ Д. Гильберта и М. Де-на. Отечественные исследования в этом направление и становление вычислимой теории моделей как самостоятельного направления современной математической логики обязаны трудам выдающегося математика академика А. И. Мальцева [5], [6]. Одним таким классическим примером изучаемым в рамках этой теории являются вычислимые линейные порядки. Вычислимые линейные порядки широко исследовались многими авторами такими, как Р. Ганди [32], Р. Доуни [21, 22], Р. Доуни и Дж. Найт[25], Р. Доуни и М. Мозес [24], М. Мозес[37, 38, 39] X. Райе[42], Л. Фейнер[27, 29], А. Н. Фролов [9, 30, 10, 11, 12, 13], Дж. Харрисон [33], Чен [17], Дж. Чишолм и М. Мозес [18], К. Эш [16] и др.

На протяжение истории изучения линейных порядков формировался круг наиболее естественных отношений на них, а именно, отношения соседства 5, блока .Р, плотности с?п, предельности справа Р+, предельности слева Р~. Данные отношения исследовались многими авторами при изучении линейных порядков, их структурных свойств и классификации. М. Мозес [37, 38] показал, что линейный порядок имеет 1-разрешимое представление тогда и только тогда, когда он имеет вычислимое представление с вычислимым отношением соседства. С. С. Гончаров и В. Д. Дзгоев[3] и Дж. Реммел[44] показали, что вычислимый линейный порядок является вычислимо категоричным тогда и только тогда, когда он имеет только лишь конечное число соседних элементов. А. Фролов [13] показал, что линейный порядок является низким тогда и

только тогда, когда он имеет 0'-вычислимое представление с 0'-вычислимым отношением соседства. Г. Ву, Р. Доуни, Ш. Лемпп [26] и А. Фролов [9] в совокупности показали, что спектр отношения соседства либо тривиален, либо замкнут наверх в в.п. степенях.

Отношение блока исследовались, например, в работах М. Мозеса [37, 38], где было показано, что отношение блока вычислимо категоричного 1-раз-решимого линейного порядка является вычислимым. Все введенные выше отношения использовались в работе Дж. Тёрбера[46], который исследовал 2-низкие булевы алгебры, порожденные линейными порядками. Также данные отношения использовались в работе П. Е. Алаева, Дж. Тёрбера, А. Н. Фролова [1] для исследования 2-низких квазидискретных линейных порядков. М. Зубков [4] исследовал отношения соседства и блока на начальных сегментах вычислимых линейных порядков, что позволило ему получить более простое доказательство теоремы Коулза-Доуни-Хусаинова [19] о существовании вычислимого линейного порядка с неконструктивизируемым Щ-начальным сегментом. Отношения соседства, предельности справа, предельности слева использовались в работе А. Фролова [30] для описания 2-низких линейных порядков. А именно, им было показано, что 0"-вычислимость структуры {М, <£, Б с, Рс), где С = (М, <с) — линейный порядок, влечёт суще-

ствование 2-низкого представления порядка С. Этот результат для специальных классов линейных порядков имеет более простой вид: если С — (М, <с) — дискретный или разреженный линейный порядок, то 0"-вычислимость структуры (М, <с, 5'с, Р£} Р^) влечет существование 2-низкого представления порядка С. Если же £ = (М, <с) — квазидискретный линейный порядок, то из 0"-вычислимости структуры (М, <с, Б с, Рслйпц, Р£, Р^) следует, что С имеет 2-низкое представление. Изучению арифметической сложности всех введенных выше отношений также посвящена недавняя магистерская работа У. П. Тернера [47]. Из последних результатов видно, что отношения соседства

5, блока Р, плотности <1п, предельности справа Р+, предельности слева Р~ играют важную роль в исследование линейных порядков.

Классический результат [21] о существование вычислимого, но не 1-вычи-слимого линейного порядка является непосредственным следствием теоремы о существовании вычислимого линейного порядка С, имеющего порядковый тип и), такого, что отношение соседства Бс невычислимо. Нетрудно видеть, однако, что отношения Рс, сЬпс, Р£, Р^ вычислимы. Следовательно, вычислимость отношений блока Рц, плотности йпс, предельности справа и предельности слева Р^ вычислимого линейного порядка £ не влечет вычислимости отношения соседства £х. Возникает вопрос об описании возможной зависимости естественных отношений на вычислимых линейных порядках.

Проблема 1. Получить описание зависимости естественных отношений соседства 5, блока Р, плотности с1п, предельности справа Р+, предельности слева Р~ на вычислимых линейных порядках.

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

Определение 1. Набор отношений Т\ назовем алгоритмически зависимым на вычислимых представлениях линейных порядков от набора отношений ■рг, если для любого линейного порядка вычислимость отношений из 7-2 в некотором его вычислимом представлении влечет существование такого его вычислимого представления, что на нем вычислимы все отношения из набора Тх.

Проблема 2. Описать зависимость естественных отношений соседства £>, блока .Р, плотности (1п, предельности справа Р+, предельности слева Р~ на вычислимых представлениях линейных порядков.

Первый результат в этом направлении был получен М. Мозесом [37], который показал, что вычислимость отношения блока Ра в некоторой вычислимой копии Л произвольного порядка С влечет существование такого его вычислимого представления В, что отношение соседства 5в вычислимо. Таким образом, отношение блока и соседства являются алгоритмически зависимыми в вышеуказанном смысле, а именно, если = {>?} и р2 Э -Р, то алгоритмически зависит от на вычислимых представлениях линейных порядков. Дж. Реммелом и С. С. Гончаровым было показано, что существует вычислимый линейный порядок С, такой, что в любой его вычислимой копии отношение соседства Б с невычислимо. Можно заметить, что (см., например [21]) этот результат также доказывается кодированием 0'-вычислимого линейного порядка £, не имеющего вычислимого представления, в вычислимый линейный порядок С, имеющий порядковый тип (т] + 2 + т]) ■ С. Нетрудно видеть, что порядок С является искомым. Подобные конструкции кодирования линейных порядков играют важную роль в теории. К примеру, первый пример нетривиального, то есть невычислимого линейного порядка, был построен Фейнером [27, 29], который показал, что для любого бесконечного £3-множества М, не содержащего 0, существует вычислимый линейный порядок типа

С + п0 + С + + ■ • •,

где по, пх, ... перечисление М в порядке возрастания. Здесь £ обозначает тип естественного порядка целых чисел Линейный порядок такого типа называется сильным (-представлением множества М. Ясно, что данное кодирование допускает релятивизацию. Тогда, взяв в качестве М произвольное Е^-множество, не являющееся ЕЦ-множеством, получаем, что сильное представление множества М имеет 0'-вычислимое представление и не изоморфно никакому вычислимому линейному порядку. Используя различные вариан-

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

В третьей главе изучаются начальные сегменты линейных порядков. Начальные сегменты вычислимых линейных являются классическим примером подструктуры линейного порядка и предметом многочисленных исследований [32, 43, 19, 15, 4]. Отметим, что сложность начального сегмента вычислимого линейного порядка может быть очень высокой. Согласно результатам Р. Ганди [32] и Дж. Харрисона[33], существует вычислимый линейный порядок с начальным сегментом, изоморфным — наименьшему неконструктивному ординалу. М. Роу [43] показал, что П^-начальный сегмент вычислимого линейного порядка имеет вычислимое представление. С другой стороны, им был построен пример вычислимого линейного порядка с неконструктиви-зируемым Пз-начальным сегментом. Р. Коулз, Р. Доуни и Б. Хусаинов [19] показали, что существует вычислимый линейный порядок с П^-начальным сегментом, не изоморфным никакому вычислимому линейному порядку. Заметим, что доказательство последнего результата использует метод приоритета с бесконечными нарушениями. Более простое доказательство, использующее только лишь приоритет с конечными нарушениями, получено М. В. Зубко-вым[4]. Для этого им были рассмотрены линейные порядки с добавленными предикатами — отношением соседства и блока. Другими словами, такие структуры (Ь, <£, Бс) и (Ь, <с, ^г), где С, — (Ь, <с) — линейный порядок. В частности, им были построены такие вычислимые структуры (Ь, <с, 5с) и {Ь, <£, -Рс), что их П^-начальные сегменты не имеют вычислимых представлений. Естественным образом возникает вопрос о справедливости вышеуказанных результатов для оставшихся естественных отношений плотности йп, предельности справа Р+ и предельности слева Р~.

Проблема 3. Верно ли, что существуют такие структуры (Ь, <с, йпц), (Ь, <ц , Р£) и (Ь, <£, что их начальные сегменты не имеют вычислимых представлений?

В совместной работе К. Амбос - Шпис, С. Б. Купер и С. Лемпп [15] показали, противоположно результату Р. Коулза, Р. Доуни и Б. Хусаинова, что каждый Е°-начальный сегмент любого вычислимого линейного порядка имеет вычислимую копию. Естественным дополнением к этому результату является решение следующей проблемы.

Проблема 4. Верно ли, что каждый вычислимый линейный порядок без наибольшего элемента является Е^-начальным сегментом наперед заданной Ез-степени некоторого вычислимого линейного порядка?

Уточнение отсутствия наибольшего элемента существенно, поскольку, если вычислимый линейный порядок имеет наибольший элемент, то он может быть только вычислимым (т.е. Ео-) начальным сегментом.

Цели и задачи исследование. Целями настоящей работы являются:

I. исследование алгоритмической зависимости естественных отношений соседства 5, блока Г, плотности <1п, предельности справа Р+ и предельности слева Р~ на вычислимых линейных порядках и на вычислимых представлениях линейных порядков;

II. исследование алгоритмической сложности начальных сегментов вычислимых линейных порядков с добавленными отношениями плотности в,п, предельности справа Р+ и предельности слева Р~, соответственно, и начальных сегментов, принадлежащих арифметическому уровню сложности иерархии множеств.

Следующие задачи исследования можно выделить в качестве основных:

1. получить описание алгоритмической зависимости естественных отношений соседства 5, блока Р, плотности ¿п, предельности справа Р+ и предельности слева Р~ на вычислимых линейных порядках и на вычислимых представлениях линейных порядков;

2. построить вычислимые линейные порядки с добавленными отношениями плотности с1п, предельности справа Р+ и предельности слева Р~, соответственно, начальные сегменты которых не имеют вычислимых представлений с вычислимыми отношениями плотности <1п, предельности справа Р+ и предельности слева Р~\

3. доказать, что каждый вычислимый линейный порядок без наибольшего элемента является Е^-начальным сегментом наперед заданной степени некоторого вычислимого линейного порядка.

Методология и методы исследования. В диссертационной работе использованы методы теории вычислимости и теории счетных линейных порядков. Среди них можно особо выделить технику приоритета с бесконечными нарушениями и технику приоритета в комбинации с 0'-оракульной конструкцией.

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

Основные результаты диссертации. На защиту выносятся следующие основные результаты исследования:

1. Построена серия вычислимых линейных порядков, демонстрирующая алгоритмическую независимость естественных отношений соседства 5, блока 2**, плотности в,п, предельности справа Р+ и предельности слева Р~ на вычислимых линейных порядках;

2. Получено описание алгоритмической зависимости естественных отношений соседства 5, блока F, плотности йп, предельности справа Р+ и предельности слева Р~ на вычислимых представлениях линейных порядков, а именно, доказано, что нет других зависимостей, кроме той, которую установил М. Мозес [37];

3. Построены вычислимые линейные порядки с добавленными отношениями плотности с1п, предельности справа Р+ и предельности слева Р~, соответственно, такие, что их П^-начальные сегменты не имеют вычислимых представлений с вычислимыми отношениями плотности йп, предельности справа Р+ и предельности слева Р~\

4. Доказано, что каждый вычислимый линейный порядок без наибольшего элемента является Е^-начальным сегментом наперед заданной степени некоторого вычислимого линейного порядка.

Апробация работы.

По результатам диссертации были сделаны доклады:

• на международной конференции "Мальцевские чтения 2013" (Новосибирск, 2013 г.);

• на научной школе-конференции "Лобачевские чтения 2013" (Казань, 2013 г.);

• на международной конференции "Алгебра и математическая логика: теория и приложения" (Казань, 2014 г.);

• на международной конференции "Logic Colloquium 2014" (Вена, Австрия, 2014 г.);

• на международной конференции "Мальцевские чтения 2014" (Новосибирск, 2014 г.);

• на научной школе-конференции "Лобачевские чтения 2014" (Казань, 2014 г.);

• на научных семинарах и итоговых конференциях кафедры алгебры и математической логики Казанского (Приволжского) федерального университета 2013-2014 гг.

Публикации. Все основные результаты диссертации опубликованы в работах [49]—[58], из них работы [49]—[52] опубликованы в журналах, входящих в перечень ВАК рецензируемых научных журналов, в которых должны быть опубликованы основные научные результаты диссертации на соискание ученых степеней доктора и кандидата наук.

Личный вклад автора. Результаты диссертации получены автором самостоятельно.

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

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе приведены необходимые для понимания диссертационной работы предварительные термины, определения и результаты. В первом параграфе приводятся основные определения и некоторые центральные результаты теории вычислимости. Во втором параграфе даны предварительные сведения теории счетных линейных порядков и некоторые центральные результаты теории, в частности, приведены определения естественных отношений соседства S, блока F, плотности dn, предельности справа Р+ и предельности слева Р~ на линейных порядках изучению которых посвящена диссертационная работа, а именно

Определение 1.2.11. Для данного линейного порядка С = (L, <с) и для любых х,у € L определим

1) интервал: [х, у]с = {z | х z у};

2) бинарное отношение соседства: Sc{x,y) (х <с у) & [х, у]с = {х, у};

3) бинарное отношение блока: Fc(x,y) |[х,у]£ U [у, х\с\ < оо;

4) бинарное отношение плотности интервала:

dnjr(x,y) (х <с у) & (Va, b £ [х,у)с)\а <с Ь ->• 3z(a <с z <с Ь)];

5) унарное отношение предельности справа:

р£{х) Уу)\у i х ^ ^Sc{x,y)]\

аналогично,

6) унарное отношение предельности слева: Р£{х) & {\/у)\у

Вторая глава посвящена изучению зависимости естественных отношений на линейных порядках. Отправной точкой исследования главы послужил следующий фольклорный результат (см., например [21]).

Предложение 2.1.1. Существует вычислимый линейный порядок £, имеющий порядковый тип ш, такой, что отношение Бс невычислимо.

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

Следствие 2.1.2. Существует вычислимый линейный порядок С, имеющий порядковый тип ш, такой, что отношение Бс невычислимо, а отношения ГС1 йпс, Рс вычислимы.

Основной результат первого параграфа, устанавливающий алгоритмическую независимость естественных отношений, является следствием ряда теорем (2.1.З., 2.1.5.-2.1.6.), полученных в работе, и предложения 2.1.1., и сформулирован в виде

Следствие 2.1.8. Пусть V = {5, Р~, ¿п, Р+}. Для любых Т\ С V и Т>2 С V таких, что ГР\Г\'Р2 = 0 и Т^иРг = V, существует вычислимый порядок С такой, что все отношения из *Р\ невычислимы, тогда как все отношения из Т2 вычислимы.

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

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

В третьем параграфе второй главы изучается алгоритмическая зависимость естественных отношений на вычислимых представлениях линейных порядков. Для этого были получены следующие варианты 0'-кодировок линейных порядков.

Теорема 2.3.5. Линейный порядок С — (Ь, <с) имеет 0'-вычислимое представление тогда и только тогда, когда порядок (£2 + ы + £2) • С имеет вычислимое представление С с вычислимыми отношениями соседства и блока

Теорема 2.3.9. Линейный порядок С, — (Ь, <с) имеет 0'-вычислимое представление тогда и только тогда, когда порядок ((С+1)-С+??+(С+1)'С)'£ имеет вычислимое представление С с вычислимыми отношениями соседства

блока предельности слева Р^ и справа

Данные теоремы в совокупности с 0'-кодировками, полученными в работах А.Н. Фролова[10, И], М. Мозеса[37] и 0"-кодировкой, установленной Р. Ватником [48], позволяют получить полное описание алгоритмической зависимости естественных отношений на вычислимых представлениях линейных порядков.

Следствие 2.3.11. Пусть V = {Б, ^ с1п, Р~, Р+}. Тогда для любых Ри Т>2 С V таких, что Р1 и^г = = 0 и 5 е Тг влечет ^ е Ри

существует линейный порядок С такой, что все отношения из Т>2 вычислимы, а все отношения из Т3! невычислимы ни в какой его вычислимой копии С.

Первый параграф третьей главы посвящен изучению алгоритмической сложности естественных отношений на начальных сегментах вычислимых линейных порядков с добавленными предикатами. М. Зубков показал, что существуют вычислимые линейные порядки с добавленными отношениями соседства и блока соответственно, что их П^-начальные сегменты не имеют вычислимых представлений. В первом параграфе рассмотрены оставшиеся случаи для отношений плотности йп, предельности справа Р+ и предельности слева Р~. Получен ряд результатов, дающих положительный ответ на проблему 3, а именно

Теорема 3.1.4. Существует вычислимая структура {Ь, <с, (1пс) и Изначальный сегмент I этой структуры, что I не имеет вычислимого представления.

Доказательство теоремы 3.1.4 разбито на два этапа, а именно, установлены следующие результаты, доказательства которых используют технику приоритета в комбинации с 0'-оракульной конструкцией.

Предложение 3.1.5. Для двухэлементного множества М = {2,3} существует такая 0'-вычислимая функция /, что гапд(/) = М и ^-представление М типа

1 + *7 + /(0) + Т?+/(1) + Т7 + /(2) + Т7 + ... не имеет вычислимого представления с вычислимым отношением плотности.

Предложение 3.1.6. Для любого непустого множества М Е А®, не содержащего 0 и 1, такого, что М = гапд(/) для некоторой ©'-вычислимой функции /, существует такой вычислимый линейный порядок С = А + В с вычислимыми отношениями плотности йпс, предельности справа Р£ и предельности слева Р£, что Л является П^-начальным сегментом £ и г}-

представлением множества М типа

1 + + /(0) + 77 + /(1) + /7 + /(2) + г? + ...

Ясно, что теорема теорема 3.1.4. следует из предложения 3.1.б., если в качестве множества М взять двухэлементное множество М = {2,3} и функцию / из предложения 3.1.5.

Модификации предложения 3.1.5. в совокупности с предложением 3.1.6. позволяют получить аналогичные результаты для отношений предельности справа Р+ и предельности слева Р~.

Теорема 3.1.11. Существует вычислимая структура (Ь, <£, Р£) и Изначальный сегмент X этой структуры, что X не имеет вычислимого представления.

Теорема 3.1.12. Существует вычислимая структура (Ь, <с, Р£) и Изначальный сегмент X этой структуры, что X не имеет вычислимого представления.

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

Теорема 3.2.1. Для любого вычислимого линейного порядка С = (Ь, <с) без наибольшего элемента и любого множества М € Е°, существует такой вычислимый линейный порядок С = Л + г), что А является Е^-начальным сегментом ¿, А = С и Л =т М.

Таким образом, доказано, что каждый вычислимый линейный порядок без наибольшего элемента является Е^-начальным сегментом наперед заданной Е^-степени некоторого вычислимого линейного порядка.

16

В заключении излагаются итоги выполненного исследования. Изложение работы заканчивается списком литературы.

Автор выражает глубокую признательность научному руководителю Андрею Николаевичу Фролову за постановку задач, поддержку в работе и интерес к исследованиям автора, Марату Мирзаевичу Арсланову, Искандеру Шагитовичу Калимуллину, Максиму Витальевичу Зубкову и Марату Хайда-ровичу Файзрахманову за внимание к исследованиям автора и активное и плодотворное обсуждение.

Литература

[1] Алаев П., Тербер Дж., Фролов А. Н. Вычислимость на линейных порядках, обогащенных предикатами // Алгебра и Логика. - 2009. - Т. 48, -№ 5. - С. 549-563.

[2] Арсланов М. М. Рекурсивно перечислимые множества и степени неразрешимости. - Казань: изд-во КГУ. - 1986. - 206 с.

[3] ГончаровС. С., ДзгоевВ.Д. Автоустойчивость моделей// Алгебра и логика - 1980. - Т. 19, - № 1. - С. 45-58.

[4] Зубков М. В. О начальных сегментах вычислимых линейных порядков с дополнительными вычислимыми предикатами // Алгебра и логика.

- 2009. - Т. 48, - № 5. - С. 564-579.

[5] Мальцев А. И. Конструктивные алгебры. I // УМН, 16:3(99) (1961), 3-60.

[6] Мальцев А.И. О рекурсивных абелевых группах // Доклады Акад. наук СССР, - 1962. - Т. 146, - №5. - С.1009-1012.

[7] Роджерс X. Теория рекурсивных функций и эффективная вычислимость. - М.: Мир, 1972. - 624 с.

[8] Соар Р.И. Вычислимо перечислимые множества и степени. - Казань: Казанское математическое общество, 2000. - 576 с.

[9] Фролов А. Н. Представления отношения соседства вычислимого линейного порядка // Известия ВУЗов. Математика. - 2010. - № 7. - С. 73-85.

[10] Фролов А. Н. А2-копии линейных порядков // Алгебра и логика. - 2006.

- Т. 45, - № 3. - С. 354-370.

[11] Фролов А. Н. Линейные порядки. Теоремы кодирования // Учён. зап. Казан, гос. ун-та. Сер. Физ.-матем. науки. - 2012. - Т. 154, - № 2. -С. 142-151.

[12] Фролов А. Н. Ранги rj-функций г/-схожих линейных порядков // Изв. вузов. Матем. - 2012. - № 3. - С. 96-99.

[13] Фролов А. Н. Линейные порядки низкой степени // Сиб. матем. журн. - 2010. - Т. 51, - № 5. - С. 1147-1162.

[14] Шенфилд Дж. Степени неразрешимости. - Москва: Наука, 1977. - 192

[15] Ambos-Spies К., Cooper S. В., Lempp S. Initial Segments of Recursive Linear Orders // Order. - 1997. - V. 14, - №. 2. - P. 101-105.

[16] Ash C. J. Categoricity in the hyperarithmetical degrees // Annals of pure and applied logic. - 1987. - V. 34, - P. 1-34.

[17] Chen К. H. Recursive well founded linear orderings // Annals of mathematical logic. - 1978. - V. 13. - P. 117-147.

[18] Chisholm J., Moses M. Undecidable linear orderings that are nrecursive for each n: to appear.

[19] Coles R. J., Downey R. G., Khoussainov B. On Initial Segments of Computable Linear Orders // Order. - 1997. - V. 14, - № 2. - P. 107-124.

[20] S. B. Cooper. Partial Degrees and the Density Problem. Part 2: The Enumeration Degrees of the Sets are Dense // The Journal of Symbolic Logic. - 1984. - V. 49, - № 2. - P. 503-513.

[21] Downey R. G. Computability theory and linear orderings // Handbook of recursive mathematics. - North-Holland, Amsterdam, 1998. - V. 2. - P. 823976.

[22] Downey R. G. On presentations of algebraic structures: to appear in the proceedings of the EC COLORET network, Marcel Dekker.

[23] Downey R. G., Jockusch C. G. Every low Boolean algebra is isomorphic to a recursive one // Proc. Am. Math. Soc. - 1994. - V. 122, - № 3. - P. 871-888.

[24] Downey R. G., Moses M. Recursive linear orderings with incomplete successivities // Trans. Amer. Math. Soc. - 1991. - V. 326. - P. 653-668.

[25] Downey R. G., Knight J. F. Orderings with a-th jump degree // Proc. Amer. Math. Soc. - 1992. - V. 14. - P. 545-552.

[26] Downey R. G., Lempp S., Wu G. On the complexity of the successivity relation in computable linear orderings // Journal of Mathematical Logic. - 2010. - V. 10, № 1-2. - P. 83-99.

[27] Feiner L. J. Orderings and Boolean Algebras not isomorphic to recursive ones: Ph.D. Thesis. - MIT, Cambridge, MA, 1967, 89 p.

[28] Feiner L. J. Hierarchies of Boolean algebras //J. Symb. Logic. - 1970-V. 35, - № 3. - C. 365-374.

[29] Feiner L. J. The strong homogeneity conjecture // J. Symb. Logic. - 1970-V. 35, - № 3. - C. 373-377.

[30] Frolov A. N. Low linear orderings // Journal of Logic and Computation. -2010. - V. 22, - No 4. - P. 745-754.

[31] Frolov A. N. Scattered linear orderings with no computable presentation // Lobachevskii Journal of Mathematics. - 2014. - V. 35, - No 1. - P. 19-22.

[32] Gandy R. O. General recursive of finite type and hierarchies of functions // Ann. Fac. Sci. Univ. Clemmont-Ferrand. - 1967. - V. 35, - No. 4. - P. 5-24.

[33] Harrison J. Recursive pseudo-well orderings // Trans. AMS. - 1968. - V. 131.

- P. 526-543.

[34] Jockusch C. G., Soare R. I. Degrees of orderings not isomorphic to recursive linear orderings // Annales of Pure and Applied Logic. - 1991. - V. 52. -P. 39-61.

[35] Kach A., Montalban A. Cuts of linear orders // Order. - 2011. - V. 28, -No 3. - P. 593-600.

[36] Kaye R. Models of Peano Arithmetic, Volume 15 of Oxford Logic Guides, Oxford University Press, New York, 1991.

[37] Moses M. Recursive Properties of Isomophism Types: Ph.D. Thesis. - Monash Univ., Clayton, Victoria, Australia, 1983.

[38] Moses M. Recursive linear orders with recursive successivities // Ann. Pure Appl. Logic. - 1984. - V. 27. - P. 253-264.

[39] Moses M. n-recursive linear orderings without n + 1 -recursive copies //In Logical methods, (Ed. J. Crossley, J. Remmel, R. A. Shore and M. Sweedler).

- Birkhciuser, 1993. - P. 572-592.

[40] Odifreddi P. Classical recursion theory. - Amsterdam: North-Holland. - 1989.

- 610 p.

[41] Knight J. F., Stob M. Computable Boolean algebras 11 J. Symb. Logic. -2000. - V. 65, - No 4. - P. 1605-1623.

[42] Rice H. Recursive and recursively enumerable orders // Trans. Amer. Math. Soc. - 1956. - V. 83. - P. 277-300.

[43] Raw M. J. S. Complexity of automorphisms of recursive linear orders: Ph.D. Thesis. University of Wisconsin-Madison, 1995.

[44] Remmel J. В. Recursively categorical linear orderings // Proc. Amer. Math. Soc. - 1981. - V. 83. - P. 387-391.

[45] Rosenstein J. Linear orderings. - New York: Academic Press, 1982. - 487 p.

[46] Thurber J. J. Every I0W2 Boolean algebra has a recursive copy // Proc. Am. Math. Soc. - 1995. - V. 123, - No. 12. - P. 3859-3866.

[47] Turner W. P. Computable linear orders and Turing reductions: Master's Thesis. - University of Connecticut, 2012.

[48] Watnick R. A generalization of Tennenbaum's Theorem on effectively finite recursive linear orderings // Journal of Symbolic Logic. - 1984. - V.49. -P. 563-569.

Публикации автора по теме диссертации

[49] Бикмухаметов Р. И. Алгоритмическая независимость естественных отношений на вычислимых линейных порядках // Учён. зап. Казан, гос. унта. Сер. Физ.-матем. науки. - 2013. - Т. 155, - № 3. - С. 80-90.

[50] Бикмухаметов Р. И. О Е!>-начальных сегментах вычислимых линейных порядков 11 Алгебра и логика - 2014. - Т. 53, - № 3. - С. 413-415.

[51] Bikmukhametov R. I. Codings on Linear Orders and Algorithmic Independence of Natural Relations // Lobachevskii Journal of Mathematics. - 2014. -T. 35, - № 4. - C. 326-331.

[52] Бикмухаметов P. И. Начальные сегменты вычислимых линейных порядков с вычислимыми естественными отношениями // Известия высших учебных заведений. Математика, принято в печать.

Тезисы конференций

[53] Бикмухаметов Р. И. О Т^-началъных сегментах вычислимых линейных порядков // Тр. Матем. центра им. Н. И. Лобачевского. - Казань: Изд-во Казан, матем. об-ва. - 2013. - Т. 47. - С. 22-23.

[54] Бикмухаметов Р. И. О Т^-начальных сегментах вычислимых линейных порядков // Электронный сборник тезисов докладов международной конференции «Мальцевские Чтения». - Новосибирск: Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук. -2013. - С. 66-67.

[55] Бикмухаметов Р.И. Вычислимые линейные порядки и естественные отношения на них // Тр. Матем. центра, им. Н. И. Лобачевского. - Казань: Изд-во К азан, матем. об-ва. - 2014. - Т. 50. - С. 27-29.

[56] Bikmukhametov R. I. On Е®-initial segments of computable linear orders // Abstract Booklet of Logic Colloquium and Logic, Algebra and Truth Degrees. - Vienna, Austria. - 2014. - P. 37-38.

[57] Бикмухаметов P. И. О ачальных сегментах вычислимых линейных порядков // Материалы международной конференции «Алгебра и математическая логика: теория и приложения». - Казань: КФУ. - 2014. -С. 44-45.

[58] Бикмухаметов Р.И. Вычислимые линейные порядки и естественные отношения на них // Электронный сборник тезисов докладов международной конференции «Мальцевские Чтения». - Новосибирск: Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук - 2014. - С. 39-40.

Подписано в печать 29.01.2015. Бумага офсетная. Печать цифровая. Формат 60x84 1/16. Гарнитура «Times New Roman». Усл. печ. л. 1,40. Уч.-изд. л. 0,12. Тираж 100 экз. Заказ 103/1

Отпечатано с готового оригинал-макета в типографии Издательства Казанского университета

420008, г. Казань, ул. Профессора Нужина, 1/37 тел. (843) 233-73-59,233-73-28