Вычислимое и невычислимое, Манин Ю.И., 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. Окончание доказательства
Список литературы
Именной указатель
Предметный указатель
| Рейтинг: | 4.8 баллов / 2537 оценок |
| Формат: | Книга |
| Уже скачали: | 12788 раз |
Похожие Книги
Нам показалось, что Книги ниже Вас заинтересуют не меньше. Эти издания Вы так же можете скачивать и читать совершенно бесплатно на сайте!
-
История Александра Македонского
Книга: История Александра Македонского Автор: Квинт Курций Руф Страниц: 464 Формат: PDF Размер: 7,04 мб Качество: Отличное Язык: Русский Год издания: 1993 Перевод сочинения римского историка Квинта Ку . . .
-
Диагностика нервных болезней
Название: Диагностика нервных болезнейАвтор: Улицкий Л.А., Чухловина М.Л.Издательство: ПитерГод: 2001Страниц: 478Язык: РусскийФормат: pdf / rarРазмер: 52,06 Mb В данном руководстве изложены особенност . . .
-
Становление официальной идеологии принципата императора Августа
Название: Становление официальной идеологии принципата императора Августа Автор: Токарев А.Н. Издательство: ХНУ имени В. Н. Каразина Страниц: 268 Формат: PDF Размер: 14,27 Мб Качество: Отличное Язык: . . .
-
Твой девятнадцатый век
Название: Твой девятнадцатый век Автор: Натан Эйдельман Издательство: АСТ, Астрель Страниц: 416 Формат: RTF Размер: 5,35 МБ Качество: Отличное Язык: Русский Жанр: История Год издания: 2010 ISBN: 978-5 . . .
-
Секреты любви. Даосская практика для женщин и мужчин
Название: Секреты любви. Даосская практика для женщин и мужчинАвтор: Бинг Л.Издательство: ФениксISBN: 978-5-222-11458-2Год издания: 2007Страниц: 320Язык: РусскийФормат: PDFРазмер: 2.55 МбОписание: П . . .
-
Дубоссары 1989-1992 гг. За кулисами политики
Название: Дубоссары 1989-1992 гг. За кулисами политики Автор: Дюкарев В. В. Издательство: Упрполиграфиздат ПМР (Тирасполь) Страниц: 421 Формат: DJVU Размер: 17,98 Мб Качество: Отличное Язык: Русский Г . . .
-
Древний Рим: проблемы экономического развития
Автор: Штаерман Е.Название: Древний Рим: проблемы экономического развитияИздательство: НаукаГод: 1978Формат: djvuРазмер: 4.08 MbШтаерман Е. Древний Рим: проблемы экономического развития. – М.: Наука, . . .
-
Зачистка в Политбюро. Как Горбачев убирал «врагов перестройки»
Название: Зачистка в Политбюро. Как Горбачев убирал «врагов перестройки» Автор: Соломенцев М. С. Издательство: Эксмо, Алгоритм Страниц: 224 Формат: DJVU Размер: 7,57 Мб Качество: Отличное . . .
-
Я на кухне № 1-12 2008
Автор:Коллектив Название: Я на кухне № 1-12 2008Издательство: Ajakirjade kirjastus ЭстонияГод: 2008Формат: PDFРазмер: 61МВСтраниц:192Язык: РусскийКулинарное приложение к журналу "Яна" (Архив за 2008 . . .
-
Всемирная история. Том 6. Римский период
Название: Всемирная история. Том 6. Римский периодАвтор: Бадак А.Н., Войнич И.Е., Волчек Н.М. и др.Издательство: ЛитератураГод: 1998Страниц: 512ISBN: 985-6274-52-4Формат: DjVuЯзык: РусскийРазмер: 10, . . .
Вы не зарегистрированы!
Если вы хотите скачивать книги, журналы и аудиокниги бесплатно, без рекламы и без смс, оставлять комментарии и отзывы, учавствовать в различных интересных мероприятиях, получать скидки в книжных магазинах и многое другое, то Вам необходимо зарегистрироваться в нашей Электронной Библиотеке.
Отзывы читателей
Ой!
К сожалению, в нашей Бесплатной Библиотеке пока нет отзывов о Книге Вычислимое и невычислимое, Манин Ю.И., 1980. Помогите нам и другим читателям окунуться в сюжет Книги и узнать Ваше мнение. Оставьте свой отзыв или обзор сейчас, это займет у Вас всего-лишь несколько минут.