Вычислимое и невычислимое, Манин Ю.И., 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 оценок |
| Формат: | Книга |
| Уже скачали: | 12790 раз |
Похожие Книги
Нам показалось, что Книги ниже Вас заинтересуют не меньше. Эти издания Вы так же можете скачивать и читать совершенно бесплатно на сайте!
-
Flight International 2009-12-01 (Vol 176 No 5217) pdf 38,2Мб
Издательство: Reed Business InformationЯзык: EnglishГод издания: 2009 - 12Количество страниц: 52Формат: pdfРазмер: 38,2 mbFlight International (or Flight) is a global aerospace weekly publication. Fou . . .
-
Маленькая Diana спецвыпуск № 11 2008 jpg 3,61Мб
Название: Маленькая Diana - спец. выпуск №11 2008Автор: коллективФормат: JPGРазмер: 3,61 MbВязаные туники и платья.Они сейчас на пике моды. 13 великолепных моделей.Скачать с DepositСкачать с Letitbit . . .
-
В Контакте - Взлом аккаунтов (2010) DVDRip avi 360Мб
Видеоурок В Контакте - Взлом аккаунтов расскажет зачем нужны куки (cookies), и как с помошью них взломать популярный В Контакте. Так же для примера, что это действительно работает показан взлом "Однок . . .
-
Орасфера. Доступно о стоматологии iso 699,53Мб
Автор: Orasphere NZ LtdИздательство: Orasphere NZ LtdГод издания: 2007Язык: русскийФормат: isoРазмер: 699.53 МбОрасфера - одна из самых популярных западных мультимедийных программ для мотивации и обуч . . .
-
Видеоуроки по работе с онлайн платежными системами (2011) SWF swf 18,11Мб
Пять видеоуроков обучающих работе с платежными системами: Rupay, Webmoney, Яндекс Деньги, E-Gold, Roboxchange. В них рассказываются как зарегестрироваться в системах, как пользоваться и основные возмо . . .
-
"Сказки о зверятах"-читаем по слогам djvu 0,8Мб
Название: "Сказки о зверятах"-читаем по слогамАвтор: Л.ЯхнинГод издания:2006Страниц: 11Формат: djvuРазмер: 0,8 MbОбучение чтению.Первая ступень-читаем по слогам.depozitfilesletitbit . . .
-
Простые раскраски - Растения djvu 2,7Мб
Название: Простые раскраски - РастенияИздательство: РосмэнISBN: 5-353-0144-9Год: 2004Страниц: 12Формат: DjVuРазмер: 2,7 МбПростые раскраски "Растения" предназначены для детей 2-4 лет.Занятия по книжке . . .
-
Юный Техник №8 2006 год pdf 13,51Мб
Название: Юный ТехникГод: 2006Страниц: 83Формат: pdfРазмер файла: 13.51 МбЯзык: русскийdepositfiles.comopenfile.ru . . .
-
Revi 44 pdf 47,82Мб
Название: Revi 44Издательство: REVI PublicationsГод издания: 2002Язык: чешскийКоличество страниц: 61Формат: PDFРазмер: 47.82 МбЧешский журнал, посвященный авиации rapidshare.com ifolder.ru uploading. . . .
-
Карлссон, который живет на крыше, возвращается тайком djvu 4,4Мб
Автор:Астрид ЛиндгренНазвание: Карлссон, который живет на крыше, возвращается тайкомИздательство: Мир ребёнкаГод: 1998Формат: DjVuРазмер: 4,4 Мбdepositfiles.comЗеркалоletitbit.net . . .
Вы не зарегистрированы!
Если вы хотите скачивать книги, журналы и аудиокниги бесплатно, без рекламы и без смс, оставлять комментарии и отзывы, учавствовать в различных интересных мероприятиях, получать скидки в книжных магазинах и многое другое, то Вам необходимо зарегистрироваться в нашей Электронной Библиотеке.
Отзывы читателей
Ой!
К сожалению, в нашей Бесплатной Библиотеке пока нет отзывов о Книге Вычислимое и невычислимое, Манин Ю.И., 1980. Помогите нам и другим читателям окунуться в сюжет Книги и узнать Ваше мнение. Оставьте свой отзыв или обзор сейчас, это займет у Вас всего-лишь несколько минут.