Кибернетика. Вычислимое и невычислимое
Автор(ы): | Манин Ю. И.
19.01.2012
|
Год изд.: | 1980 |
Описание: | Использование электронно-вычислительной техники связано с возможностью алгоритмического решения задач и эффективного вычисления функций. Между тем в математике широко используются функции, заданные неэффективными определениями. Столь же часты доказательства разрешимости задач, например оптимизации, не сопровождаемые алгоритмами их решения. В действительности класс задач, доступных классическим средствам, в некотором трудно уточняемом смысле строго шире класса задач, решаемых алгоритмически. Книга посвящена прояснению смысла этого утверждения, изложению математических моделей вычислимости, а также некоторых недавних результатов, которые используют понятия теории вычислимости, но выходят за ее пределы. В ней обсуждаются проблемы оценки сложности вычислений и алгоритмов. Книга будет полезна широкому кругу специалистов, занимающихся проблемами машинного перевода, искусственного интеллекта, общего использования ЭВМ. |
Оглавление: |
Обложка книги.
Предисловие [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] |
Формат: | djvu |
Размер: | 2859147 байт |
Язык: | РУС |
Рейтинг: | 191 |
Открыть: | Ссылка (RU) |