Показать ещё...
Предисловие................ 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
|
2023. 720 с. Твердый переплет. 16.9 EUR
Книга «Зияющие высоты» – первый, главный, социологический роман, созданный интеллектуальной легендой нашего времени – Александром Александровичем Зиновьевым (1922-2006), единственным российским лауреатом Премии Алексиса де Токвиля, членом многочисленных международных академий, автором десятков логических... (Подробнее) URSS. 2023. 272 с. Мягкая обложка. 15.9 EUR
Настоящая книга посвящена рассмотрению базовых понятий и техник психологического консультирования. В ней детально представлены структура процесса консультирования, описаны основные его этапы, содержание деятельности психолога и приемы, которые могут быть использованы на каждом из них. В книге... (Подробнее) 2023. 696 с. Твердый переплет в суперобложке. 119.9 EUR
Опираясь на новейшие исследования, историк Кристофер Кларк предлагает свежий взгляд на Первую мировую войну, сосредотачивая внимание не на полях сражений и кровопролитии, а на сложных событиях и отношениях, которые привели группу благонамеренных лидеров к жестокому конфликту. Кларк прослеживает... (Подробнее) URSS. 2024. 704 с. Твердый переплет. 26.9 EUR
В новой книге профессора В.Н.Лексина подведены итоги многолетних исследований одной из фундаментальных проблем бытия — дихотомии естественной неминуемости и широчайшего присутствия смерти в пространстве жизни и инстинктивного неприятия всего связанного со смертью в обыденном сознании. Впервые... (Подробнее) URSS. 2024. 800 с. Мягкая обложка. 37.9 EUR
ВЕРСАЛЬ: ЖЕЛАННЫЙ МИР ИЛИ ПЛАН БУДУЩЕЙ ВОЙНЫ?. 224 стр. (ТВЁРДЫЙ ПЕРЕПЛЁТ) 11 ноября 1918 года в старом вагоне неподалеку от Компьеня было подписано перемирие, которое означало окончание Первой мировой войны. Через полгода, 28 июня 1919 года, был подписан Версальский договор — вердикт, возлагавший... (Подробнее) URSS. 2024. 344 с. Мягкая обложка. 18.9 EUR
Мы очень часто сталкиваемся с чудом самоорганизации. Оно воспринимается как само собой разумеющееся, не требующее внимания, радости и удивления. Из случайно брошенного замечания на семинаре странным образом возникает новая задача. Размышления над ней вовлекают коллег, появляются новые идеи, надежды,... (Подробнее) URSS. 2024. 576 с. Мягкая обложка. 23.9 EUR
Эта книга — самоучитель по военной стратегии. Прочитав её, вы получите представление о принципах военной стратегии и сможете применять их на практике — в стратегических компьютерных играх и реальном мире. Книга состоит из пяти частей. Первая вводит читателя в мир игр: что в играх... (Подробнее) URSS. 2024. 248 с. Мягкая обложка. 14.9 EUR
В книге изложены вопросы новой области современной медицины — «Anti-Ageing Medicine» (Медицина антистарения, или Антивозрастная медицина), которая совмещает глубокие фундаментальные исследования в биомедицине и широкие профилактические возможности практической медицины, а также современные общеоздоровительные... (Подробнее) URSS. 2024. 240 с. Твердый переплет. 23.9 EUR
Предлагаемая вниманию читателей книга, написанная крупным биологом и государственным деятелем Н.Н.Воронцовым, посвящена жизни и творчеству выдающегося ученого-математика, обогатившего советскую науку в области теории множеств, кибернетики и программирования — Алексея Андреевича Ляпунова. Книга написана... (Подробнее) 2023. 416 с. Твердый переплет. 19.9 EUR
Вам кажется, что экономика — это очень скучно? Тогда мы идем к вам! Вам даже не понадобится «стоп-слово», чтобы разобраться в заумных формулах — их в книге нет! Все проще, чем кажется. Автор подаст вам экономику под таким дерзким соусом, что вы проглотите ее не жуя! Вы получите необходимые... (Подробнее) |