Вычислимое и невычислимое

Книга посвящена доказательству существования невычислимых функций и алгоритмически неразрешенных задач. Обсуждаются проблемы оценки сложности вычислений и алгоритмов. Книга будет полезна широкому кругу специалистов, занимающихся проблемами машинного перевода, искусственного интеллекта, общего использования ЭВМ. Использование электронно-вычислительной техники связано с возможностью алгоритмического решения задач и эффективного вычисления функций. Между тем в математике широко используются функции, заданные неэффективными определениями. Столь же часты доказательства разрешимости задач, например оптимизации, не сопровождаемые алгоритмами их решения. В действительности класс задач, доступных классическим средствам, в некотором трудно уточняемом смысле строго шире класса задач, решаемых алгоритмически. Книга посвящена прояснению смысла этого утверждения, изложению математических моделей вычислимости, а также некоторых недавних результатов, которые используют понятия теории вычислимости, но выходят за ее пределы. Сюда относятся прежде всего идеи А. Н. Колмогорова о связях понятий вычислимости и случайности, а также результаты о теоретико-числовых аспектах теории вычислений. Более подробно математическая проблематика книги обсуждена во введении. Оглавление Предисловие Введение Глава I. Рекурсивные функции и алгоритмы 1. Интуитивная вычислимость 2. Частично рекурсивные функции 3. Образцы рекурсивности ш 4. Перечислимые и разрешимые множества 5. Элементы рекурсивной геометрии 6. Конструктивные объекты и алгоритмы Глава II. Диофантовы множества и алгоритмическая неразрешимость 1. Основные результаты 2. План доказательства 3. Перечислимые множества являются D-множествами 4. Редукция 5. Конструкция специального днофантова множества 6. График экспоненты диофантов 7. Графики факториала и биномиальных коэффициентов диофантовы 8. Дополнения Глава III. Сложность и случайность 1. Версальные семейства 2. Сложность по Колмогорову 3. Сложность и случайность Глава IV. Формальные языки и вычислимость 1. Арифметика синтаксиса 2. Синтаксический анализ 3. Перечислимость выводимых формул Глава V. Теорема Геделя 1. Принцип неполноты 2. Неперечислимость истинных формул 3. О длине доказательств 4. Арифметическая иерархия 5. Продуктивность арифметической истины 6. Вычислимые функции с очень быстрым ростом Глава VI. Рекурсивные группы 1. Основной результат и его следствия 2. Свободные произведения н НNN-расширения 3. Вложения в группы с двумя образующими 4. Хорошие подгруппы 5. Ограниченные системы образующих 6. Окончание доказательства Список литературы Именной указатель Предметный указатель