Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. 2-е изд., исправленное. М., 2002, 192 с.
Книга написана по материалам лекций и семинаров, проводившихся авторами для студентов младших курсов мехмата МГУ. В ней рассказывается об основных понятиях общей теории вычислимых функций (вычислимость, разрешимость, перечислимость, универсальные функции, нумерации и их свойства, ш-полнота, теорема о неподвижной точке, арифметическая иерархия, вычисления с оракулом, степени неразрешимости) и о конкретных вычислительных моделях (машины Тьюринга, рекурсивные функции). Изложение рассчитано на учеников математических школ, студентов-математиков и всех интересующихся основами теории алгоритмов. Книга включает себя около 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. m-сводимость и свойства перечислимых множеств 64
6.1. m-сводимость..................................64
6.2. m-полные множества..........................66
6.3. m-полнота и эффективная неперечислимость...........67
6.4. Изоморфизм m-полных множеств............71
6.5. Продуктивные множества....................74
6.6. Пары неотделимых множеств................78
7. Вычисления с оракулом 82
7.1. Машины с оракулом............................82
7.2. Эквивалентное описание......................85
7.3. Релятивизация..................................88
7.4. O'-вычисления..................................91
7.5. Несравнимые множества......................95
7.6. Теорема Мучника-Фридберга: схема конструкции............98
7.7. Теорема Мучника-Фридберга: выигрышные условия.............101
7.8. Теорема Мучника-Фридберга: метод приоритета...................103
8. Арифметическая иерархия 105
8.1. Классы Σn и Пn................105
8.2. Универсальные множества в Σn и Пn ........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
