• Язык
   

 

Классы элементарных рекурсивных функций

ISBN: 978-5-9221-1714-2

Москва: Физматлит, 2017

Объем (стр):136

 

Постраничный просмотр для данной книги Вам недоступен.

Книга доступна только по подписке.

Аннотация

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

Содержание

Предисловие 5
Глава I. Ограниченно арифметические и рудиментарные предикаты 8
§ 1.1. Ограниченно арифметические предикаты 8
§ 1.2. Рудиментарные предикаты 15
§ 1.3. Рудиментарное моделирование вычислений на машинах Тьюринга 27
§ 1.4. Классы FBA, FR, BPC 37
Задачи и темы для дальнейших исследований 46
Глава II. Функции, элементарные по Сколему, и классы Гжегорчика 49
§ 2.1. Ограниченная рекурсия и нумерационные функции 49
§ 2.2. Функции, элементарные по Сколему 51
§ 2.3. Классы Гжегорчика 59
§ 2.4. Соотношение между классами Sk⁎ и ε⁎⁰ 70
§ 2.5. Функции, элементарные по Кальмару 76
Задачи и темы для дальнейших исследований 81
Глава III. Машинное описание классов 84
§ 3.1. Стековые регистровые машины 84
§ 3.2. Вычисления на машинах SRM с ограничениями на зону 85
§ 3.3. Универсальные функции 89
§ 3.4. Конечные базисы по суперпозиции 96
Задачи и темы для дальнейших исследований 102
Глава IV. Простой базис по суперпозиции в классе ε² 104
§ 4.1. Основные понятия и формулировка центрального результата 104
§ 4.2. Конфигурации и коды конфигураций машин Минского 106
§4.3. Вывод свойств функции Q 111
§ 4.4. Доказательство основной теоремы 114
Задачи и темы для дальнейших исследований 117
Глава V. Простые базисы по суперпозиции в классе функций, элементарных по Кальмару 118
§ 5.1. Построение простейших функций 118
§ 5.2. Построение функций нод, exp₂, σ 120
§ 5.3. Однократные экзистенциальные представления предикатов 122
§ 5.4. Суммирование экспоненциально полиномиальных выражений 125
Приложение 5.1. Биномиальные коэффициенты и теорема Куммера 130
Приложение 5.2. Суммирование обобщенной геометрической прогрессии 131
Список литературы 133
Предметный указатель 136

Рекомендации материалов по теме: нет