| Предисловие | 6 |
| Обозначения и терминология | 11 |
| Введение | 13 |
| |
| Ч а с т ь I. Основные открытия общей теории алгоритмов | 15 |
| |
| § 1.0. Предварительные понятия теории алгоритмов: конструктивные |
 объекты и их ансамбли, локальные свойства и локальные действия | 17 |
| 1.0.1. Первые примеры конструктивных объектов: слова и деревья |
| (18). 1.0.2. Конструктивные объекты: попытка общего описания |
| (19). 1.0.3. Локальные свойства и локальные действия: |
| неформальное изложение (21). 1.0.4. Колмогоровские комплексы |
| (22). 1.0.5. (Б, k)-комплексы (24). 1.0.6. Ансамбли (25). 1.0.7. |
| Локальные свойства и локальные действия: формальное определение |
| (27). |
| § 1.1. Общее понятие алгоритма как самостоятельное (отдельное) |
| понятие | 29 |
| 1.1.1. X—Y-алгоритмы (34). |
| § 1.2. Представительные вычислительные модели | 34 |
| 1.2.1. Машины Колмогорова (35). 1.2.2. Формальные задания (37). |
| 1.2.3. Представительные модели (39). 1.2.4. Тезис Чёрча (41). |
| 1.2.5. Языки программирования (41). |
| Добавление к § 1.2. Машины Шёнхаге | 42 |
| § 1.3. Общее понятие исчисления как самостоятельное (отдельное) |
| понятие | 44 |
| 1.3.1. Исчисления со входом (52). |
| Добавление к § 1.3. Алгебраические примеры | 53 |
| § 1.4. Представительные порождающие модели | 62 |
| § 1.5. Выяснение связей между алгоритмами и исчислениями | 63 |
| § 1.6. Время и ёмкость как сложности вычисления и порождения | 65 |
| 1.6.1. Машины Тьюринга (66). 1.6.2. Время (69). 1.6.3. Ёмкость |
| (71). 1.6.4. Норма (74). 1.6.Б. Примеры нормированных ансамблей |
| (75). 1.6.6. Ограниченно-искажающие отображения и изоморфизмы |
| (75). 1.6.7. Дополнительные требовании к нормам (75). 1.6.8. |
| Сложности порождения (76). 1.6.9. Эффективные алгоритмы (76). |
| Добавление к § 1.6. Моделирование в реальное время | 77 |
| § 1.7. Вычислимые функции и породимые множества; перечислимые |
| множества; разрешимые множества | 78 |
| § 1.8. Понятие μ-рекурсивной функции | 87 |
| § 1.9. Возможность арифметического и даже диофантова представления |
| любого перечислимого числового множества | 89 |
| § 1.10. Построение неразрешимого породимого множества | 91 |
| § 1.11. Проблема сводимости Поста | 93 |
| § 1.12. Понятие относительного алгоритма, или алгоритма с оракулом | 98 |
| § 1.13. Понятие вычислимой операции | 101 |
| § 1.14. Понятие программы: программы как объекты вычисления |
| и порождения | 106 |
| 1.14.1. Способы программирования (106). 1.14.2. Универсальные |
| алгоритмы и универсальные функции (110). 1.14.3. Главные, или |
| гёделевы, универсальны: функции (112). 1.14.4. Вычислительные |
| структуры (114). 1.14.5. Экономные по норме, или оптимальные |
| функции (117). 1.14.6. Программирование исчислений (119). |
| 1.14.7. Преобразования программ (120). |
| § 1.15. Понятие нумерации и теория нумераций | 122 |
| 1.15.1. Вычислимые нумерации (126). 1.15.2. Нумерованные |
| множества (132). 1.15.3. Операции над нумерованными |
| множествами (133). |
| § 1.16. Начало создания инвариантной, или машинно-независимой, |
| теории сложности вычисления | 133 |
| § 1.17. Теория сложности и энтропии конструктивных объектов | 135 |
| § 1.18. Удобные вычислительные модели.141 |
| |
| Ч а с т ь II. Основные математические приложения теории |
| алгоритмов | 144 |
| |
| § 2.1. Исследование массовых проблем | 146 |
| 2.1.0. Основные понятия (146). 2.1.1. Семь нерешимых проблем |
| (151). 2.1.2. Массовые проблемы в математике (154). 2.1.3. |
| Массовые проблемы в смысле Медведева (163). 2.1.4. О пользе |
| правильной терминологии (165). |
| § 2.2. Приложения к основаниям математики: конструктивная семантика | 165 |
| § 2.3. Приложения к математической логике: анализ формализованных |
| языков логики н арифметики | 169 |
| § 2.4. Вычислимый анализ | 173 |
| 2.4.0. Ранняя история: Борель и Тьюринг (173). 2.4.1. |
| Конструктивный анализ (175). 2.4.2. Начальные понятия (176). |
| 2.4.3. Главные результаты (178). 2.4.4. Эффективно метрические |
| пространства (179). 2.4.5. Эффективно топологические |
| пространства (180). 2.4.6. Отчасти вычислимый анализ (181). |
| 2.4.7. Эффективно пренебрежимые множества (182). |
| § 2.5. Нумерованные структуры | 184 |
| 2.5.1. Нумерации программного типа (185). 2.5.2. Квазистандартные |
| нумерации (186). 2.5.3. Конструктивизации (186). 2.5.4. |
| Расширения конструктивных структур (188). 2.5.5. Алгебраически |
| корректные массовые проблемы (189). 2.5.6. Алгоритмические |
| размеры (190). 2.5.7. Конструктивные и конструктивизируемые |
| модели (195). 2.5.8. Модели арифметики (197). |
| § 2.6. Приложения к теории вероятностей! определения случайной |
| последовательности | 198 |
| 2.6.1. Частотный подход (200). 2.6.2. Каким должен быть класс |
| всех допустимых правил выбора? (206). 2.6.3. Сложностный подход |
| (208), 2.6.4. Количественный, или теоретико-мерный, подход (209). |
| 2.6.5. Соотношения между различными определениями (210). 2.6.6. |
| Конечные последовательности о точки зрения случайности (212). |
| § 2.7. Приложения к теории информации: алгоритмический подход |
| к понятию количества информации | 215 |
| § 2.8. Оценки сложности решения отдельных задач | 220 |
| 2.8.1. Верхние оценки (220). 2.8.2. Нижние оценки (223). |
| § 2.9. Влияние теории алгоритмов на алгоритмическую практику | 224 |
| 2.9.1. Общее понятие алгоритма и возможность его формализации |
| (225). 2.9.2. Существование нерешимых алгоритмических проблем |
| в математике и нерешаемость многих естественно возникающих |
| проблем (225). 2.9.3. Появление различных понятий сложности |
| вычисления и порождения (225). 2.9.4. Неалгоритмическое описание |
| вычислимых функций (226). 2.9.5. Вычислительные и порождающие |
| модели (226). 2.9.6. Трактовка программ как объектов вычисления |
| (227). 2.9.7. Рассмотрение программ как объектов порождения |
| (227). 2.9.8. Смешанные вычисления (227). 2.9.9. Методы |
| программирования (229). 2.9.10. Программирование как вторая |
| грамотность (229). 2.9.11. Математическая логика и вычислительная |
| техника (230). |
| |
| Д о п о л н е н и е. О вероятностных алгоритмах (как использование |
| случайности позволяет укорачивать вычисления) | 231 |
| |
| § Д.1. Предварительные замечания | 231 |
| § Д.2. Основные результаты | 235 |
| § Д.З. Формальные определения | 238 |
| |
| Список сокращений | 244 |
| Список литературы | 245 |
| Именной указатель | 272 |
| Предметный указатель | 276 |
