URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Мальцев А.И. Алгоритмы и рекурсивные функции
Id: 56146
 
599 руб.

Алгоритмы и рекурсивные функции. Изд.2

1986. 368 с. Твердый переплет. Букинист. Состояние: 4+. Есть погашенная библиотечная печать.

 Аннотация

Данная книга посвящена систематическому изложению теории алгоритмов и рекурсивных функций. В начальных главах указываются точные определения различных классов рекурсивных функций, доказываются фундаментальные свойства этих классов и строятся примеры рекурсивных функций, обладающих рядом особо важных свойств. В последующих главах рассматриваются классы алгоритмов, достаточные для вычисления произвольных рекурсивных функций и связанные с так называемыми машинами Тьюринга--Поста.


 ОГЛАВЛЕНИЕ

Предисловие................ 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. Множества ге-ок натуральных чисел (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. Сводимость и 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. Диофантовы уравнения............. 324

16.1. Диофантовы предикаты и функции (324).

16.2. Арифметическое представление (330). 16.3. Представимость натуральных чисел многочленами (336). 16.4. Показательные уравнения (339). Дополнения и примеры (346)

Список литературы................... 348

Приложение. Диофантовость рекурсивно перечислимых множеств и предикатов (Д. А. Захаров).... 355

Предметный указатель.................. 365

 
© URSS 2016.

Информация о Продавце