Успенский В.А. Лекции о вычислимых функциях

Успенский В.А. Лекции о вычислимых функциях.- М., 1960. - 492 с.
Настоящие «Лекции» посвящены изложению основ теории вычислимых функций (проводимому на базе принятого в настоящее время отождествления их — для случая функций с натуральными аргументами и значениями — с частично-рекурсивными функциями), а также некоторым приложениям этой теории.
СОДЕРЖАНИЕ
Предисловие................................................8
§ 1. Введение.................................15
§ 2. Предварительные сведения из теории множеств и функций.........24
1. Множества..........................................24
2. Функции............................................'29
3. Подстановка........................................32
4. Частичные отображения .........................38
5. Функции большого размаха .......................43
6. Характеристические функции........................45
7. Примитивная рекурсия....................48
8. Примеры вычислимых функций................51
§ 3. Предварительные сведения из математической логики 53
1. Высказывания и высказывательные формы..........53
2. Истинностные значения............................61
3. Предикаты и операции над ними....................64
4. Ограниченные кванторы............................78
5. Оператор «наименьшее число»......................81
6. Ограниченный оператор «наименьшее число» .... 83
7. Ограниченный оператор «наибольшее число» .... 85
8. Ограниченный оператор «число тех, которые» ... 86
9. Интуитивно-вычислимые предикаты................86
§ 4. Примитивно-рекурсивные функции, множества, предикаты.......90
1. Примитивно-рекурсивные функции..................91
2. Примитивно-рекурсивные множества................99
3. Примитивно-рекурсивные предикаты................106
4. Примитивно-рекурсивные функции (окончание) ... 114
5. Примитивно-рекурсивное соответствие между N и N3......119
6. Примитивно-рекурсивный пересчет множества N ............426
§ 5. Рекурсивно-перечислимые множества и предикаты .............136
1. Рекурсивно-перечислимые множества................136
2. Рекурсивно-перечислимые предикаты................149
§ 6. Частично-рекурсивные функции........................153
1. Определение и Основная гипотеза..................154
2. Функции с рекурсивно-перечислимым графиком . . 159
3. Следствия Теоремы о графике......................107
§ 7. Общерекурсивные функции, множества, предикаты . . 176
1. Общерекурсивные функции и множества 176.
2. Общерекурсивные предикаты..............182
3. Общерекурсивные пересчеты........................184
§ 8. Функция, универсальная для примитивно-рекурсивных функций..........190
1. Вспомогательный аппарат ........................191
2. Универсальная функция............................203
3. Важные примеры....................................237
§ 9. Функция, универсальная для частично-рекурсивных функций, и множество, универсальное для рекурсивно-перечислимых множеств......................248
1. Универсальная функция..............................249
2. Важные примеры.........................255
3. Универсальное множество. Универсальная пара .......265
§ 10. Дополнительные сведения о рекурсивно-перечислимых множествах........276
1. Униформизуемость..................................278
2. Отделимость и неотделимость . ...................281
3. Простые множества..................................286
§ 11. Нумераций и операции...........................294
1. Нумерации и занумерованные множества............294
2. Нумерации систем ......................298
3. Конструктивные операторы..........................322
§ 12. Приложения теории вычислимых функций к математическому анализу: выделение вычислимых действительных
чисел..............................335
1. Действительные числа...................336
a) Канторова теория................................337
b) Дедекиндова теория..............................338
c) Сегментная теория ..............................339
d) q-ичная теория .............................339
2. Вычислимые функции от рациональных чисел .... 341
3. Вычислимые действительные числа..................347
a) Числа, вычислимые по Кантору..................347
b) Числа, вычислимые по Дедекинду........ 351
c) Сегментно вачислимые числа......................354
d) Десятично вычислимые числа; q-ично вычислимые числа............................................356
e) Конструктивный континуум......................359
4. Системы обозначений вычислимых действительных чисел..........360
§ 13. Приложения теории вычислимых функций к логике:
конструктивизация отрицательных определений .... 379
1. Конструктивная неконечность......................380
2. Конструктивная неперечислимость..................388
3. Конструктивная неотделимость....... . . . . 395
§ 14. Приложения теории вычислимых функций к вычислительной математике: возможности абстрактных вычислительных машин .................................401
1. Машины типа I....................................401
2. Машины типа II....................................407
3. Многоленточные машины............................417
4. Функции, вычислимые на машинах................425
5. Доказательство теорем 3 и 4........................470
Упомянутая литература....................................476
Указатель терминов........................................482
Указатель обозначений .....................488

Created using FlowPaper Flipbook Maker ↗