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

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

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





Предисловие.

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

ОГЛАВЛЕНИЕ.

Предисловие
Глава 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
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


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




Теги: Марченков :: 2017 :: функция :: математика