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