Вычислимое и невычислимое, Манин Ю.И., 1980

Вычислимое и невычислимое, Манин Ю.И., 1980.

   Книга посвящена доказательству существования невычислимых функций и алгоритмически неразрешенных задач. Обсуждаются проблемы оценки сложности вычислений и алгоритмов. Книга будет полезна широкому кругу специалистов, занимающихся проблемами машинного перевода, искусственного интеллекта, общего использования ЭВМ.

   Использование электронно-вычислительной техники связано с возможностью алгоритмического решения задач и эффективного вычисления функций. Между тем в математике широко используются функции, заданные неэффективными определениями. Столь же часты доказательства разрешимости задач, например оптимизации, не сопровождаемые алгоритмами их решения.
В действительности класс задач, доступных классическим средствам, в некотором трудно уточняемом смысле строго шире класса задач, решаемых алгоритмически. Книга посвящена прояснению смысла этого утверждения, изложению математических моделей вычислимости, а также некоторых недавних результатов, которые используют понятия теории вычислимости, но выходят за ее пределы. Сюда относятся прежде всего идеи А. Н. Колмогорова о связях понятий вычислимости и случайности, а также результаты о теоретико-числовых аспектах теории вычислений. Более подробно математическая проблематика книги обсуждена   во введении.

Оглавление
Предисловие
Введение
Глава 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. Окончание доказательства
Список литературы
Именной указатель
Предметный указатель



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Вычислимое и невычислимое, Манин Ю.И., 1980 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать djvu
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать книгу Вычислимое и невычислимое, Манин Ю.И., 1980 - Яндекс Народ Диск.

Скачать книгу Вычислимое и невычислимое, Манин Ю.И., 1980 - depositfiles.




Теги: учебник по математике :: математика :: Манин :: теорема Геделя