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


 
Вернуться в: Каталог  
Обложка Роджерс Х. __Теория рекурсивных функций и эффективная вычислимость: Пер. с англ.
Id: 222024
 
1999 руб.

__Теория рекурсивных функций и эффективная вычислимость: Пер. с англ.

1972. 622 с. Твердый переплет. Букинист. Состояние: 3. Блок текста: 4. Обложка: 3. Состояние близко к хор., корешок склеен скотчом и бумагой. Небольшие пятна на обл. Погашенная библиотечная печать.

 Аннотация

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

Не предполагающая в основной своей части никаких предварительных знаний, кроме знакомства с теоретико-множественной терминологией, книга Роджерса написана хорошим, ясным языком; при этом формальному изложению предпосылаются содержательные рассуждения, разъясняющие природу вводимых понятий или идей построений и доказательств; в ней содержится очень много упражнений.

Книга рассчитана на читателей, интересующихся современными проблемами математической логики и теории алгоритмов. Она доступна аспирантам и студентам старших курсов университетов и пединститутов.


 ОГЛАВЛЕНИЕ

От редактора перевода...................... 5

Из предисловия автора...................... 7

Введение............................ 11

Глава 1. РЕКУРСИВНЫЕ ФУНКЦИИ............. 17

§ 1.1. Неформальное понятие алгоритма.......... 17

§ 1.2. Пример: примитивнорекурсивные функции 22

§.1.3. Экстенсиональность................. 25

§ 1.4. Диагонализация.................. 27

§ 1.5. Формализация................... 28

§ 1.6. Основной результат....... 36

§ 1.7. Тезис Чёрча.................... 38

§ 1.8. Гёделевы номера, универсальность, s-m-ra-теорема... 39

§ 1.9. Проблема остановки................ 43

§ 1.10. Рекурсивность................... 46

Глава 2. НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ............ 53

§ 2.1. Новые примеры неразрешимых проблем....... 53

§ 2.2. Неразрешимые проблемы в других областях математики 56

§ 2.3. Существование некоторых частично рекурсивных функций........................ 58

§ 2.4. Исторические замечания.............. 60

§ 2.5. Обсуждение.................... 61

§ 2.6. Упражнения.................... 62

Глава 3. ЦЕЛИ КНИГИ И ЕЕ СОДЕРЖАНИЕ.......... 68

§ 3.1. Задачи теории................... 68

§ 3.2.. Направленность этой книги............ 70

§ 3.3. Обзор содержания................. 71

Глава 4. РЕКУРСИВНАЯ ИНВАРИАНТНОСТЬ......... 73

§ 4.1. Инвариантность относительно группы........ 73

§ 4.2. Рекурсивные перестановки............. 74

§ 4.3. Рекурсивная инвариантность............ 75

§ 4.4. Сходство...................... 77

§ 4.5. Универсальные функции.............. 77

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

Глава 5. РЕКУРСИВНЫЕ И РЕКУРСИВНО ПЕРЕЧИСЛИМЫЕ

МНОЖЕСТВА..................... 81

§ 5.1. Определения.................... 81

§ 5.2. Основная теорема.................. 84

§ 5.3. Рекурсивные и рекурсивно перечислимые отношения; кодирование ге-ок.......... 89

§ 5.4. Теоремы о проекции................ 92

§ 5.5. Равномерность................... 95

§ 5.6. Конечные множества................ 96

§ 5.7. Теорема об однозначности.............. 99

§ 5.8. Упражнения................. 101

Глава 6. СВОДИМОСТИ..................... 106

§ 6.1. Общее введение.................... 106

§ 6.2. Упражнения.................... 109

Глава 7. ОДНО-ОДНОСВОДИМОСТЬ; МНОГО-ОДНОСВОДИ-

МОСТЬ; ТВОРЧЕСКИЕ МНОЖЕСТВА........ 110

§ 7.1. Одно-односводимость и много-односводнмость.... 110

§ 7.2. Полные множества................. 113

§ 7.3. Творческие (креативные) множества......... 114

§ 7.4. Одно-одноэквивалентность и рекурсивный изоморфизм 116

§ 7.5. Одно-однополнота и много-однополнота........ 118

§ 7.6. Цилиндры..................... 121

§ 7.7. Продуктивность.................. 122

§ 7.8. Логика...................... 127

§ 7.9. Упражнения.................... 133

Глава 8. ТАБЛИЧНЫЕ СВОДИМОСТИ; ПРОСТЫЕ МНОЖЕСТВА 140

§ 8.1. Простые множества.................. 140

