Мальцев А.Н. Алгоритмы и рекурсивные функции ОНЛАЙН


Для математиков различных специальностей: научных работников, аспирантов и студентов.
ОГЛАВЛЕНИЕ
Предисловие……………………….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



Читать онлайн
скачать бесплатно


Теги:
теория алгоритмов, Мальцев теория алгоритмов

Коментарі до Мальцев А.Н. Алгоритмы и рекурсивные функции ОНЛАЙН