Конечные базисы по суперпозиции в классах элементарных рекурсивных функций

• Автор: Волков, Сергей Александрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 126 с.

Оглавление
Введение
1. Краткий обзор результатов по теме диссертации
1.1. Классификации рекурсивных функций
1.2. Конечные базисы по суперпозиции
2. Общая характеристика работы
3. Формулировка основных результатов
3.1. Основные определения
3.2. Основные результаты главы
3.3. Основные результаты главы
3.4. Основные результаты главы
1. Порождение некоторых классов суперпозициями простых арифметических функций
1. Экспоненциальное расширение класса функций, элементарных по Сколему, и формулы высоты два
1.1. Определения
1.2. Включение ГхУ С ХЭ
1.3. Классы ВА, ВА и Г- полиномиальность
1.4. Включение ХБ С [Т]2х
1.5. Доказательство теоремы
2. Базис по суперпозиции в РРОМ
2.1. Определения
2.2. Совпадение классов РБОМ, РРОМа11 и РРОМуаг
2.3. Принадлежность некоторых функций классу [Т'
2.4. Правильность предикатов, соответствующих РОМ-
формулам

2.5. Доказательство теоремы
3. Иерархии классов, исчерпывающие класс функций, элементарных по Кальмару, и формулы произвольной высоты
3.1. Определения
3.2. Совпадение классов ХЭП и ХБ+
3.3. Доказательство теоремы
2. Простой базис по суперпозиции в классе £2 иерархии Гже-горчика
1. Машины Минского
2. Вектор-функции, конфигурации и их коды
3. Основное свойство функции <5
4. Доказательство теоремы
3. Конечная порождаемость некоторых групп рекурсивных перестановок
1. Определения
2. Конечная порождаемость группы Ог((5)
3. Порождаемость группы Ог(<5) двумя перестановками
4. Конечная порождаемость группы Ог(<5) для конкретных
классов (3
Литература

Введение
1. Краткий обзор результатов по теме диссертации
1.1. Классификации рекурсивных функций
Понятие алгоритмически вычислимой (рекурсивной) функции является одним из основных в современной математике. Формализация понятия вычислимой функции была выполнена в середине 1930-х годов известными математиками: А. Тьюрингом [30], Э. Постом [25], А. Чёрчем [17], С. Кли-ни [22] и др. Для каждой из этих формализаций существует тезис (тезис Чёрча-Тьюринга), который утверждает, что класс всех алгоритмически вычислимых функций совпадает с классом функций, вычислимых в данной формализации.
Существуют разные подходы к формализации понятия вычислимой функции. Однако всегда пользуются предпочтением наиболее простые формализации. Самым известным является подход, основанный на использовании моделей различных механических устройств, таких, как машина Тьюринга [30, 25].
Другой подход основан на порождении функций на основе базового набора функций и некоторых порождающих операций. С. Клини в своей работе [22] ввел понятие частично рекурсивной функции. Частично рекурсивная функция — это частично определенная функция / : Мр —> N0 , которую можно получить из исходных функций 0, ж+1 с помощью конечного числа применений операций суперпозиции (суперпозиция включает подстановку функций в функции, перестановку и отождествление переменных, введение фиктивных переменных), примитивной рекурсии и минимизации.
Заметим, что класс всех вычислимых функций не является адекватной формализацией понятия вычислимости на практике. Например, функция

Ясно, что предикат (х < у) лежит в S* (см. [10]). Поэтому
(:У < /(£)) е S*.
Из этого и следует доказываемое утверждение. □
Теорема 7. Имеет место включение [Т]хУ С XS.
Доказательство. Докажем это утверждение индукцией по построению функций в классе [Тху. Пусть h Е Тху- Тогда возможны случаи.
1. h Е Т. Тогда очевидно (см. например [10]), что h Е S. Из S С XS следует, что h Е XS.
2. h получается из / перестановкой, отождествлением переменных или введением фиктивных переменных, / 6 XS. В этом случае включение h Е XS, следует из того, что класс S замкнут относительно суперпозиции (в частности, перестановки, отождествления переменных, введения фиктивных переменных).
3. h(x) = f(gi(x)
4. h = /9, где / е XS, д Е [Т]. Тогда можно записать
h _ flenW+l)'
Ясно, что д Е S (см. [10]), поэтому 29-El Е XS (утверждение 1.1.2.10). Отсюда, из соотношения ж1еп(Я g FFOM (утверждение 1.1.2.9) и из утверждения 1.1.2.8 следует, что h Е XS.
Теорема доказана. □
1.3. Классы ВА#, ВА и Т- полиномиальность
Утверждение 1.1.3.1. Класс ВА:,/,/~ замкнут относительно ограниченных квантификаций вида (Вх)х<р и (Ух)х<р, где р — полином с натуральными коэффициентами.