Алгоритмы и рекурсивные функции, Мальцев А.И., 1986

Алгоритмы и рекурсивные функции, Мальцев А.И., 1986.
   
   Посвящается одному из актуальных и бурно развивающихся разделов математической логики — теории алгоритмов, а также важнейшим ее связям с другими разделами математики. Является одним из лучших пособий для знакомства с основными направлениями, идеями и методами теории алгоритмов.
Для математиков различных специальностей: научных работников, аспирантов и студентов.




Функции и операции.
Этот параграф имеет вспомогательное значение. Здесь с целью установления терминологии и употребляющейся далее символики напоминаются определения ряда всем известных общематематических понятий.

Алфавит. Слова. Исходным материалом для нас будет служить понятие ленты, разделенной па («равные») участки, называемые ячейками или клетками. Лента будет считаться конечной длины в каждый момент времени, неограниченно продолжаемой (надстраиваемой) в обе стороны п направленной, так что у каждой ячейки есть соседняя справа и соседняя слева.

Предполагается, что каждая ячейка ленты может находиться в различных состояниях и что эти состояния сравнимы, так что мы можем однозначно решить, находятся ли произвольные две ячейки в «одинаковых» состояниях или в разных. Одно из возможных состояний ячеек будет называться исходным. Ячейки, находящиеся в этом состоянии, называются пустыми. Остальные состояния будут обозначаться буквами, занимающими соответствующие ячейки.

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



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Алгоритмы и рекурсивные функции, Мальцев А.И., 1986 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: учебник по математике :: математика :: Мальцев