РЕШАЕМ МАТЕМАТИКУ ВМЕСТЕ!
 
СТУДЕНТАМ:    Учебники     Решебники    Шпаргалки    Контрольные работы   Видео уроки

ШКОЛЬНИКАМ:  ГДЗ - 1 класс  2 класс  3 класс  4 класс  5 класс  6 класс  7 класс  8 класс  9 класс  10 класс  11 класс


Главная » Файлы » Учебные материалы » Математическая логика и теория алгоритмов
Н.К.Верещагин, А.Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции.

19.12.2011, 17:01
В книге рассказывается об основных понятиях общей теории вычислимых функций (вычислимость, разрешимость, перечислимость, универсальные функции, нумерации и их свойства, m-полнота, теорема о неподвижной точке, арифметическая иерархия, вычисления с оракулом, степени неразрешимости) и о конкретных вычислительных моделях (машины Тьюринга, рекурсивные функции). Изложение рассчитано на учеников математических школ, студентов-математиков и всех интересующихся основами теории алгоритмов. Книга включает себя около 90 задач различной трудности.

Оглавление

Предисловие 6
1. Вычислимость, разрешимость и перечислимость 9
1.1. Вычислимые функции 9
1.2. Разрешимые множества 10
1.3. Перечислимые множества 11
1.4. Перечислимые и разрешимые множества 14
1.5. Перечислимость и вычислимость 15
2. Универсальные функции и неразрешимость 19
2.1. Универсальные функции 19
2.2. Диагональная конструкция 20
2.3. Перечислимое неразрешимое множество  22
2.4. Перечислимые неотделимые множества 24
2.5. Простые множества: конструкция Поста 25
3. Нумерации и операции 27
3.1. Главные универсальные функции 27
3.2. Вычислимые последовательности функций 31
3.3. Главные универсальные множества 32
4. Свойства главных нумераций 35
4.1. Множества номеров 35
4.2. Новые номера старых функций 39
4.3. Изоморфизм главных нумераций 42
4.4. Перечислимые свойства функций 44
5. Теорема о неподвижной точке 49
5.1. Неподвижная точка и отношения эквивалентности 49
5.2. Программа, печатающая свой текст 52
5.3. Системный трюк: ещё одно доказательство 54
5.4. Несколько замечаний 58
6. га-сводимость и свойства перечислимых множеств 64
6.1. га-сводимость 64
6.2. га-полные множества 66
6.3. га-полнота и эффективная неперечислимость 67
6.4. Изоморфизм га-полных множеств 71
6.5. Продуктивные множества 74
6.6. Пары неотделимых множеств 78
7. Вычисления с оракулом 82
7.1. Машины с оракулом 82
7.2. Эквивалентное описание 85
7.3. Релятивизация 88
7.4. 0'-вычисления 91
7.5. Несравнимые множества 95
7.6. Теорема Мучника-Фридберга: схема конструкции 98
7.7. Теорема Мучника-Фридберга: выигрышные условия 101
7.8. Теорема Мучника-Фридберга: метод приоритета 103
8. Арифметическая иерархия 105
8.1. Классы Ση и Пп 105
8.2. Универсальные множества в Ση и Пп  108
8.3. Операция скачка 110
8.4. Классификация множеств в иерархии  116
9. Машины Тьюринга 120
9.1. Зачем нужны простые вычислительные модели? 120
9.2. Машины Тьюринга: определение 121
9.3. Машины Тьюринга: обсуждение 123
9.4. Ассоциативные исчисления 126
9.5. Моделирование машин Тьюринга 128
9.6. Двусторонние исчисления 132
9.7. Полугруппы, образующие и соотношения  134
10. Арифметичность вычислимых функций 138
10.1. Программы с конечным числом переменных 138
10.2. Машины Тьюринга и программы 141
10.3. Арифметичность вычислимых функций  143
10.4. Теоремы Тарского и Гёделя 148
10.5. Прямое доказательство теорем Тарского и Гёделя 150
10.6. Арифметическая иерархия и перемены кванторов 154
11. Рекурсивные функции 157
11.1. Примитивно рекурсивные функции 157
11.2. Примеры примитивно рекурсивных функций 158
11.3. Примитивно рекурсивные множества  159
11.4. Другие виды рекурсии 162
11.5. Машины Тьюринга и рекурсивные функции 165
11.6. Частично рекурсивные функции 168
11.7. Вычислимость с оракулом 172
11.8. Оценки скорости роста. Функция Аккермана 175
Литература 179
Предметный указатель 181
Указатель имён 188





Размер файла: (972.6Kb)

Категория: Математическая логика и теория алгоритмов | Добавил: nikka
Просмотров: 2044 | Загрузок: 403 | Рейтинг: 2.0/1


Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]



ВЫБОР ПО КАТЕГОРИЯМ:

Аналитическая геометрия и алгебра [0]
Высшая алгебра [52]
История математики [55]
Математика для технарей [21]
Математика для экономистов, юристов и т.д.. [5]
Математическая логика и теория алгоритмов [40]
Теория вероятностей и мат. статистика [28]
Теория чисел [33]
Учебники по математике [46]



При полном или частичном использовании материалов
активная ссылка на портал VMATE.RU обязательна


Высшая математика онлайн - всё бесплатно, наш портал создан специально для студентов кому интересна высшая математика. У нас на портале возможно скачать бесплатно учебники по высшей математике, книги по математике или сделать заказ учебных пособий, скачать контрольные по высшей математике, заказать, задачники по высшей математики и решебники. Оставить запрос по предмету - аналитическая геометрия или задать вопрос - справочная по математике Заказать решение и т.д. Высшая математика онлайн - математический портал и здесь собраны шпаргалки по высшей математике и видео уроки. миэмп Добро пожаловать! Вход