Вычислимое и невычислимое, Манин Ю.И., 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 оценок |
| Формат: | Книга |
| Уже скачали: | 12780 раз |
Похожие Книги
Нам показалось, что Книги ниже Вас заинтересуют не меньше. Эти издания Вы так же можете скачивать и читать совершенно бесплатно на сайте!
-
Ницше
Название: НицшеАвтор: Гранье Ж.Серия: Cogito, ergo sum: "Университетская библиотека"Издательство: М.: АСТ, АстрельISBN: 5-271-10609-8Жанр: Монография, философияГод: 2005Страниц: 158Формат: DjVuРазмер: . . .
-
The Complete Idiot's Guide to WordPress
Автор: Susan GuneliusНазвание: The Complete Idiot's Guide to WordPress Издательство: AlphaГод: 2011Формат: pdfРазмер: 20MbЯзык: АнглийскийWith more than 22 million users worldwide, WordPress is the №1 . . .
-
Learning FuelPHP for Effective PHP Development
Год: 2013Автор: Ross TweedieИздательство: Packt PublishingISBN: 978-1-78216-037-3Язык: АнглийскийФормат: PDFКачество: Изначально компьютерное (eBook)Интерактивное оглавление: ДаКоличество страниц: 104 . . .
-
Коллекция. Увлекательное собирание чего-то приятного...
Автор: Стукалова З.Е. Название: Коллекция. Увлекательное собирание чего-то приятного... Издательство: Москва : Higher school consultingГод: 2013Страниц: 101Формат: pdfРазмер: 16 mbСогласно словарям . . .
-
M.T.H. Electric Trains 1993-2002 (Greenberg's Guides)
Автор: Kent J. JohnsonНазвание: M.T.H. Electric Trains 1993-2002 (Greenberg's Guides)Издательство: Kalmbach BooksГод: 2002Формат: PDF Страниц: 116Язык: EnglishРазмер: 12.3 MBThis handy, portable pocke . . .
-
KnockoutJS Blueprints
Год: 2015Автор: Carlo RussoИздательство: Packt PublishingISBN: 978-1-78398-085-7Язык: АнглийскийФормат: PDFКачество: Изначально компьютерное (eBook) (Converted)Интерактивное оглавление: ДаКоличество с . . .
-
Правила игры в хоккей. Сезон 2014/2015
Автор: КоллективНазвание: Правила игры в хоккей. Сезон 2014/2015 Издательство: ИД Флюид ФриФлайГод: 2014Страниц: 176Формат: pdfРазмер: 2 mbВ книге представлены правила игры в хоккей, по которым прово . . .
-
Buyer's Guide to Toy Train Locomotives (Classic Toy Trains Magazine)
Автор: Ray L. PlummerНазвание: Buyer's Guide to Toy Train Locomotives (Classic Toy Trains Magazine)Издательство: Kalmbach BooksГод: 2001Формат: PDF Страниц: 148Язык: EnglishРазмер: 20.5 MBLooking for . . .
-
Между прошлым и будущим
Автор: Юрий Яковлев Название: Между прошлым и будущим Издательство: АСТ, Астрель Год: 2003Страниц: 418Формат: pdfРазмер: 30 mbКнига воспоминаний выдающегося артиста театра и кино Юрия Васильевича Яко . . .
-
Беззвестный русский — известный француз
Автор: Федотова, Е. - ред.Название: Беззвестный русский — известный французИздательство: СПб.: Изд-во БуковскогоГод: 1999Объем: 136 с., ил.Серия: Библиотека всемирного клуба петербуржцевФормат: pdfРаз . . .
Вы не зарегистрированы!
Если вы хотите скачивать книги, журналы и аудиокниги бесплатно, без рекламы и без смс, оставлять комментарии и отзывы, учавствовать в различных интересных мероприятиях, получать скидки в книжных магазинах и многое другое, то Вам необходимо зарегистрироваться в нашей Электронной Библиотеке.
Отзывы читателей
Ой!
К сожалению, в нашей Бесплатной Библиотеке пока нет отзывов о Книге Вычислимое и невычислимое, Манин Ю.И., 1980. Помогите нам и другим читателям окунуться в сюжет Книги и узнать Ваше мнение. Оставьте свой отзыв или обзор сейчас, это займет у Вас всего-лишь несколько минут.