Классы элементарных рекурсивных функций, Марченков С.С., 2017

Классы элементарных рекурсивных функций, Марченков С.С., 2017.

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




Конечные базисы по суперпозиции.
Пусть Q — некоторый класс функций, замкнутый относительно операции суперпозиции, и Q0 ⊆ Q. Будем говорить, что система Q0 порождает класс Q (относительно операции суперпозиции), если замыкание системы Q0 относительно операции суперпозиции совпадает с классом Q. Конечные порождающие системы класса Q принято называть (конечными) базисами по суперпозиции в классе Q.

ледует отметить два обстоятельства, связанные с конечными базисами по суперпозиции. Во-первых, конечный базис по суперпозиции может и не быть независимой системой. Иными словами, некоторые функции базиса могут выражаться через другие функции базиса с помощью операции суперпозиции. Во-вторых, если класс Q не состоит только из одноместных функций, то, говоря о конечном базисе по суперпозиции в классе Q, мы допускаем в качестве суперпозиций так называемые «нерегулярные» суперпозиции (см. об этом в начале § 1.4). В противном случае, как нетрудно понять, из конечного набора функций с помощью операции суперпозиции можно получить лишь функции от ограниченного числа переменных.

ОГЛАВЛЕНИЕ.
Предисловие.
Глава I. Ограниченно арифметические и рудиментарные предикаты.
§1.1. Ограниченно арифметические предикаты.
§1.2. Рудиментарные предикаты.
§1.3. Рудиментарное моделирование вычислений на машинах Тьюринга.
§1.4. Классы FBA, FR, BPC.
Задачи и темы для дальнейших исследований.
Глава II. Функции, элементарные по Сколему, и классы Гжегорчика.
§2.1. Ограниченная рекурсия и нумерационные функции.
§2.2. Функции, элементарные по Сколему.
§2.3. Классы Гжегорчика.
§2.4. Соотношение между классами Sk и E0.
§2.5. Функции, элементарные по Кальмару.
Задачи и темы для дальнейших исследований.
Глава III. Машинное описание классов.
§3.1. Стековые регистровые машины.
§3.2. Вычисления на машинах SRM с ограничениями на зону.
§3.3. Универсальные функции.
§3.4. Конечные базисы по суперпозиции.
Задачи и темы для дальнейших исследований.
Глава IV. Простой базис по суперпозиции в классе E2.
§4.1. Основные понятия и формулировка центрального результата.
§4.2. Конфигурации и коды конфигураций машин Минского.
§4.3. Вывод свойств функции Q.
§4.4. Доказательство основной теоремы.
Задачи и темы для дальнейших исследований.
Глав  V. Простые базисы по суперпозиции в классе функций, элементарных по Кальмару.
§5.1. Построение простейших функций.
§5.2. Построение функций нод, exp2, σ.
§5.3. Однократные экзистенциальные представления предикатов.
§5.4. Суммирование экспоненциально полиномиальных выражений.
Приложение 5.1. Биномиальные коэффициенты и теорема Куммера.
Приложение 5.2. Суммирование обобщенной геометрической прогрессии.
Список литературы.
Предметный указатель.



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

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


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

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




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