РЕШАЕМ МАТЕМАТИКУ ВМЕСТЕ!
 
СТУДЕНТАМ:    Учебники     Решебники    Шпаргалки    Контрольные работы   Видео уроки

ШКОЛЬНИКАМ:  ГДЗ - 1 класс  2 класс  3 класс  4 класс  5 класс  6 класс  7 класс  8 класс  9 класс  10 класс  11 класс

Главная » Файлы » Учебные материалы » Математическая логика и теория алгоритмов
Мальцев А.Н. Алгоритмы и рекурсивные функции.

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

ОГЛАВЛЕНИЕ
Предисловие  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. Нумерация пар и п-ок чисел F0).
   3.4. Зависимости между операторами примитивной рекурсии и минимизации (64).
   3.5.Одноместные примитивно рекурсивные функции (68).Дополнения, примеры и  изадачи(76).
§ 4. Рекурсивно перечислимые множества 77
   4.1. Рекурсивные и примитивно рекурсивные множества (77).
   4.2. Рекурсивно перечлслимые множества (79).
   4.3. Порожденные множества (82).
   4.4. Множества ге-ок натуральных чисел (86). Примеры и задачи (91).
Глава III. Общерекурсивные и частично рекурсивные функции 93
§ 5. Общерекурсивные функции 93
  5.1. Рекурсии 2-й ступени (93).
  5.2.Универсальная общерекурспвная функция (98).
  5.3. Быстрорастущие функции (105).
  5.4. Обращение функций. Алгебра Робинсон (108). Дополнения, примеры и задачи (113).
§ 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. Сводимость и го-эквивалентность множеств (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). Дополнения, примеры и              задачиA91).
§ 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-й ступени B63).
   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).
Список литературы (348) 
Приложение. Диофантовость рекурсивно-перечислимых множеств и предикатов
(Д. А.Захаров) 355
Предметный указатель 365





Размер файла: (4.47Mb)

Категория: Математическая логика и теория алгоритмов | Добавил: nikka
Просмотров: 3933 | Загрузок: 727 | Рейтинг: 5.0/1


Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]



ВЫБОР ПО КАТЕГОРИЯМ:

Аналитическая геометрия и алгебра [0]
Высшая алгебра [52]
История математики [55]
Математика для технарей [21]
Математика для экономистов, юристов и т.д.. [5]
Математическая логика и теория алгоритмов [40]
Теория вероятностей и мат. статистика [28]
Теория чисел [33]
Учебники по математике [46]



При полном или частичном использовании материалов
активная ссылка на портал VMATE.RU обязательна


Высшая математика онлайн - всё бесплатно, наш портал создан специально для студентов кому интересна высшая математика. У нас на портале возможно скачать бесплатно учебники по высшей математике, книги по математике или сделать заказ учебных пособий, скачать контрольные по высшей математике, заказать, задачники по высшей математики и решебники. Оставить запрос по предмету - аналитическая геометрия или задать вопрос - справочная по математике Заказать решение и т.д. Высшая математика онлайн - математический портал и здесь собраны шпаргалки по высшей математике и видео уроки. Добро пожаловать! Вход