URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Арсланов М.М. Рекурсивно перечислимые множества и степени неразрешимости
Id: 104571
 
999 руб.

Рекурсивно перечислимые множества и степени неразрешимости

1986. 208 с. Мягкая обложка. Букинист. Состояние: 4+. Есть погашенная библиотечная печать.

 Аннотация

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

Книга рассчитана на специалистов, работающих в области математической логики.


 ОГЛАВЛЕНИЕ

Предисловие.............................3

Введение.............................. 5

Глава 1. ОСНОВНЫЕ ПОНЯТИЯ.................. 9

§ 1.1. Рекурсивные функции.. Тезис Черча.......... 9

§ 1.2. Рекурсивные и рекурсивно перечеслимые множества. Неразрешимые проблемы............ 14

§ 1.3. Вычисления с оракулом. Сводимость по Тьюрингу....... 17

§ 1.4. Арифметическая иерархия................ 24

§ 1.5. Упражнения...................... 26

Глава 2. КРИТЕРИЙ ПОЛНОТЫ РЕКУРСИВНО ПЕРЕЧИСЛИМЫХ МНОЖЕСТВ. ПОЛНЫЕ СТЕПЕНИ............. 28

§ 2.1. Проблема Поста. О методе приоритета......... 28

§ 2.2. Критерий полноты рекурсивно перечислимых множеств. Полные степени................. 32

§ 2.3. Иерархия высоких-низких степеней........... 39

§ 2.4. Упражнения...................... 43

Глава 3. СТРОЕНИЕ ПОЛУРЕШЕТОК D и Dp.n...... 46

§ 3.1. Нерешеточность. Вложение частично-упорядоченных множеств.................... 46

§ 3.2. Вложение решеток................... 52

§ 3.3. Теоремы о ромбе.................... 60

§ 3.4. Метод Сакса сохранения равенства и метод приоритета с бесконечными нарушениями..........65

§ 3.5. Гипотеза Шенфилда. „Вниз-наверх" теоремы...... 77

§ 3.6. Идеалы D и Dp.n..................... 82

§ 3.7. Упражнения...................... 84

Глава 4. КЛАССЫ РЕКУРСИВНО ПЕРЕЧИСЛИМЫХ МНОЖЕСТВ И ИХ СТЕПЕНИ НЕРАЗРЕШИМОСТИ.......... 87

§ 4.1. Простые множества................... 87

§ 4.2. Гиперпростые множества.................. 93

§ 4.3. Гипергиперпростые и максимальные множества..... 102

§ 4.4. Теоретико-решеточные свойства Ш и 9т*........ 113

§ 4.5. т)-гипергиперпростые множества............ 121

§ 4.6. Упражнения...................... 130

Глава 5. НАЧАЛЬНЫЕ СЕГМЕНТЫ СТЕПЕНЕЙ. НЕРАЗРЕШИМОСТЬ Ф......................... 136

§ 5.1. Деревья. Функции без неподвижных точек....... 136

§ 5.2. Минимальные степени................. 142

§ 5.3. Начальные сегменты степеней............. 147

§ 5.4. Неразрешимость 35................... 157

§ 5.5. Упражнения...................... 159

Глава 6. СЕМЕЙСТВА РЕКУРСИВНО ПЕРЕЧИСЛИМЫХ МНОЖЕСТВ И СТЕПЕНЕЙ................... 161

§ 6.1. Семейства рекурсивно перечислимых множеств и их индексные множества.......... 161

§ 6.2. Семейства рекурсивно перечислимых степеней.... 173

§ 6.3. Упражнения...................... 178

Глава 7. ИЕРАРХИИ МНОЖЕСТВ И СТЕПЕНЕЙ, СВОДЯЩИХСЯ К 0......................... 181

§ 7.1. Рекурсивная аппроксимация функций и множеств, сводящихся к 0.................... 181

§ 7.2. Структурные свойства степеней Dn, п>1........ 185

§ 7.3. Слабо рекурсивно перечислимые степени........ 188

§ 7.4. Упражнения...................... 196

Литература.............................198

 
© URSS 2016.

Информация о Продавце