Алгоритмы и рекурсивные функции

Автор(ы):Мальцев А. И.
06.10.2007
Год изд.:1986
Издание:2
Описание: Посвящается одному из актуальных и бурно развивающихся разделов математической логики - теории алгоритмов, а также важнейшим ее связям с другими разделами математики. Является одним из лучших пособий для знакомства с основными направлениями, идеями и методами теории алгоритмов. Для математиков различных специальностей научных работников, аспирантов, студентов.
Оглавление:
Алгоритмы и рекурсивные функции — обложка книги.
Предисловие [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. Нумерация пар и n-ок чисел [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]
      Дополнения, примеры и задачи [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]
      Дополнения, примеры и задачи [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. Диофаптовы уравнения [324]
    16.1. Диофантовы предикаты и функции [324]
    16.2. Арифметическое представление [330]
    16.3. Представимость натуральных чисел многочленами [336]
    16.4. Показательные уравнения [339]
      Дополнения и примеры [346]
Список литературы [348]
Приложение. Диофантовость рекурсивно перечислимых множеств и предикатов (Д. А. Захаров) [355]
Предметный указатель [365]
Формат: djvu
Размер:3594256 байт
Язык:RUS
Рейтинг: 244 Рейтинг
Открыть: