Мальцев А.Н. Алгоритмы и рекурсивные функции. - М., 1986. - 366 с.
Посвящается одному из актуальных и бурно развивающихся разделов математической логики — теории алгоритмов, а также важнейшим ее связям с другими разделами математики. Является одним из лучших пособий для знакомства с основными направлениями, идеями и методами теории алгоритмов.
Для математиков различных специальностей: научных работников, аспирантов и студентов.
ОГЛАВЛЕНИЕ
Предисловие............................6
Предисловие редактора ко второму изданию....... . 8
Введение....................... . 9
Глава I. Основные понятия.............. 17
§ 1. Функции и операции.............. 17
1.1. Алфавит. Слова (17). 1.2. Функции. Термы (19). 1.3. Алгебры (24). 1.4. Кодирование (27). Примеры и задачи (30). § 2. Основные вычислимые операторы........ 30
2.1. Суперпозиции частичных функций (30).
2.2. Оператор примитивной рекурсии (33). 2.3. Операция, минимизации (39). 2.4. Общерекурсивные функции (45). Примеры и задачи (47).
Глава II. Примитивно рекурсивные функции и рекурсивно перечислимые множества ........... 49
§ 3. Примитивно рекурсивные функции....... 49
3.1. Операции суммирования и мажорированного обращения (49). 3.2. Примитивная рекурсивность некоторых арифметических функции (53).
3.3. Нумерация пар и п-оп чисел (60). 3.4. Зависимости между операторами примитивной рекурсии я минимизации (64). 3.5. Одноместные примитивно рекурсивные функции (68). Дополнения, примеры и задачи (76).
§ 4. Рекурсивно перечислимые множества....... 77
4.1. Рекурсивные и примитивно рекурсивные множества (77). 4.2. Рекурсивно перечислимые множества (79). 4.3. Порожденные множества (82).
4.4. Множества n-ок натуральных чисел (86). Примеры и задачи (91).
Глава III. Общерекурсивные и частично рекурсивные функции ...................... 93
§ 5. Общерекурсивные функции ............ 93
5.1. Рекурсии 2-й ступени (93). 5.2. Универсальная общерекурсивная функция (98). 5.3. Быстрорастущие функции (105). 5.4. Обращение функций. Алгебра Робинсон (108). Дополнения, примеры и задачи (ИЗ).
§ 6. Частично рекурсивные функции......... 114
6.1. Параметризация частично рекурсивных функций (114). 6.2. Универсальные частично рекурсивные функции (120). 6.3. Доопределение функций. Построение нерекурсивного рекурсивно перечислимого множества (123). 6.4. Исследование представления К лини (127). Дополнения, примеры и задачи (129).
Глава IV. Нумерованные совокупности......... 133
§ 7. Нумерации совокупностей множеств и функций 133 7.1. Универсальные функции Клини (133). 7.2. Нумерация Клини (136). 7.3. Нумерация Поста (139). 7.4. Однозначные нумерации (145). Дополнения, примеры и задачи (155).
§ 8. Сводимость и креативность множеств....... 156
8.1. Сводимость и m-эквивалентность множеств (156). 8.2. Продуктивные и креативные множества (159). 8.3. Простые множества (163). 8.4. Максимальные множества (164). Дополнения, примеры и задачи (167).
§ 9. Нумерации произвольных совокупностей .... 171 9.1. Изоморфизм и эквивалентность нумераций (171). 9.2. Односводимость нумераций (176). 9.3. Полные нумерации (183). 9.4. Семейства объектов нумерованных совокупностей (188). Дополнения, примеры и задачи (191).
§ 10. Универсальные и креативные системы множеств 192
10.1. m-универсальные системы множеств (192).
10.2. Креативные системы множеств (196). 10.3. Рекурсивно неотделимые множества (199). Дополнения, примеры и задачи (202).
Глава V. Алгоритмы и машины Тьюринга...... 204
§ 11. Словарные множества и функции........ 204
11.1. Словарные множества (205). 11.2. Основные словарные операторы (209). 11.3. Прямое определение класса частично рекурсивных словарных функций (215). Дополнения и примеры (218).
§ 12. Машины Тьюринга............... 218
12.1. Машины Тьюринга — Поста (219). 12.2. Вычислимые функции (225). 12.3. Синтез машин Тьюринга (230). 12.4. Теоремы о графике и существовании универсальных частично рекурсивных функций (243). 12.5. Универсальные машины (250). Дополнения, примеры и задачи (252).
§ 13. Приложения.................. 254
13.1. Проблема равенства слов в полугруппах (254). 13.2. Тоядественно истинные формулы исчисления предикатов 1-й ступени (263). 13.3. Арифметические множества (270). 13.4. Формулы 2-й ступени (276). Дополнения и примеры (277).
Глава VI. Варианты машин и алгоритмов Тьюринга —Поста ............................283
§ 14. Нормальные и операторные алгоритмы..... 283
14.1. Формальные системы. Продукции Поста (284). 14.2. Нормальные алгоритмы (289). 14.3. Операторные алгоритмы (291). Дополнения и примеры (301).
§ 15. Многоленточные машпны и ТАГ-системы .... 302 15.1. Общие многоленточные машины (302). 15.2. Машины Минского (304). 15.3. Однородные продукции. ТАГ-системы (315). Дополнения, примеры и задачи (320).
§ 16. Диофаyтовы уравнения............. 324
16.1. Диофантовы предикаты и функции (324).
16.2. Арифметическое представление (330). 16.3. Представимость натуральных чисел многочленами (336). 16.4. Показательные уравнения (339). Дополнения и примеры (346).
Список литературы ................... 348
Приложение. Диофантовость рекурсивно перечислимых множеств и предикатов (Д. А. Захаров) .... 355
Предметный указатель.................. 365
