Лекции по математической логике и теории алгоритмов, Часть 3, Вычислимые функции, Верещагин Н.К., Шень А., 2012
Лекции по математической логике и теории алгоритмов, Часть 3, Вычислимые функции, Верещагин Н.К., Шень А., 2012.
Книга написана по материалам лекций и семинаров, проводившихся авторами для студентов младших курсов мехмата МГУ. В ней рассказывается об основных понятиях общей теории вычислимых функций (вычислимость, разрешимость, перечислимость, универсальные функции, нумерации и их свойства, m-полнота, теорема о неподвижной точке, арифметическая иерархия, вычисления с оракулом, степени неразрешимости) и о конкретных вычислительных моделях (машины Тьюринга, рекурсивные функции). Изложение рассчитано на учеников математических школ, студентов-математиков и всех интересующихся основами теории алгоритмов. Книга содержит около 100 задач различной трудности.
Вычислимые функции.
Функция f с натуральными аргументами и значениями называется вычислимой, если существует алгоритм, ее вычисляющий, то есть такой алгоритм A, что
• если f(n) определено для некоторого натурального n, то алгоритм А останавливается на входе п и печатает f(n);
• если f(п) не определено, то алгоритм А не останавливается на входе п.
Несколько замечаний по поводу этого определения:
1. Понятие вычислимости определяется здесь для частичных функций (областью определения которых является некоторое подмножество натурального ряда). Например, нигде не определённая функция вычислима (в качестве А надо взять программу, которая всегда зацикливается).
2. Можно было бы изменить определение, сказав так: «если f(n) не определено, то либо алгоритм А не останавливается, либо останавливается, но ничего не печатает». На самом деле от этого ничего бы не изменилось (вместо того, чтобы останавливаться, ничего не напечатав, алгоритм может зацикливаться).
3. Входами и выходами алгоритмов могут быть не только натуральные числа, но и двоичные строки (слова в алфавите {0,1}), пары натуральных чисел, конечные последовательности слов и вообще любые, как говорят, «конструктивные объекты». Поэтому аналогичным образом можно определить понятие, скажем, вычислимой функции с двумя натуральными аргументами, значениями которой являются рациональные числа.
Оглавление
Предисловие
1. Вычислимость, разрешимость и перечислимость
1.1. Вычислимые функции
1.2. Разрешимые множества
1.3. Перечислимые множества
1.4. Перечислимые и разрешимые множества
1.5. Перечислимость и вычислимость
2. Универсальные функции и неразрешимость
2.1. Универсальные функции
2.2. Диагональная конструкция
2.3. Перечислимое неразрешимое множество
2.4. Перечислимые неотделимые множества
2.5. Простые множества: конструкция Поста
3. Нумерации и операции
3.1. Главные универсальные функции
3.2. Вычислимые последовательности функций
3.3. Главные универсальные множества
4. Свойства главных нумераций
4.1. Множества номеров
4.2. Однозначные нумерации
4.3. Новые номера старых функций
4.4. Изоморфизм главных нумераций
4.5. Перечислимые свойства функций
5. Теорема о неподвижной точке
5.1. Неподвижная точка и отношения эквивалентности
5.2. Программа, печатающая свой текст
5.3. Системный трюк: ещё одно доказательство
5.4. Несколько замечаний
6. m-сводимость и свойства перечислимых множеств
6.1. m-сводимость
6.2. m-полные множества
6.3. m-полнота и эффективная неперечислимость
6.4. Изоморфизм неполных множеств
6.5. Продуктивные множества
6.6. Пары неотделимых множеств
7. Вычисления с оракулом
7.1. Машины с оракулом
7.2. Эквивалентное описание
7.3. Релятивизация
7.4. 0' - вычисления
7.5. Несравнимые множества
7.6. Теорема Мучника Фридберга: общая схема
7.7. Теорема Мучника Фридберга: выигрышные условия
7.8. Теорема Мучника Фридберга: метод приоритета
7.9. Решётка Медведева
8. Арифметическая иерархия
8.1. Классы ?n и Пn
8.2. Универсальные множества в ?n и Пn
8.3. Операция скачка
8.4. Классификация множеств в иерархии
9. Машины Тьюринга
9.1. Зачем нужны простые вычислительные модели?
9.2. Машины Тьюринга: определение
9.3. Машины Тьюринга: обсуждение
9.4. Ассоциативные исчисления
9.5. Моделирование машин Тьюринга
9.6. Двусторонние исчисления
9.7. Полугруппы, образующие и соотношения
10. Арифметичность вычислимых функций
10.1. Программы с конечным числом переменных
10.2. Машины Тьюринга и программы
10.3. Арифметичность вычислимых функций
10.4. Теоремы Тарского и Геделя
10.5. Прямое доказательство теорем Тарского и Гёделя
10.6. Арифметическая иерархия и перемены кванторов
11. Рекурсивные функции
11.1. Примитивно рекурсивные функции
11.2. Примеры примитивно рекурсивных функций
11.3. Примитивно рекурсивные множества
11.4. Другие виды рекурсии
11.5. Машины Тьюринга и рекурсивные функции
11.6. Частично рекурсивные функции
11.7. Вычислимость с оракулом
11.8. Оценки скорости роста. Функция Аккермана
Литература
Предметный указатель
Указатель имён.
| Рейтинг: | 4.8 баллов / 2537 оценок |
| Формат: | Книга |
| Уже скачали: | 12851 раз |
Похожие Книги
Нам показалось, что Книги ниже Вас заинтересуют не меньше. Эти издания Вы так же можете скачивать и читать совершенно бесплатно на сайте!
-
Радиолоцман №5 (май), 2014
Колектив авторов Издательство: А.Николаев Год издания: 2014 Страниц: 68 Язык: русский Формат: PDF Размер: 6 Мб Журнал «Радиолоцман» будет интересен всем, кто интересуется электроникой. Ра . . .
-
Il Corriere della Sera (5.06.2014)
Название: Il Corriere della Sera (5.06.2014) Издатель: Rcs MediaGroupГод: 5 Giugno 2014 | 5 июня 2014Язык: ItalianФормат: pdf (оригинал)Страниц: 48Размер: 11.9 mb Il Corriere della Sera (5.06.2014) . . .
-
Hawker Typhoon IB (Airfix Model World Special Supplement)
Название: Hawker Typhoon 1BИздательство: Key PublishingСерия: Airfix Model World Special SupplementГод издания: 2014Язык: EnglishКоличество страниц: 24Формат: PDF OCRРазмер: 13,7 MBЖурнал для любителе . . .
-
BBC Knowledge Asia Edition - June 2014
Название: BBC Knowledge Asia Edition Год / месяц: June 2014 Номер: 6 Формат: pdf Страниц:100 Язык:English Размер: 24,6 Mb In this month’s issue of BBC Knowledge Magazine, we take a look at the lat . . .
-
Conceptive C
Название: Conceptive Cавтор: Harry McGeoughИздательство: CreateSpaceГод выпуска: 2012ISBN: 978-1469957395Формат: PDFРазмер: 18 MBКоличество страниц: 172Язык: АнглийскийОписание: Conceptive-C is an AI . . .
-
Аптечка-библиотечка №6, 2014
Название: Лечебные письма. Аптечка-библиотечкаНомер: № 6/2014Страниц: 112Формат: pdfРазмер: 56.38 MBЯзык: русскийТема: "Здоровье вaших ног"Приложение к газете «Лечебные письма». DOWNLOAD: -- df . . .
-
With Our Backs to the Wall. Victory and Defeat in 1918
Автор: David StevensonНазвание: With Our Backs to the Wall. Victory and Defeat in 1918Издательство: Belknap PressГод: 2011Формат: PDF Страниц: 747Язык: EnglishРазмер: 5.5 MBWith so much at stake and s . . .
-
Светлей лазури (Аудиокнига)
Название: Светлей лазуриАвтор: Александр Проханов Жанр: повестьИздательство: Нигде не купишьГод выпуска: 2014Тип: аудиокнигаЧитает (ют): Лебедева ЕленаЯзык: РусскийВремя звучания: 05:49:03Формат | Кач . . .
-
Фехтование. Начинающему тренеру. Методическое пособие
Название: Фехтование. Начинающему тренеру. Методическое пособие. Автор: Мовшович А. Издательство: Академический проектГод: 2011Страниц: 112Формат: PDFРазмер: 35.52 MBКачество: хорошееЯзык: русскийПосо . . .
-
Meine kreative Welt (2007-2013)
Название: Meine kreative Welt Издательство: Frechverlag GmbHГод / месяц: 2007-2013 Номер: в полной новости Формат: pdf Страниц:32-52 Язык:German Размер:185,3 Mb В журнале представлены креативные иде . . .
Вы не зарегистрированы!
Если вы хотите скачивать книги, журналы и аудиокниги бесплатно, без рекламы и без смс, оставлять комментарии и отзывы, учавствовать в различных интересных мероприятиях, получать скидки в книжных магазинах и многое другое, то Вам необходимо зарегистрироваться в нашей Электронной Библиотеке.
Отзывы читателей
Ой!
К сожалению, в нашей Бесплатной Библиотеке пока нет отзывов о Книге Лекции по математической логике и теории алгоритмов, Часть 3, Вычислимые функции, Верещагин Н.К., Шень А., 2012. Помогите нам и другим читателям окунуться в сюжет Книги и узнать Ваше мнение. Оставьте свой отзыв или обзор сейчас, это займет у Вас всего-лишь несколько минут.