ОГЛАВЛЕНИЕ: Предисловие (3). Введение (5). Глава I. Рекурсивные функции и алгоритмы (16). 1. Интуитивная вычислимость (16). 2. Частично рекурсивные функции (20). 3. Образцы рекурсивности (25). 4. Перечислимые и разрешимые множества (29). 5. Элементы рекурсивной геометрии (39). 6. Конструктивные объекты и алгоритмы (44). Глава II. Диофантовы множества и алгоритмическая неразрешимость (46). 1. Основные результаты (46). 2. План доказательства (49). 3. Перечислимые множества являются D-множествами (51). 4. Редукция (53). 5. Конструкция специального диофантова множества (56). 6. График экспоненты диофантов (61). 7. Графики факториала и биномиальных коэффициентов диофанговы (62). 8. Дополнения (64). Глава III. Сложность и случайность (65). 1. Версальные семейства (65). 2. Сложность по Колмогорову (68). 3. Сложность и случайность (73). Глава IV. Формальные языки и вычислимость (74). 1. Арифметика синтаксиса (74). 2. Синтаксический анализ (80). 3. Перечислимость выводимых формул (85). Глава V. Теорема Геделя (87). 1. Принцип неполноты (87). 2. Неперечислимость истинных формул (88). 3. О длине доказательств (91). 4. Арифметическая иерархия (93). 5. Продуктивность арифметической истины (96). 6. Вычислимые функции с очень быстрым ростом (99). Глава VI. Рекурсивные группы (101). 1. Основной результат и его следствия (101). 2. Свободные произведения и HNN-расширения (104). 3. Вложения в группы с двумя образующими (107). 4. Хорошие подгруппы (108). 5 Ограниченные системы образующих (111). 6. Окончание доказательства (116). Список литературы (123). Именной указатель (125). Предметный указатель (125). Аннотация издательства: Книга посвящена доказательству существования невычислимых функций и алгоритмически неразрешимых задач. Обсуждаются проблемы оценки сложности вычислений и алгоритмов. Книга будет полезна широкому кругу специалистов, занимающихся проблемами машинного перевода, искусственного интеллекта, общего использования ЭВМ.