§ 8.2. Иммунные множества................ 142

§ 8.3. Табличная сводимость................ 145

§ 8.4. Табличная сводимость и много-односводимость.... 148

§ 8.5. Ограниченнотабличная сводимость.......... 150

§ 8.6. Структура степеней................ 155

§ 8.7. Другие рекурсивно перечислимые множества..... 158

§ 8.8. Упражнения.................... 160

Глава 9. СВОДИМОСТЬ ПО ТЬЮРИНГУ; ГИПЕРПРОСТЫЕ

МНОЖЕСТВА.................... 167

§ 9.1. Пример...................... 167

§ 9.2. Относительная рекурсивность............ 168

§ 9.3. Релятивизованная теория.............. 176

§ 9.4. Сводимость по Тьюрингу.............. 179

§ 9.5. Гиперпростые множества; теорема Деккера..... 181

§ 9.6. Сводимость по Тьюрингу и табличная сводимость;

проблема Поста......:............ 184

§ 9.7. Сводимость по перечислимости............ 189

§ 9.8. Рекурсивнв1е операторы............... 193

§ 9.9. Упражнения.................... 202

Глава 10. ПРОБЛЕМА ПОСТА; НЕПОЛНЫЕ МНОЖЕСТВА... 209

§ 10.1. Конструктивные подходы.............. 209

§ 10.2. Фридбергово решение................. 212

§ 10.3. Дальнейшие результаты и проблемы........ 217

§ 10.4. Неотделимые множества произвольной рекурсивно перечислимой степени.....220

§ 10.5. Теории произвольной рекурсивно перечислимой степени 222

§ 10.6. Упражнения.................... 226

Глава 11. ТЕОРЕМА О РЕКУРСИИ............... 232

§ 11.1 Введение...................... 232

§ 11.2. Теорема о рекурсии................ 233

§ 11.3. Полнота творческих множеств; вполне продуктивные

множества..................... 236

§ 11.4. Другие применения и конструкции......... 239

§ 11.5. Другие формы теоремы о рекурсии...... 249

§ 11.6. Обсуждение..................... 256

§ 11.7. Системы обозначений для ординалов......... 263

§ 11.8. Конструктивные ординалы............. 271

§ 11.9. Упражнения.................... 274

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

12.1. Решетки множеств.........

12.2. Разложение............

12.3. Сжатые множества.........

12.4. Максимальные множества......

12.5. Подмножества максимальных множеств

12.6. Свойства почти-конечности.....

12.7.. Упражнения.............

Глава 13. СТЕПЕНИ НЕРАЗРЕШИМОСТИ...........

§ 13.1. Операция скачка..................

§ 13.2. Некоторые важные множества и степени.......

§ 13.3. Полные степени; категории и мера.........

§ 13.4. Упорядочение степеней...............

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

§ 13.6. Частичные степени.................

§ 13.7. Решетка Медведева.................

§ 13.8. Дальнейшие результаты...............

§ 13.9. Упражнения....................

Глава 14. АРИФМЕТИЧЕСКАЯ ИЕРАРХИЯ (ЧАСТЬ 1).....

§ 14.1. Иерархия множеств.................

§ 14.2. Нормальные формы...........•.....

§ 14.3. Алгоритм Тарского --- Куратовского.........

§ 14.4. Арифметическая представимость...........

§ 14.5. Сильная теорема об иерархии............

§ 14.6. Степени.......................

§ 14.7. Приложения в логике...............

§ 14.8. Вычислимые степени неразрешимости........

§ 14.9. Упражнения....................

Глава 15. АРИФМЕТИЧЕСКАЯ ИЕРАРХИЯ (ЧАСТЬ 2).....

§ 15.1. Иерархия классов множеств.............

- § 15.2. Иерархия классов функций.............

§ 15.3. Функционалы...................

§ 15.4. Упражнения....................

Глава 16. АНАЛИТИЧЕСКАЯ ИЕРАРХИЯ...........

§ 16.1. Аналитическая иерархия..............

§ 16.2. Аналитическое представление; приложения, к логике

§ 16.3. Деревья с конечными путями............

§ 16.4. П^-множества и AJ-множества...........

§ 16.5. Обобщенная вычислимость..............

§ 16.6, Гиперстепени и гиперскачок; 2|-множества и Д|-мно-

жества.......................

§ 16.7. Результаты о базисе и неявная определимость....

§ 16.8. Гиперарифметическая иерархия...........

§ 16.9. Упражнения..................

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

Указатель обозначений...............

Указатель теорем....................

Алфавитный указатель................

 
© URSS 2016.

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