Конечные базисы по суперпозиции в классах элементарных рекурсивных функций тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. Ломоносова

На правах рукописи

□ □34 ГВО-г: .

ВОЛКОВ Сергей Александрович

КОНЕЧНЫЕ БАЗИСЫ ПО СУПЕРПОЗИЦИИ В КЛАССАХ ЭЛЕМЕНТАРНЫХ РЕКУРСИВНЫХ ФУНКЦИЙ

Специальность 01.01.09 — дискретная математика и математическая

кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 7 С"

> Т" '1^

Москва - 2009

003476627

Работа выполнена на кафедре математической кибернетики факультета вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова.

Научный руководитель: доктор физико-математических наук,

профессор кафедры математической кибернетики факультета ВМиК МГУ Марченков Сергей Серафимович.

Официальные оппоненты: доктор физико-математических наук,

профессор Института проблем передачи информации имени А. А. Харкевича РАН Вьюгин Владимир Вячеславович;

кандидат физико-математических наук, старший научный сотрудник Вычислительного центра имени А. А. Дородницына РАН Вялый Михаил Николаевич.

Ведущая организация: Институт системного программирования РАН.

Защита диссертации состоится 9 октября 2009 г. в 11 час. 00 мин. на заседании диссертационного совета Д 501.001.44 в Московском государственном университете имени М. В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, ВМиК, ауд. 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ. С текстом автореферата можно ознакомиться на официальном сайте ВМиК МГУ http://cs.msu.ru в разделе "Наука" — "Работа диссертационных советов" - "Д.501.001.44".

Автореферат разослан сентября 2009 г.

I Ученый секретарь / диссертационного совета ^ профессор --р н. П. Трифонов

Общая характеристика работы

Актуальность темы. Понятие алгоритмически вычислимой (рекурсивной) функции является одним из основных в современной математике. Формализация понятия вычислимой функции была выполнена в середине 1930-Х'годов известными математиками: А. Тьюрингом, Э. Постом, А. Чёрчем, С. Клини и др.

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

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

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

Впервые вопрос о порождаемости достаточно широких и содержательно интересных классов рекурсивных функций с помощью одной лишь операции суперпозиции был рассмотрен А. Гжегорчиком в 1953 году1. Базисом по суперпозиции в некотором классе мы будем называть полную относительно суперпозиции систему в этом классе. Традиционно в теории рекурсивных функций не требуют минимальности для таких систем. В этой же известной работе 1953 года А. Гжегорчиком было показано, что класс примитивно рекурсивных функций не имеет конечного базиса по суперпозиции. Кроме того, в той работе была введена иерархия классов £п, п ^ 0,

'Grzegorczyk A. Some classes о/ recursive functions, Rozprawy Mathematyczne, 1953, V. 4, P. 1-46. (Русск. пер.: Гжегорчик А. Некоторые классы рекурсивных функций, Проблемы математической логики, М.: Мир, 1970, С. 9-49.)

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

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

Р. Ричи в 1964 году показал, что классы £п, п ^ 2, могут быть охарактеризованы в терминах сложности вычислений на машинах Тьюринга. В частности, £2 — это множество всех функций, вычислимых с линейным ограничением на зону (от длины записи входа), а £3 — с ограничением, имеющим вид "многоэтажной" экспоненты (с любым фиксированным числом этажей). Поэтому исследование базисов по суперпозиции в этих классах может пролить свет на природу вычислительной сложности.

Поставленная А. Гжегорчиком проблема решалась в несколько этапов. Существование конечного базиса по суперпозиции в классах £п (п ^ 3) было доказано Д. Рёддингом в 1964 году2. Для класса £2 это было доказано С. С. Марченковым в 1969 году3. Основной идеей работы С. С. Марчен-кова было использование так называемых квазиуниверсальных функций, которые определяются на основе нумерации одной разновидности машин Тьюринга. В 1970 году А. А. Мучник4 на основе идей С. С. Марченкова доказал существование базисов в большом семействе классов, определяемых в терминах сложности вычислений на машинах Тьюринга, например, для класса FP функций, вычислимых за полиномиальное время (от длины записи аргументов).

Особый интерес представляет проблема построения "простых" базисов по суперпозиции. Если класс имеет базис простого вида, то вопрос о принадлежности какой-либо функции этому классу сводится к вопросу о представимости этой функции в виде суперпозиции конкретных функций достаточно простого вида. Первым существенным продвижением в этом на-

2Röddmg D. Übe г die Eliminierbarkeit von Definitionssckemata in der Theorie der rekursiven Funktionen, Zeitschr. math. Logik, u. Grundlag. Math., 1964, B. 10, N 4, S. 315-330.

3Марченков С. С. Устранение схем рекурсий в классе £2 Гжегорчико, Математические заметки, 1969, Т. б, N. 5, С. 561-568.

4 Мучник А. А. О двух подходах к классификации рекурсивных функций, Проблемы математической логики, М.: Мир, 1970, С. 123-138.

правлении был результат, полученный С. С. Марченковым в 1980 году5: базисом по суперпозиции в классе £3 является система

{х + 1,

где <р(х, у) равно наименьшему номеру нулевого разряда в представлении числа у в позиционной системе счисления с основанием х. Таким образом, был построен базис, состоящий из простых арифметических функций и одной специальной функции, которая не является арифметической "в чистом виде", но имеет очень короткое определение. В этой же работе С. С. Мар-ченкова было показано, что суперпозициями функций

х + 1, х + у,

можно получить все функции из £3, принимающие конечное число значений. Избавиться от "плохой" функции смог С. Маззанти в 2002 году6. Более точно, он доказал, что

{х + у, х +

х

12/J

, 2х}

— базис по суперпозиции в £г.

Техника, предложенная в этих работах, позволяет строить базисы простого вида в классах, содержащих £3.

Цель диссертации. В диссертации рассматривается проблема построения конечных базисов по суперпозиции в различных классах рекурсивных функций. В работе ставятся и решаются следующие основные задачи:

• описание классов функций, получающихся суперпозициями простых арифметических функций и, возможно, других общеизвестных функций, с различными ограничениями на скорость роста используемых функций и строение формул;

• построение конечных базисов по суперпозиции простого вида в классах, аналогичных классу S2 Гжегорчика, без использования нумераций машин Тьюринга;

5Марченков С. С. Об одном базисе по суперпозиции в классе функций, элементарных по Кальмару, Математические заметки, 1980, Т. 27, N 3, С. 321-332.

eMazzanti S. Plain bases for classes of primitive recursive functions, Mathematical Logic Quarterly, 2002, V. 48, P. 93-104.

• исследование групп перестановок, связанных с известными классами рекурсивных функций, на предмет конечной порождаемое™.

Научная новизна. Все полученные результаты являются новыми.

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

2. Впервые построены базисы по суперпозиции простого вида без использования нумераций машин Тьюринга в классах, существенно меньших, чем £3.

3. Решена (положительно) проблема о конечной порождаемости групп перестановок, связанных с известными классами рекурсивных функций.

Научная и практическая ценность. Работа носит теоретический характер. Результаты и методы работы, по мнению автора, могут быть применены к другим задачам теории рекурсивных функций. Явные базисы по суперпозиции, а также методы, разработанные для их получения, могут быть применены для получения простых эквивалентных определений различных классов рекурсивных функций и сложностных классов. Эти эквивалентные определения могут помочь в исследовании природы этих классов, а также в установлении вычислительной сложности конкретных функций.

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

Методы исследования. В диссертации используются методы теории рекурсивных функций.

Публикации и апробирование. Основные результаты диссертации докладывались на международных конференциях "Дискретные модели

в теории управляющих систем" (Москва, 2006 г.), "Проблемы теоретической кибернетики" (Казань, 2008 г.), научно-исследовательском семинаре кафедры математической кибернетики факультета ВМиК МГУ, научно-исследовательском семинаре кафедры математической логики и теории алгоритмов механико-математического факультета МГУ, научно-исследовательском семинаре института проблем передачи информации, опубликованы в работах [1-5].

Структура и объем работы. Диссертация состоит из введения, трех глав и списка литературы. Объем работы 126 страниц.

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

Пусть N0 = {0,1,2,...}. Рассматриваются всюду определенные функции (произвольного числа аргументов) на множестве N0. Под операцией суперпозиции будем подразумевать подстановку функций в функции, перестановку и отождествление переменных, введение фиктивных переменных.

Пусть <5 — некоторый класс функций на N0. Будем обозначать через [<Э] замыкание по суперпозиции класса ф.

Пусть Ф - некоторое множество функций, замкнутое относительно суперпозиции, иФСФ. Будем говорить, что множество Ф порождает множество Ф, если [Ф] = Ф. Конечные множества, порождающие Ф, будем называть конечными базисами по суперпозиции в множестве Ф.

Положим

Краткое содержание диссертации

х -г у = тах(ж - у, 0),

0, если х > 0,

1, если х — 0,

остатку от деления х на у, если у > 0,

{1, если х > 0, 0 иначе,

гт(ж,у)

0 иначе.

[l°g2z] =

целой части двоичного логарифма х, если х > О, О иначе,

х(у) — у-иу двоичному разряду числа х

00

(таким образом, х = ~^х(у) • 2У).

у=0

Определим функцию х Л у — поразрядную конъюнкцию двоичных представлений чисел х и у. Пусть а„а„_ 1... ао, Ь„Ьп-1... Ьо — двоичные представления чисел х и у (если длины двоичных представлений различны, то старшие разряды двоичного представления меньшего числа равны нулю). Тогда двоичное представление числа х А у есть

Характеристической функцией предиката р{хх,..., хп) будем называть функцию Хр(х1, ■ ■ ■, хп) такую, что при любых Хх,..., хп

Для класса функций <5 через будем обозначать множество всех предикатов, характеристические функции которых лежат в С).

Будем говорить, что функция ..., хп, у) получена из функций 0(2:1, ■ ■ •, хп), Цх 1, ...,хп,у, г), ](хи ...,хп,у) с помощью операции ограниченной рекурсии, если выполняются соотношения

{/(хи ...,хп, 0) = д(хи ...,хп),

/(®1, .. . , Х„, У + 1) = Л(хь ...,Хп,у, ¡{XI, ...,хп, у)), /(хь ...,х„,у) ^Цхь ...,х„, у).

Определим классы £п (п 6 N0) иерархии Гжегорчика1. £п есть минимальный класс функций, содержащий функции х+1, [п(х, у) и замкнутый относительно суперпозиции и ограниченной рекурсии, где

7Grzegorczyk A. Some classes of recursive functions, Rozprawy Mathematyczne, 1953, V. 4, P. 1-46. (Русск. пер,: Гжегорчик А. Некоторые классы рекурсивных функций, Проблемы математической логики, М.: Мир, 1970, С. 9-49.)

(fln ■ bn)(an-i ■ 6„_0... (о0 • Ьо).

Хр(х 1, ■ • ■ ! %п) —

1, если р{х 1,... ,хп) истинно, О иначе.

/о(я, У) = У + 1, f1(x,y) = x + y, f2{x,y) = {x + l)-{y + l),

при

/n+i(0, у) = fniy + 1,2/+ 1),

/n+l(® +1)2/) = fn+i(x, f„+\(x,y)).

Для векторов из переменных (и их частей) будут использоваться сокращенные обозначения вида х, у и т. п. (например, (х,Ь) вместо {х\ ,...,£„, ¿)).

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

В разделе 1.1 описывается класс функций, представимых формулами с экспонентами высоты не более 2.

Будем говорить, что функция /(я, г\,... ,гп) получается из функции д(у, 21,..., гп) с помощью операции ограниченного суммирования по переменной у, если

Класс 8 функций, элементарных по Сколему 8 — это минимальный класс функций, содержащий функции

и замкнутый относительно суперпозиции и ограниченного суммирования. Отметим, что Б совпадает с минимальным классом, содержащим функции (1) и замкнутым относительно суперпозиции и суммирования вида "%2х<у (сумма по пустому множеству равна нулю), для удобства мы будем использовать именно это определение.

Для каждого множества функций <5 по индукции определим последовательности классов и [<5]"„ (п = 0,1,2,...).

8Skolem Th. A theorem on recursively enumerable sets, Abstract of short comm. Int. Congress Math., 1962, Stockholm, P. 11.

0, x+1, x + y

(1)

i. [Qt = [Qt = IQ\-

2. Если / е МЪ {[Я\1), то /е \Q\li1 ([С„+1)_

3. Если / е (/ е [<Э]"„) и ^ получается из / перестановкой или отождествлением переменных, а также введением фиктивных переменных, то д е (д е [<?]"„).

4. Если /(у1,...,ут) е я и ..., дт(хи...,хк) € [<?]£* (Ж), то

е (Ж)-

5. Если / 6 Ж1, 5 е , Л е Щ ,то 2"е т?1 и /' € Ж1.

Для [ф]^ и будем использовать сокращенные обозначения [<5]г* и [<5]хи соответственно.

Индуктивно определим последовательность классов Рп (п — 0,1,2,...).

1. Р° - класс всех полиномов с коэффициентами из N0.

2. Р"+1 есть класс всех функций вида 2^, где / е Р".

Определим класс ХЭ" (п = 0,1,2,...) как класс всех функций /(®1,..., х„), для которых выполнены следующие два условия:

1. / ограничена некоторой функцией из Рп+1.

2. Существуют функции т{х\, ...,г„)еР„ и д(х\,...,хп,у,г) € Б такие, что

/(хи ...,х„) (у) = р(гь ...,хп,у, т(х ь..., я„)).

ХБ определим как класс всех функций /(жь...,хп), для которых выполнены следующие два условия:

1. Существует полином р(х 1,... ,хп) с натуральными коэффициентами такой, что для любых х\,...,хп справедливо неравенство

2. /{хи...,хп)(у)е8. Положим

Т = {ж + 1, ху, х-~у, хЛу, [х/у]}.

Теорема 1. ХЭ = [Т]2, = [Т]х„.

Отметим, что теорема 1 является первым результатом, описывающим классы рекурсивных функций, получающихся с помощью суперпозиции с ограничением на строение формул.

В разделе 1.2 описан класс функций, получающихся суперпозициями функций простого вида со следующим ограничением на скорость роста: длина записи значения функции ограничена полиномом от длин записей аргументов. Класс описан в терминах выразимости в логике первого порядка.

Если А — некоторый алфавит, то будем обозначать А+ множество всех конечных непустых слов в алфавите А. Если X — некоторое слово в алфавите А, то будем обозначать \Х\ длину этого слова.

Назовем РОМ-термом над переменными ц,..., хт любое выражение вида ..., хт, 1, \Х\ (подраузмевается, что такого рода выражениям соответствуют функции, которые зависят еще и от словарной переменной X, но мы это не будем указывать явно; см. ниже).

Определение. Элементарными РОМ -формулами над переменными х1,...,хт называются выражения вида (¿1 < ¿г), В1Т(^,¿г) или Х(^), где ¿х, ¿2 — РОМ-термы над переменными , хт.

Определим индуктивно понятие РОМ-формулы над переменными

XI,... , Хт-

1. Все элементарные РОМ-формулы над х\,...,хт являются РОМ-формулами над х\,..., хт.

2. Если <£>1, Фг — РОМ-формулы над переменными х1,...,хт, Х{ € {хи...,хт}, то (Ф1&Ф2), (ФхУФа), Н>1), (Эх4)(Ф1), (Ма^ХФ!) являются РОМ-формулами над х1,...,хт.

Каждому РОМ-терму £ над переменными х\,...,хт следующим образом сопоставим функцию Н^Х, Х\,...,хт), определенную на множестве всех наборов (Х,х\,... ,хт) таких, что X е {0,1}+ и 1 ^ Х1,...,хт <

1. Если I есть 1, то

Ы(Х,Х\,.. .,хт) = 1.

2. Если £ есть то

^(Х,х\,...,хт) = \Х\.

3. Если t есть х^ то

Ы(Х,хи.. -,хт) = Х{.

Каждой элементарной РОМ-формуле Ф над переменными х\,... ,хт следующим образом сопоставим предикат р$(Х,Х\,. ■ ■,хт), область определения которого совпадает с областью определения функций РОМ-термов над XI,...,хт.

1. Если Ф имеет вид (¿1 < ¿2)1 то

Рф(Х,хи...,хт) = {Нн(Х,хи. ,.,хт) ^ 1цг{Х,х\,... ,хт)).

2. Если Ф имеет вид ВЩ^г), то

Рф(Х,Х1,...,Хт) = (Х,Х1,..., Хт) {Лг2 {X, XI,..., Хт) - 1) = 1) ■

3. Если Ф имеет вид Х(^), то

р${Х, а?!,..., Хт) = (Ы^Х,Х\,...,жт)-й символ слова X равен 1),

где нумерация символов начинается с единицы (и символы нумеруются слева направо).

Каждой РОМ-формуле Ф над переменными х\,...,хт следующим образом сопоставим предикат рф{Х,х\,..., хт), область определения которого совпадает с областью определения функций РОМ-термов над Х\,..., хт.

1. Если формула является элементарной РОМ-формулой, то соответствующий ей предикат совпадает с предикатом, определенным для данной элементарной формулы.

2. Если Ф имеет вид (Ф1&Ф2), то

Рф{Х, Х\,.. . , Хт) = Рф1 {Х,Х1,..., хт) &РФ1 (Х,хх,...,хт).

3. Если Ф имеет вид (Ф! V Фг), то

Рф(Х, XI,..., Хт) = РФ^Х, XI,... , Хт) V РФ2(Х, XI,..., хт).

4. Если Ф имеет вид (-1Ф1), то

рф{Х,Х\,...,Хт) = -прфДХ,^!,. .. ,хт).

5. Если Ф имеет вид (Эж,)(Ф1), то

Рф(Х, х\,...,хт) = (Зх)(1^<|х|)Рф1(Х, Х[,..., х^г, х, ..., хт).

6. Если Ф имеет вид (Vx,)(Ф1), то

Рф(Х, xi,..., хт) = (Ух)(1<х<1х\)Рф1(Х, Xi, ... , ^i—l, X, ®f+l) • • • 1 -Ern)-

7. Если Ф имеет вид (Мж,-)(Ф1), то р$(Х,хi,...,xm) истинно тогда и только тогда, когда количество х таких, что 1 < х < и р^(Х, a?i,..., Xi-i,x, Xi+i,..., Хт) истинно, больше, чем \Х\/2.

Клехс FOM (от англ. First Order with Majority9) определим как множество всех всюду определенных на множестве {0,1}+ предикатов <р(Х), для которых существует FOM -формула, которой соответствует предикат р(Х,Xi,..., Хт) такой, что при любых X, xi,..., хт из его области определения

ip{X) = p{X,xx,...,xm).

Вообще говоря, класс FOM можно назвать "очень маленьким". Все предикаты из из ТОМ вычислимы за полиномиальное время (и, более того, с логарифмической зоной).

Если х\,...,хт — натуральные числа, то будем обозначать CODE(a;i,..., хт) слово

01si01s201... 01sm01,

где

пустому слову, если х\ = О,

слову, получающемуся из двоичной записи х.

Si =

заменой каждой единицы на 11, а каждого нуля на 00, если Xi ф 0.

Класс FOM^ определим как множество всех всюду определенных на множестве No предикатов <р(х\,..., я„), для которых существует предикат чр(Х) € FOM такой, что при любых х\,...,хп выполнено

<р( xh ...,хп) = ф{ CODEfo,..., хп)).

Класс FFOM определим как множество всех всюду определенных на множестве No функций f(x\, ...,хп) таких, что выполняются следующие два условия.

1. Существует полином р(у\,...,уп) такой, что при любых • • • I Хп f(x 1, ,х„) <

'Barrington D.A.M., Immerman N., Straubing H. On uniformity within NC1, Journal of Computer and System Sciences, 1990, V. 41, P. 274-306.

2. Предикат р, определяемый соотношением

р(хи ...,хп,у) = (/(жь • • •, хп)(у) = 1), лежит в РОМ^.

Класс ГРОМ можно назвать функциональным аналогом класса РОМ (аналогично тому, что иногда рассматривают класс полиномиально вычислимых предикатов, а иногда — функций). Класс ЕРОМ, не смотря на свою "малость", содержит большинство встречающихся на практике эффективно вычислимых функций, подходящих по скорости роста.

Теорема 2. Имеет место

РРОМ-

х + у, х + у, хА у, [х/у], =

х + у, х + у, х А у, [х/у], ^ .

Эта теорема является первым результатом, в котором построен "явный" базис, состоящий из общеизвестных функций, для достаточно естественного класса рекурсивных функций (который с некоторыми оговорками можно назвать сложностным), существенно меньшего, чем К.

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

Определим класс ГРОМ" (п = 1,2,...) как класс всех ограниченных сверху функциями из Р" функций ¡(хх, ...,хп), для которых существуют функция т(х 1,..., хп) € Р" и предикат р(х х, ...,хп,у,г) € ¥ОМ^ такие, что

(/(жь ...,хп) (у) = 1) = р{хь ...,х п,у, ш(жь..., хп))■ Теорема 3. При любом п > 0 имеет место

ХБ" = [Г]£+1 = \Т]п+1 = РРОМп+1.

Эта теорема является обобщением теоремы 1.

В главе 2 построен явный базис в классе £2 иерархии Гжегорчика. Напомним, что этот класс может быть охарактеризован как множество всех функций, вычислимых на машине Тьюринга с линейным ограничением на

зону (от длины входа). В построенном базисе не используется в явном виде нумерация какой-либо разновидности машин Тьюринга. Базис состоит из простых арифметических функций и функции <д(х, р\, р2, С\, С2, Ь), определенной с помощью примитивной рекурсии. Функция С} в известном смысле является квазиуниверсальной в £2.

Определим И(х, у) как циклический сдвиг двоичного представления числа х на у разрядов вправо. Иными словами, пусть Я(0, у) — О, У) — а если 1 ) 2 и апа„-1... а^о - двоичное представление х, причем а„ — 1, то двоичная запись Я(х, у) есть

0>п+у0"п+у-1 • • • +у&у)

где все сложения проводятся по модулю п 4-1.

Определим функцию (¿(х, рх, рг, с2, £) следующей примитивной рекурсией:

Р1, Р2, Си с2, 0) = X, <Э(я, РиР2, Си С2, ¿ + 1) = _ (с](х, Ри Р2, Си С2, ¿), если С}{х, Ри Р2, Си 02, А Я(ръ С1-г)Ф О, ри Р2, Си с2, + Д(р2, с2 ■ г) в противном случае.

Поскольку <5(ж, р1, рг, Сх, с2, ¿) ^ х+2р2^, то имеем ограниченную рекурсию в классе £2 и, таким образом, <5 £ £2.

Функцию д(жь ж2) - ят) из класса £2 будем называть квазиуниверсальной в классе £2 относительно системы функций Ф, если для любой функции /(у) из класса £2 найдутся функции М®. У)> 51 (у)> 52(у), • • •, 5т(у) из множества Ф, такие, что

/(у) = ЧЯЫу)> $а(у)> • • • 1 5т(у)).у)-

Теорема 4. Функция (¿(х, р\, р2, й, с2, ¿) является квазиуниверсалъной в классе £2 относительно замыкания по суперпозиции системы функций

х + 1, ху, тт(а;, 2"), жЧ-у, Следствие. Система функций

х

L2/J

[log2 х].

х + 1, ху, min(a;, 2У), х + у,

[log2 х], Q(x, ри Р2, си с2, t)

образует базис по суперпозиции в классе £2 Гжегорчика.

Теорема 4 и следствие из нее в качественном отношении существенно усиливают результаты С. С. Марченкова10 и А. А. Мучника11.

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

Под термином перестановка будет подразумеваться перестановка на множестве No.

Для любого класса Q, замкнутого относительно суперпозиции и содержащего функцию 1{х) — х, через Gr(Q) обозначим группу перестановок ({/: fJ-'eQ}, о).

Определение. Бесконечное множество А С No называется регулярным в классе функций Q, если выполняются условия:

1- ХА е Q;

2. Можно так занумеровать элементы множества А, что функция ß(x), вычисляющая номер элемента х в этой нумерации (равна нулю при х ^ Л), и функция v(x), вычисляющая элемент с номером х, принадлежат Q (нумерация начинается с нуля).

Будем рассматривать классы функций Q, удовлетворяющие требованиям:

I. Q содержит функции

1, х + у, х + у, X-Sgy, [ж/2]; (2)

II. Q содержит нумерационную функцию сг^ъ £2), взаимно-однозначно отображающую множество Ng на No, и обратные к ней функции с2д(ж) и с2,2(ж) (с2д(с2(а;,у)) = х, с2,2(02(2,2/)) = у при любых х, У)\

III. Для любой перестановки / б Gr(Q) существуют непересекающиеся регулярные в Q множества А, В такие, что f(A) П В = 0 и No\A, No\ß регулярны в Q\

10Марченков С. С. Устранение схем рекурсий в классе £2 Гокегорчика, Математические заметки, 1969, Т. 5, N. 5, С. 561-568,

"Мучник А. А. О двух подходах к классификации рекурсивных функций, Проблемы математической логики, М.: Мир, 1970, С. 123-138.

IV. <3 имеет конечный базис по суперпозиции.

Теорема 5. Если класс <5 удовлетворяет требованиям I—IV, то существуют две перестановки из Сг(С}), композициями которых можно представить любую перестановку из Сг(ф).

Пусть РР — множество всех функций Мд —» N0, вычислимых на машине Тьюринга за полиномиальное время от длины входа (числа представляются в двоичном виде). Аналогично, И. — множество всех функций, вычислимых с зоной п), где п — длина входа (на многоленточных машинах Тьюринга, не записывающих на входную ленту).

Класс функций ф называется £2 -замкнутым, если он содержит функции

О, я + 1, ху

и замкнут относительно суперпозиции и ограниченной рекурсии.

Теорема 6. Классы РР, РЬ, РРОМ, а также все £2-замкнутые классы, имеющие конечный базис по суперпозиции, удовлетворяют требованиям I—IV.

Теоремы 5, 6 представляют собой решение проблемы, которая неоднократно формулировалась в 1970-80 гг.12

Основные результаты диссертации

1. Описаны классы функций, представимых формулами заданной высоты над простыми арифметическими функциями с экспонентой и одной функцией, являющейся стандартной во многих языках программирования. Эти классы описаны в терминах выразимости в логике первого порядка, а также в терминах порождения функций на основе суперпозиции и ограниченного суммирования.

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

12Марченков С. С. Базисы по суперпозиции в классах рекурсивных функций, Математические вопросы кибернетики, М.: Наука, 1991, вып. 3, С. 115-139.

3. Построен базис по суперпозиции простого вида в классе £2 иерархии Гжегорчика, в котором не используется в явном виде нумерация машин Тьюринга. Кроме того, приведен пример квазиуниверсальной функции простого вида в этом классе.

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

Публикации по теме диссертации

[1] Волков С. А. Конечная порождаемость некоторых групп рекурсивных перестановок // Дискретная математика. — 2008. — Т. 20, вып. 4. — С. 61-78.

[2] Волков С. А. Конечная порождаемость некоторых групп рекурсивных перестановок // Проблемы теоретической кибернетики. Тезисы конференции. — Казань, 2008. — С. 15.

[3] Волков С. А. Порождение некоторых классов рекурсивных функций суперпозициями простых арифметических функций // Доклады Академии наук. - 2007. - Т. 415, N. 4. - С. 43&-440.

[4] Волков С. А. Пример простой квазиуниверсальной функции в классе £2 иерархии Гжегорчика // Дискретная математика . — 2006. — Т. 18, вып. 4. - С. 31-44.

[5] Волков С. А. Экспоненциальное расширение класса функций, элементарных по Сколему, и ограниченные суперпозиции простых арифметических функций // Математические вопросы кибернетики. М.: Физмат-лит, 2007. - вып. 16. - С. 163-190.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 02.09.2009 г. Формат 60x901/16. Усл.печ.л. 1,0. Тираж 70 экз. Заказ 451. Тел. 939-3890. Тел./факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

Введение

1. Краткий обзор результатов по теме диссертации.

1.1. Классификации рекурсивных функций.

1.2. Конечные базисы по суперпозиции.

2. Общая характеристика работы.

3. Формулировка основных результатов

3.1. Основные определения.

3.2. Основные результаты главы 1.

3.3. Основные результаты главы 2.

3.4. Основные результаты главы 3.

1. Порождение некоторых классов суперпозициями простых арифметических функций

1. Экспоненциальное расширение класса функций, элементарных по Сколему, и формулы высоты два

1.1. Определения.

1.2. Включение [Т]хУ С XS.

1.3. Классы ВА#, ВА^ и Т- полиномиальность.

1.4. Включение XS С [Т]2Х.

1.5. Доказательство теоремы 1.

2. Базис по суперпозиции в FFOM.

2.1. Определения.

2.2. Совпадение классов FFOM, FFOMalt и FFOMvar

2.3. Принадлежность некоторых функций классу [Т"]

2.4. Правильность предикатов, соответствующих FOM-формулам.

2.5. Доказательство теоремы 2.

3. Иерархии классов, исчерпывающие класс функций, элементарных по Кальмару, и формулы произвольной высоты

3.1. Определения.

3.2. Совпадение классов XSn и XS+.

3.3. Доказательство теоремы 3.

2. Простой базис по суперпозиции в классе £2 иерархии Гже-горчика

1. Машины Минского.

2. Вектор-функции, конфигурации и их коды.

3. Основное свойство функции Q.

4. Доказательство теоремы 4.

3. Конечная порождаемость некоторых групп рекурсивных перестановок

1. Определения.

2. Конечная порождаемость группы Gr(Q)

3. Порождаемость группы Gr(Q) двумя перестановками

4. Конечная порождаемость группы Gr(Q) для конкретных классов Q.

1. Краткий обзор результатов по теме диссертации 1.1. Классификации рекурсивных функций

Понятие алгоритмически вычислимой (рекурсивной) функции является одним из основных в современной математике. Формализация понятия вычислимой функции была выполнена в середине 1930-х годов известными математиками: А. Тьюрингом [30], Э. Постом [25], А. Чёрчем [17], С. Кли-ни [22] и др. Для каждой из этих формализация существует тезис (тезис Чёрча-Тьюринга), который утверждает, что класс всех алгоритмически вычислимых функций совпадает с классом функций, вычислимых в данной формализации.

Существуют разные подходы к формализации понятия вычислимой функции. Однако всегда пользуются предпочтением наиболее простые формализации. Самым известным является подход, основанный на использовании моделей различных механических устройств, таких, как машина Тьюринга [30, 25].

Другой подход основан на порождении функций на основе базового набора функций и некоторых порождающих операций. С. Клини в своей работе [22] ввел понятие частично рекурсивной функции. Частично рекурсивная функция — это частично определенная функция / : Nq —> No, которую можно получить из исходных функций 0, ж+1 с помощью конечного числа применений операций суперпозиции (суперпозиция включает подстановку функций в функции, перестановку и отождествление переменных, введение фиктивных переменных), примитивной рекурсии и минимизации.

Заметим, что класс всех вычислимых функций не является адекватной формализацией понятия вычислимости на практике. Например, функция

Дп, x), определяемая соотношениями

ДО, а?) = ж+ 2,

Дп + 1,0) = 1, (1) п + 1,ж + 1) = /(п,/(га + 1,ж)), является вычислимой, но растет она настолько быстро, что даже значение /(10,10) вычислить на практике нереально. Кроме того, нет способа для произвольной вычислимой функции и набора входных значений заранее предсказать, сколько времени потребуется для вычисления значения данной функции на данном наборе (и оценить сверху объем ресурсов, которые будут затрачены на вычисление). Более того, не все вычислимые функции всюду определены (вычислимая функция не определена на тех наборах, на которых вычисляющий алгоритм не выдает ответ за конечное время).

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

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

Примером подобного класса является класс примитивно рекурсивных функций (см. [3]). Говорят, что функция f{x,y) получается из функций д(х) и h(x,y, z) с помощью операции примитивной рекурсии, если выполняются соотношения:

Г /(^,0) = д(х), №y + l) = h(xiyj(xiy)). 1 ;

Функция называется примитивно рекурсивной, если ее можно получить из функций 0, х + 1 с помощью операций суперпозиции и примитивной рекурсии. Класс примитивно рекурсивных функций содержит практически все всюду определенные функции (на No), используемые в математической практике. Этот класс можно описать и в терминах сложности машинных вычислений: всюду определенная функция д(х\,., Хк) примитивно рекурсивна тогда и только тогда, когда она вычислима на машине Тьюринга с ограничением на время вида /(п, #! + . + Хк) для некоторого п, где / определяется соотношениями (1) (см. [26, 12]).

Другим примером является класс функций К, элементарных по Кальмару [21]. Класс К есть множество всех функций, которые можно получить из функций х + 1, х + у (3) с помощью операций суперпозиции, ограниченного суммирования вида Ylx^y и ограниченного умножения вида Па^у (3Десь и далее х у = max(0, х — у)). Все функции из класса К являются примитивно рекурсивными, однако обратное неверно (см. [21]). В терминах машинных вычислений класс К является классом всех функций д(хi,., хп), вычислимых на машинах Тьюринга с ограничением на время вида hk{%\ + • • • + хп) при некотором к, где h0{x) = x, hk+1(x) = 2hk(-x\ аналогичное утверждение справедливо и для ограничения на зону (см. [26]). Есть и другие эквивалентные определения класса К. Например, f(x 1,., хп) G К тогда и только тогда, когда существуют такие к Е No и полиномы Р(х, у, z), Q(x, у, z) с коэффициентами из No, что f(x) ^ т(х) и

У = /(£)) = (3zi)Zl<mi2). (3zi)Zl<m^){P(x,у, z) = Q(x,у, z)), где т(х 1,., хп) = hk(xi + . + хп) (см. [1]).

В работе [19] А. Гжегорчик определил иерархию классов €п, п € No. Говорят, что f{x,y) получается из функций д(х) и h(x,y,z), j(x,y) с помощью операции ограниченной рекурсии, если выполняются соотношения (2) и

Л®,2/)

8п есть минимальный класс функций, содержащий функции х+1, fn(x,y) и замкнутый относительно суперпозиции и ограниченной рекурсии, где о(х,у) = у + 1, fi(x,y) = х + у, /2{х1у) = (х + 1)-(у + 1)1 при п > 2 fn+i(0,y) = fn(y + 1,2/ + 1), п+1(ж + 1,2/) = /n+i(a?,/n+i(a?,y)).

Иерархия Гжегорчика строго монотонна и исчерпывает класс примитивно-рекурсивных функций. Кроме того, £3 = К (это доказано в [19]). Для классов £п, п > 2, существует описание в терминах сложности вычислений на машинах Тьюринга. Например, £2 — это множество всех функций, которые вычислимы на машинах Тьюринга с линейной зоной (от длины входа; числа представляются в двоичном виде), см. [26].

Еще одним классом, который заслуживает внимания, является введенный Т. Сколемом в [28, 29] класс элементарных функций ("lower elementary functions"). Этот класс мы будем обозначать S и называть классом функций, элементарных по Сколему. S есть минимальный класс, содержащий функции (3) и замкнутый относительно суперпозиции и ограниченного суммирования вида • Для этого класса не известно какого-либо описания на основе сложности машинных вычислений. Известно, что S С но вопрос о совпадении этих классов на данный момент открыт (см. [10]). Кроме того, известно, что S содержит NP-трудные функции (см. доказательство для другого класса в [31], связь с классом S в [10]).

Рассмотренные классы отличаются по скорости роста входящих в них функций. Например, все функции классов £2 и S ограничены полиномами, а £3 содержит функции экспоненциального роста. Чтобы выделить вычислительную сложность функций "в чистом виде", для каждого класса Q рассматривают множество Q* всех предикатов с характеристическими функциями из Q (характеристической функцией предиката называется функция, равная 1 на всех наборах, на которых значение предиката истинно, и равная 0 на всех остальных наборах). Известно [19], что иерархия п > 2 строго монотонна. Кроме того, известно [5], что

S* С

Вопрос о том, какие из классов S*, , , совпадают, а какие нет, на данный момент открыт.

Отметим еще, что часто в качестве приближения класса практически вычислимых функций рассматривают класс FP функций, вычислимых на машине Тьюринга за полиномиальное время (от длины записи входа). Класс FP тоже имеет эквивалентные функциональные определения (см. [16, 15]). Они немного более сложны, чем приведенные выше для других классов, поэтому мы не будем их здесь приводить.

1.21 Конечные базисы по суперпозиции

Впервые вопрос о порождаемости достаточно широких и содержательно интересных классов рекурсивных функций с помощью одной лишь операции суперпозиции был рассмотрен А. Гжегорчиком в 1953 году в работе [19]. Базисом по суперпозиции в некотором классе мы будем называть полную относительно суперпозиции систему в этом классе. Традиционно в теории рекурсивных функций не требуют минимальности для таких систем. В [19] было показано, что класс примитивно рекурсивных функций не имеет конечного базиса по суперпозиции. В этой же работе был поставлен вопрос о существовании таких базисов в классах Еп.

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

Поставленная А. Гжегорчиком проблема решалась в несколько этапов. Существование конечных базисов по суперпозиции в классах £п (п ^ 3) было доказано Д. Рёддингом в 1964 году в работе [27]. Доказательство Д. Рёддинга было настолько громоздко, что базисы даже не были выписаны в явном виде. В 1968 году в работе [24] Ч. Парсонсом были получены более простые базисы по суперпозиции в классах 8п (п ^ 3). Ч. Парсонс в явном виде выписал систему из 19 функций, которая является базисом по суперпозиции в 83. Рёддинг и Парсонс использовали для построения своих базисов метод, который мы будем называть методом производящих функций. Суть этого метода в том, что для функций строятся производящие функции, т.е. функции, каждое значение которых содержит информацию о начальном отрезке значений исходной функции. Например, для функции f(x) производящей можно назвать функцию д(х) = ПрР, где рг — г-е простое число. Если функции получаются из других с помощью ограниченной рекурсии, суммирования и т.п., то соответствующие им производящие функции можно получать из производящих исходных функций с помощью одной лишь суперпозиции (при наличии некоторого набора вспомогательных функций). Для применения метода производящих функций необходимо наличие в классе функций как минимум экспоненциального роста. Все функции классов 8°, 81, 82 ограничены полиномами, поэтому для них метод производящих функций не работает.

Для класса 82 трудности с построением базиса были преодолены в 1969 году С. С. Марченковым в работе [9] (см. также [6]). В этой работе был применен метод, основанный на моделировании одной разновидности машин Тьюринга. Важную роль при построении базисов с использованием "машинного" метода играют нумерационные функции (функции, нумерующие числовые векторы). Все функции классов 8° и 81 ограничены сверху линейными функциями, поэтому не содержат нумерационных функций. Вопрос о существовании базисов в 8° и 81 на данный момент открыт. Также открытым является вопрос о существовании базисов в S (в нем есть нумерационные функции, но "машинный" метод для него не работает по другим причинам).

В 1970 году в работе [12] А. А. Мучником на основе идей С. С. Мар-ченкова [9] был предложен достаточно простой метод построения базисов по суперпозиции в некоторых классах рекурсивных функций. Этот метод основан на использовании специальных функций (которые были названы квазиуниверсальными), основанных на нумерации машин Тьюринга. В этой же работе доказано существование базисов в целом семействе классов, определяемых на основе сложности вычислений на машинах Тьюринга, а также на основе результатов [26] получено альтернативное доказательство существования конечных базисов в £п, п ^ 2.

Особый интерес представляет проблема построения базисов как можно более простого вида. В этом направлении было получено достаточно много интересных результатов. Первым существенным продвижением в этом направлении был результат [7], полученный С. С. Марченковым в 1980 году: базисом по суйерпозиции в классе К является система ху, <р{х,у)}: где <р{х,у) при х > 1 равно наименьшему номеру нулевого разряда в представлении числа у в позиционной системе счисления с основанием х, при х < 1 равно нулю. В этой же работе было показано, что суперпозициями функций ж + 1, х + У, х У J х* можно получить все функции из К, принимающие конечное число значений. В 1989 году работе [8] доказано, что базисом в классе К является х + 1,

2 о-МЬ где а(х) — число единиц в двоичном представлении х. Отметим, что во всех перечисленных выше базисах в классе К кроме стандартных арифметических функций содержится одна "плохая" функция, которая хотя и имеет очень простой вид, но не является в чистом виде арифметической. Избавиться от "плохой" функции смог С. Маззанти в 2002 году в работе [23]. В этой работе было доказано, что х + у, х~у, — базис по суперпозиции в классе К. х

1У\

В качестве примера применения сформулированных выше результатов приведем формулу для биномиального коэффициента:

2x+l.

2X+1 +1)®"

2(х+1 )у 2(*+i)(y+i)

2. Общая характеристика работы

Целями данной диссертации являются:

• описание классов функций, получающихся суперпозициями простых арифметических функций, с различными ограничениями на скорость роста используемых функций и строение формул;

• построение конечных базисов по суперпозиции простого вида в классах, аналогичных классу S2 Гжегорчика, без использования нумераций машин Тьюринга;

• исследование групп рекурсивных перестановок, связанных с известными классами рекурсивных функций, на предмет конечной порождаемое™.

Результаты [7, 8, 23] о базисах в классе К, не смотря на всю свою красоту, простоту и удивительность, обладают существенным недостатком: они не применимы на практике в связи с тем, что класс К содержит функции очень высокой вычислительной сложности (например, xyZ) и поэтому является очень плохим приближением для класса функций, "вычислимых на практике". Техника, предложенная в этих работах, существенно использует функции суперэкспоненциального роста, поэтому не позволяет получить аналогичные результаты для классов, существенно меньших, чем К.

Техника из работ [6, 9, 12] позволяет строить базисы в более узких слож-ностных классах, чем К (таких, как, например, £2 или FP), но эти базисы получаются достаточно громоздкими (одна из функций базиса определяется на основе нумерации некоторых типов машин Тьюринга). Никаких способов получения более простых базисов в подобных классах известно не было. Более того, выдвигалась гипотеза, что существенно более простыми, чем построенные на основе нумерации машин Тьюринга, они быть не могут.

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

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

Рассмотрим класс S. Все функции этого класса вычислимы за экспоненциальное время с линейной памятью (от длины записи входа), поэтому S гораздо лучше приближает класс практически вычислимых функций, чем К. Вопрос о существовании конечного базиса в S остается открытым, но, тем не менее, удалось получить описание этого класса в терминах суперпозиции. В разделе 1 главы 1 введен класс XS. Все функции этого класса ограничены функциями вида 2Р^ , где р — полином. S совпадает с множеством всех функций из XS , ограниченных полиномами, поэтому мы будем называть XS экспоненциальным расширением S. Класс XS не замкнут относительно суперпозиции (поэтому базиса в нем быть не может). Тем не менее, этот класс получается достаточно естественным и имеет много эквивалентных определений. Основным результатом раздела 1 главы 1 является то, что XS есть множество всех функций, представимых суперпозициями функций ж + 1, ху, х + у, хЛу, [х/у], 2х, где х А у — поразрядная конъюнкция двоичных представлений х и у, со следующим ограничением на формулы: формула должна иметь высоту не более, чем 2. Высота формулы считается по отношению к экспоненте, т.е., например, высота формулы x2x+yz + 2* равна 2, а у формулы 22* она равна 3.

В разделе 2 главы 1 рассматривается класс FFOM, являющийся функциональным аналогом класса FOM (от англ. First Order with Majority, см. [14]). Класс FOM определяется на основе представления словарных предикатов логическими формулами первого порядка с обобщенными кванторами мажорирования. Все функции из FFOM ограничены функциями вида , т.е. для любой функции f(x) е FFOM длина записи f(x) ограничена полиномом от длины записи х. Вообще говоря, классы FOM и FFOM можно назвать "очень маленькими". Все функции из FFOM вычислимы за полиномиальное время (и, более того, с логарифмической зоной, см. [14]). Тем не менее, FFOM содержит большинство встречающихся в математической практике эффективно вычислимых функций, подходящих по скорости роста. Кроме того, FFOM обладает свойством вычислительной полноты, в частности, все рекурсивно перечислимые множества перечислимы функциями из FFOM (см., например, [14]), FFOM можно рассматривать как "обобщенный" сложностной класс. Основным результатом раздела 2 главы 1 является то, что система функций х + у, х + у, хАу, [х/у], 2^°ё2 ж'2} базис по суперпозиции в FFOM. Отметим, что FFOM-сводимость является достаточно сильной (см. [13, 14]). Анализ доказательств из [2, 18] показывает, что большинство известных NP -полных, PSPACE-полных, а также Р-полных (относительно, например, сводимости с логарифмической зоной) задач являются таковыми и относительно FFOM-сводимости1. Это означает, что полученный в разделе 2 главы 1 результат можно использовать для построения базисов простого вида во многих известных классах. Например, для построения базиса в FP достаточно добавить к базису в FFOM любую FP-полную функцию относительно FFOM-сводимости, которые легко строятся, например, на основе Р-полных задач из [18].

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

Известно, что FOM Ф PSPACE, но вопрос о совпадении классов FOM и NP на данный момент является открытым. класс). В разделе 3 рассматриваются эквивалентные определения классов этой иерархии, основанные на подстановке в функции классов S и FOM монотонных функций с соответствующими скоростями роста.

Отметим, что во всех базисах, описанных в главе 1, присутствует функция х Л у — порязрядная конъюнкция, не являющаяся "в чистом виде арифметической" (хотя и входит в набор стандартных арифметических функций большинства языков программирования и процессоров). К сожалению, избавиться от этой функции аналогично тому, как было сделано в [23] для класса К, пока не удается.

Основной задачей главы 2 является построение базиса простого вида в классе Е2 иерархии Гжегорчика [19]. Можно заметить (см. [13, 14]), что функции простого вида, ограниченные полиномами, аналогичные тем, что были использованы для построения базисов, в главе 1 (например, [у/х\, [loga- у], mm(x,yz): различные несложные операции с двоичной записью или другими формами представления и т.п.), лежат в FFOM и, следовательно, вычислимы с логарифмической зоной, т.е. лежат в \JCuc2 FSPACE(Ci logn + С2), где FSPACE(/(п)) - множество всех функций, вычислимых многоленточными машинами Тьюринга, не записывающими на входную ленту и не читающими с выходной, с ограничением на зону f(n), п — длина входа (см. [14, 20]). С другой стороны, из эквивалентного определения Е2 в [26] и теоремы об иерархии [20] следует, что если Ф — базис в Е2 и /(п) = о(п), то в Ф есть функция, не лежащая в FSPACE(/(n)). Это означает, что базис в Е2 обязан содержать функцию, существенно более сложную, чем рассмотренные выше "простые арифметические". В главе 2 приводится пример базиса, состоящего из простых арифметических функций и специальной функции Q(x,pi,p2, Ci, С2, t). Функция Q определяется на основе примитивной рекурсии, ее определение имеет очень простой вид и не содержит в явном виде какой-либо нумерации машин Тьюринга. Функция Q в некотором смысле является квазиуниверсальной в Е2 (определение квазиуниверсальности немного отличается от введенного А. А. Мучником в [12]). Отметим, что функция Q интересна еще и как очень простой пример PSPACE-эквивалентной функции (см. [2]).

В главе 3 исследуются специфические классы функций — классы перестановок. Более точно, рассматриваются группы перестановок Gr(Q) = {/ : fi f~l £ Q} Для классов Q, замкнутых относительно суперпозиции и содержащих тождественную функцию. Основным результатом главы 3 является доказательство конечной порождаемости Gr((Q) для большого семейства классов Q (удовлетворяющих определенным требованиям). Требования носят чисто "функциональный" характер, никаких предположений о вычислимости функций из Q не делается. Доказательство этого утверждения конструктивно, перестановки порождающего множества строятся из функций базиса в Q, нумерационных функций, а также некоторых базовых арифметических функций. Особый интерес представляют классы Q, являющиеся приближениями класса функций, "вычислимых на практике". В этом случае Gr(Q) представляет собой множество всех эффективных неизбыточных кодов No —» No, допускающих эффективное декодирование. Такие коды используются как при сжатии информации, так и при шифровании. Нахождение конечных порождающих множеств таких групп дает много информации о структуре этих групп, а также дает простой и эффективный способ нумерации элементов этих групп.

В главе 3 доказана конечная порождаемость группы Gr(Q) для классов FP, FFOM, обобщений классов Гжегорчика и др. Отметим, что классы перестановок Gr(Q) являются подклассами классов одноместных функций QW, существование базисов в Q^ для большого семейства классов Q доказано в [4]. При доказательстве конечной порождаемости Q^ в [4] используется тот факт, что суперпозиция позволяет выделить из функции ту информацию, которая требуется, и "убрать все лишнее", например, значение f(g(x)) не зависит от значений функции / на аргументах, не принадлежащих области значений д. Это позволяет использовать квазиуниверсальные функции, аналогичные тем, что использовались в работах [9,12, 6], т.е. функции, содержащие в некотором смысле информацию о всех функциях из Q^1) (с использованием вспомогательных функций из квазиуниверсальной функции можно выделить ту часть информации, которая соответствует некоторой конкретной функции, и, воспользовавшись другими вспомогательными функциями, построить нужную функцию). Для классов перестановок такой метод не работает, для доказательства конечной порождаемости Gr(Q) используется новый метод, специально разработанный в рамках этой диссертации.

Особый интерес представляет задача минимизации порождающего множества. В главе 3 доказано, что при тех же самых требованиях на Q мощность минимального порождающего множества равна двум (точнее, доказана только верхняя оценка, нижняя тривиально следует, например, из некоммутативности). Более того, доказано, что существует двухэлементное множество, порождающее Gr(Q) в функциональном смысле, т.е. базис по суперпозиции из двух функций.

Основные результаты диссертации докладывались на международных конференциях "Дискретные модели в теории управляющих систем" (Москва, 2006 г.), "Проблемы теоретической кибернетики" (Казань, 2008 г.), научно-исследовательском семинаре института проблем передачи информации, научно-исследовательском семинаре кафедры математической логики и теории алгоритмов механико-математического факультета МГУ, научно-исследовательском семинаре кафедры математической кибернетики факультета ВМиК МГУ, опубликованы в работах [32-36].

3. Формулировка основных результатов 3.1. Основные определения

Для удобства читателя некоторые определения здесь и в других разделах повторяют приведенные в обзорной части.

Пусть No = {0,1,2,.}. Рассматриваются всюду определенные функции (произвольного числа аргументов) на множестве No. Под операцией суперпозиции будем подразумевать подстановку функций в функции, перестановку и отождествление переменных, введение фиктивных переменных.

Пусть Q — некоторый класс функций на No. Будем обозначать через [Q] замыкание по суперпозиции класса Q.

Пусть Ф - некоторое множество функций, замкнутое относительно суперпозиции, иФСФ. Будем говорить, что множество Ф порождает множество Ф, если [Ф] = Ф. Конечные множества, порождающие Ф, будем называть конечными базисами по суперпозиции в множестве Ф.

Положим х у — тах(.т — у, 0), . , I 1, если х > 0, sgO) = <

10 иначе, , ч I 0, если х > О, sg(®) = \

II, если х = О, ^ ^ ^остатку от деления х на у, если у > О, log2 ж]

О иначе, целой части двоичного логарифма х, если х > О, О иначе, х(у) = у-му двоичному разряду числа х оо таким образом, х = ^^ х{у) • 2У), у=о

1еп(ж) = ([log2 х] + 1) • sg(:r). (4)

Заметим, что 1еп(ж) равно длине двоичной записи х, если х > 0, и нулю иначе. Определим функцию х Л у — поразрядную конъюнкцию двоичных представлений чисел х и у. Пусть апап-1. ао5 ЬпЪп-\. &о — двоичные представления чисел х и у (если длины двоичных представлений различны, то старшие разряды двоичного представления меньшего числа равны нулю). Тогда двоичное представление числа х Л у есть ап ■ bn)(an-1 • Ъп-1). (ао • bo).

Характеристической функцией предиката р{хi,. ,хп) будем называть функцию Хр{х 1? • • •, хп) такую, что при любых Х\,.,хп

Jl, если р(х\,хп) истинно,

Хр\х1 )■■■■> хп) — Л

10 иначе.

Для класса функций Q через Q* будем обозначать множество всех предикатов, характеристические функции которых лежат в Q.

Будем говорить, что функция f(x 1, у) получена из функций д{х 1, ., хп), h(xi, ., хП} у, z), j(xi, ., хп, у) с помощью операции ограниченной рекурсии, если выполняются соотношения

Оь ., хп: 0) = д(х 1, ., жп), a?i, ., хп, у 4-1) = h{xu .,хп,у, f{xh ., хп, у)), f(x 1, ., ж„, у) < • • •, Жп, у).

Определим классы £n (n € No) иерархии Гжегорчика [19]. есть минимальный класс функций, содержащий функции х + 1, fn(x,y) и замкнутый относительно суперпозиции и ограниченной рекурсии, где

Мх,у) = у + 1, fi(x,y) = x + y,

2(аг,г/)=Ф + 1Му + 1), при n ^ 2

Лн-1(0,у) = /„(у + 1,2/ + 1), п+1(ж + 1,г/) = /п+1(а:,/п+1(ж,2/)).

Для векторов из переменных (и их частей) будут использоваться сокращенные обозначения вида х, у и т. п. (например, (x,t) вместо (жь ., t)).

3.2. Основные результаты главы 1

Будем говорить, что функция f{x,zi,.,zn) получается из функции д(у, zi,., zn) с помощью операции ограниченного суммирования по переменной у, если f{x,zu.,zn) = ^g{y,zh.,zn). у^х

Класс S функций, элементарных по Сколему (см. [10, 28, 29]) — это минимальный класс функций, содержащий функции

0, ® + 1, х + у (5) и замкнутый относительно суперпозиции и ограниченного суммирования. Отметим, что S совпадает с минимальным классом, содержащим функции (5) и замкнутым относительно суперпозиции и суммирования вида Ylx<y (сумма по пустому множеству равна нулю), для удобства мы будем использовать именно это определение.

Для каждого множества функций Q определим последовательности классов [Q] 2* и [Q]"y (п = 0,1,2,.) индуктивно.

1- \Qt = [<?]°. = [<?]•

2. Если / € \Q\l ([Qfxv), то / е [Q]J,+1 (КС1).

3. Если / G [Q]2х (/ € [Q]"y) и д получается из / перестановкой или отождествлением переменных, а также введением фиктивных переменных, то д G [Q\lx (д Е [Q]nxy).

4. Если f(yi,.,ym) е Q и gi(xu.,xn), gm(xi,.,xn) G [Q]%x (№)■ то жп),., gm{x\i., жп)) G [Q]2x ([Q]xy)

5. Если / € , ^ G [Q]nxV, Л G [Q& , то 2h G и /' G [Q]"y+1.

Для [Qjg* и будем использовать сокращенные обозначения [Q] 2* и [Q]а;у соответственно.

Введем последовательность классов Р" (п = 0,1, 2,.) индуктивно.

1. Р° - класс всех полиномов.

2. Pn+1 есть класс всех функций вида 2?, где / G Рп.

Определим класс XSn (п = 0,1,2,.) как класс всех функций /(ж 1,. ,хп), для которых выполнены следующие два условия:

1. / ограничена некоторой функцией из Pn+1.

2. Существуют функции т(х i,., ж„) G Р„ и д(х i,. ,хП7 у, z) G S такие, что жь ., жп)(2/) = .,хп,у, т{х 1,., Я7„)). xs определим как класс всех функций f(x 1,. ,жп), для которых выполнены следующие два условия:

1. Существует полином р(х\,. ,хп) с натуральными коэффициентами такой, что для любых х\,. ,хп справедливо неравенство

2. f(xi,.,xn)(y) е S. Очевидно, что S С XS и

XS° - XS (это доказывается на основе техники из [10]). Положим

Т = {ж + 1, ху, х + у, хАу, [х/у]}. Теорема 1. XS = [Т]2Х = [Т]хУ.

Эта теорема доказана в разделе 1 главы 1.

Если А — некоторый алфавит, то будем обозначать А+ множество всех конечных непустых слов в алфавите А. Если X — некоторое слово в алфавите А, то будем обозначать \Х\ длину этого слова.

Назовем FOM-термом над переменными xi,.,xm выражение вида

Х\, . . . , Жт, 1, •

Определение. Элементарными FOM -формулами над переменными a?i,.,a;m называются выражения вида (ti ^ ^2), BIT^i,^) или X(£i), где t\,t2 — FOM-термы над переменными х\,. ,хт.

Определим индуктивно понятие FOM-формулы над переменными Х\,., хт.

1. Все элементарные FOM-формулы над xi,.,xm являются FOM-формулами над xi,., хт.

2. Если Ф1, Ф2 — FOM-формулы над переменными xi,.,xm, Xi G {хи.,хт}, то (Ф1&Ф2), (Ф1 V Фг), (-Ф0, (3^)(Фх), (Vsi)№i), (Мж^)(Ф1) являются FOM-формулами над . ,хт.

2 В список переменных входят не только свободные, но и связанные переменные, технически это более удобно.

Каждому FOM-терму t над переменными xi,.,xm следующим образом сопоставим функцию ht(X, х\,., хт), определенную на множестве всех наборов (X, Xi,., хт) таких, что X 6 {0,1}+ и 1 ^ ., хт ^

1. Если t есть 1, то ht{X,Xi,. ,хт) = 1.

2. Если t есть |Х|, то ht(X,x i,.,xm) = \Х\.

3. Если t есть Xi, то ht{X,x 1,. ,жт) = Xi.

Каждой элементарной FOM-формуле Ф над переменными xi,. ,хт следующим образом сопоставим предикат p$(X,xi,. ,хт), область определения которого совпадает с областью определения функций FOM-термов над Xi,., хт.

1. Если Ф имеет вид (t\ ^ £2), то

Рф(Х,хъ. ,хт) = (Ыг(Х,х 1,.,жт) < Ы2(Х,хи.,хт)).

2. Если Ф имеет вид BIT^i,^)? то рФ(Х,хи .,хт)~ (htl(X,xh . ,xm){ht2{X,x 1,. ,хт) - 1> = 1).

3. Если Ф имеет вид X{t\), то

Рф (X, х\:., Хт) = (ht^X, х\,., жт)-й символ слова X равен 1), где нумерация символов начинается с единицы.

Каждой FOM-формуле Ф над переменными х\,. ,хт следующим образом сопоставим предикат рф(Х, Х\,., хт), область определения которого совпадает с областью определения функций FOM-термов над Xi,., хт.

1. Если формула является элементарной FOM-формулой, то соответствующий ей предикат совпадает с предикатом, определенным для данной элементарной формулы.

2. Если Ф имеет вид (Ф1&Ф2), то

Рф{Х,хъ. ,хт) = рфг{Х,Х1,. ,хт)крф2(Х,х1,. .,хт).

3. Если Ф имеет вид (Ф1 V Ф2), то

Рф(Х, xi,., хт) = рф, (X, xi,., хт) V рф2(X, xi,., жт).

4. Если Ф имеет вид (—1Ф1), то рф{Х,х\, .,хт)~ ^рфг(Х,х 1,. ,жт).

5. Если Ф имеет вид (Зж;)(Ф1), то

Рф(Х, х\, .,хт)= (зх)(1^х<\х\)РФ1{х, Xi,., Xi-1, X, Xi+1, . . . , хт).

6. Если Ф имеет вид (Vrc^)(Фх), то

Х\, ., хт = Xi,., Xi-1, X, Xi+1, ., хт).

7. Если Ф имеет вид (Мжг-)(Ф1), то рф{Х,Х\,. ,хт) истинно тогда и только тогда, когда количество х таких, что 1 ^ х ^ \Х\ и рФх{Х,

Xi, . . . , Xi— 1, X, Xi-)-i, . . . , Хт ) истинно, больше, чем \Х\/2.

Класс FOM (см. [14]) определим как множество всех всюду определенных на множестве {0,1}+ предикатов <р{Х), для которых существует FOM-формула, которой соответствует предикат р(Х, х\,., хт) такой, что при любых X, х\,., хт из его области определения ip{X) = р{Х,х 1,. ,хт).

Если х\,.,хт — натуральные числа, то будем обозначать CODE(a?i,., хт) слово

01si01s201.01sm01, где пустому слову, если Х{ = О, слову, получающемуся из двоичной записи Xi

Si — заменой каждой единицы на 11, а каждого нуля на 00, если х\ф 0.

Класс FOM^ определим как множество всех всюду определенных на множестве No предикатов ip(xi,., хп), для которых существует предикат i{j{X) € FOM такой, что при любых х\,., хп выполнено Хп

Класс FFOM определим как множество всех всюду определенных на множестве No функций f(x 1,. ,хп) таких, что выполняются следующие два условия.

1. Существует полином р(уi,. ,уп) такой, что при любых х\,. ,хп

2. Предикат р, определяемый соотношением р(хи.,хп,у) = (f(xi,.,xn){y) = 1), лежит в FOM^. Теорема 2. Имеет место

FFOM = \х + у, х + у, х А у, [х/у], х + у, х + у, хАу, [х/у],

Эта теорема доказана в разделе 2 главы 1.

Введем последовательность классов Рп (тг = 0,1, 2,.) индуктивно.

1. Р° - класс всех полиномов.

2. Pn+1 есть класс всех функций вида 2?, где / G Рп.

Определим класс FFOMn (п = 1,2,,.) как класс всех ограниченных сверху функциями из Рп функций j{x\,., хп), для которых существуют функция т{х 1,., хп) еРпи предикат р(хi,., хп, у, z) е FOM^ такие, что asi,., хп) (у) = 1) == р(х 1 ,.,хп,у, m(xi,., хп)). Теорема 3. При любом п > О имеет место

XS" - [ТЙ+1 = [Т]^1 = FFOMn+1.

Эта теорема является обобщением теоремы 1 и доказана в разделе 3 главы 1.

3.3. Основные результаты главы 2

Определим R{x, у) как циклический сдвиг двоичного представления числа х на у разрядов вправо. Иными словами, пусть R{0, у) = О, R( 1, у) = 1, а если х ^ 2 и атеап-1 • • • - двоичное представление х, причем an = 1, то двоичная запись у) есть

0>п+у0"п+у—1 • ■ ■ ®1+у&у) где все сложения проводятся по модулю п + 1. Из [19] следует, что функции X sg(a?), sgO), х + у, - , [log2 ж], гшп(ж, 2У), гт(ж,?/) У принадлежат классу £2 Гжегорчика.

С использованием, например, операции ограниченного суммирования [10] нетрудно показать, что функции ж Л г/, у) принадлежат классу

Определим функцию Q(x, рi, р2, Ci, С2, £) следующей примитивной рекурсией: Q(x, Ри Рг, Си С2, 0) = ж, Q(x, Pi, Р2, Ci, с2, 1 + 1) =

Q(a?, рь р2, СЬ с2, если Pi J Р2, Ci, с2, 0 A r(pu с1-€)ф О, Q(xi Ри Р2, ci) с2; t) + -R(P2j C2-t) в противном случае.

Поскольку Q(x, pi, Р2, Ci, С2, t) < ж+ 2^, то имеем ограниченную рекурсию в классе и, таким образом, Q е £ . Функцию Ж2, • • •, хт) из класса S2 будем называть квазиуниверсальной в классе относительно системы функций Ф, если для любой функции f(y) из класса £2 найдутся функции Й» 9i(y), 92(у), • • •, 9т{у) из множества Ф, такие, что

Й = KQ(gi(y), д2(у), ., дт(у)),у)

Теорема 4. Функция Q(x, р\, Р2, Ci, с2, £) является квазиуниверсальной в классе 2 относительно замыкания по суперпозиции системы функций х~ ж + 1, ху, тт(ж, 2У),

L2/J log2 ж]. (6)

Следствие. Система функций ж + 1, ху, min(a7, 2У), х + у, —

LУJ образует базис по суперпозиции в классе Е2 Гэюегорчика. pog2a?], Q{x, ри р2, сь с2, t)

3.4. Основные результаты главы 3

Под термином перестановка будет подразумеваться перестановка на множестве No

Для любого класса Q, замкнутого относительно суперпозиции и содержащего функцию /(ж) = х, через Gr(Q) обозначим группу перестановок fJ-'eQ}, о).

Определение. Бесконечное множество А С No называется регулярным в классе функций Q, если выполняются условия:

1- ХА е Q;

2. Можно так занумеровать элементы множества А, что функция //(ж), вычисляющая номер элемента х в этой нумерации (равна нулю при х А), и функция 1у(х), вычисляющая элемент с номером ж, принадлежат Q (нумерация начинается с нуля).

Будем рассматривать классы функций Q, удовлетворяющие требованиям:

I. Q содержит функции

1, х + у, х + у, ж-sg у, [ж/2]; (7)

II. Q содержит нумерационную функцию С2(ж1,ж2), взаимно-однозначно отображающую множество Ng на No, и обратные к ней функции с2д(ж) и С2,2(ж) (с2д(с2(ж,у)) = ж, с2)2(с2(ж, у)) = у при любых ж, уУ,

III. Для любой перестановки / Е Gr(Q) существуют непересекающиеся регулярные в Q множества А, В такие, что f(A) П В = 0 и No\A, No\B регулярны в Q;

IV. Q замкнут относительно суперпозиции;

V. Q имеет конечный базис по суперпозиции.

Заметим, что требования не являются независимыми (например, IV следует из V). Тем не менее, рассматриваться будут все требования, чтобы для некоторых утверждений показать, что они справедливы при достаточно слабых ограничениях на Q (см. главу 3).

Теорема 5. Если класс Q удовлетворяет требованиям X—XXI, V, то существуют две перестановки из Gr(Q), композициями которых моэюно представить любую перестановку из Gr(Q).

Пусть FP — множество всех функций Nq —> No, вычислимых на машине Тьюринга за полиномиальное время от длины входа (числа представляются в двоичном виде). Аналогично, FL — множество всех функций, вычислимых с зоной O(logn), где п — длина входа (на многоленточных машинах Тьюринга, не записывающих на входную ленту). Кроме того, будем использовать определение класса FFOM из раздела 3.2 введения.

Класс функций Q называется £2 -замкнутым, если он содержит функции

О, ж + 1, ху и замкнут относительно суперпозиции и ограниченной рекурсии.

Теорема 6. Классы FP; FL, FFOM, а также все Е2 -замкнутые классы, имеющие конечный базис по суперпозиции, удовлетворяют требованиям I—III, V.

Следствие. Для классов Q из теоремы 6 группа Gr(Q) порождается двумя перестановками (в том числе в функциональном смысле, т.е. с использованием только композиции).

1. Виноградов А. К., Косовский Н. К. Иерархия диофантовых представлений примитивно рекурсивных предикатов // Вычислительная техника и вопросы кибернетики. — 1975. — Вып. 12. — С. 99-107.

2. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. — 416 с.

3. Мальцев А. И. Алгоритмы и рекурсивные функции. М.: Наука, 1986. 367 с.

4. Марченков С. С. Базисы по суперпозиции в классах рекурсивных функций // Математические вопросы кибернетики. М.: Наука, 1991. -вып. 3.-С. 115-139.

5. Марченков С. С. О функциях, элементарных по Сколему // Математические заметки. 1975. - Т. 17, N. 1. — С. 133-141.

6. Марченков С. С. Об ограниченных рекурсиях // Mathematica Balkanica. 1972. - Т. 2. - С. 124-142.

7. Марченков С. С. Об одном базисе по суперпозиции в классе функций, элементарных по Кальмару // Математические заметки. — 1980. — Т. 27, N 3. С. 321-332.

8. Марченков С. С. Простые примеры базисов по суперпозиции в классе функций, элементарных по Кальмару // Banach Center Publication. Warsaw. 1989. - Т. 25. - С. 119-126

9. Марченков С. С. Устранение схем рекурсий в классе £2 Гжегорчика // Математические заметки. — 1969. — Т. 5. — N. 5. — С. 561-568.

10. Марченков С. С. Элементарные рекурсивные функции. М.: МЦНМО, 2003. 112 с.

11. Минский М. Вычисления и автоматы. М., Мир, 1971. — 367 с.

12. Мучник А. А. О двух подходах к классификации рекурсивных функций // Проблемы математической логики. М.: Мир, 1970. С. 123-138. 432 с.

13. Allender Е., Barrington D.A.M., Hesse W. Uniform constant-depth threshold circuits for division and iterated multiplication // Journal of Computer and System Sciences. — 2002. — V. 65. — P. 695-716.

14. Barrington D.A.M., Immerman N., Straubing H. On uniformity within NC1 // Journal of Computer and System Sciences. — 1990. — V. 41. — P. 274-306.

15. Bellantoni S., Cook S. A new recursion-theoretic characterization of the polytime functions // Computational Complexity. — 1992. — V. 2. — P. 97-110.

16. Cobham A. The intrinsic computational difficulty of functions // Proceedings of the 1964 International Congress for Logic, Methodology, and Philosophy of Science. — 1964. — P. 24-30.

17. Church A. An unsolvable problem of elementary number theory // American journal of mathematics. — 1936. — N. 58. — P. 345—363.

18. Greenlaw R., Hoover H., Ruzzo W. Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, 1995. — 311 p.

19. Grzegorczyk A. Some classes of recursive functions // Rozprawy Mathematyczne. — 1953. — V. 4. — P. 1-46. (Русск. пер.: Гжегорчик А. Некоторые классы рекурсивных функций // Проблемы математической логики. М.: Мир, 1970. С. 9-49. — 432 с.)

20. Волков С. А. Конечная порождаемоеть некоторых групп рекурсивных перестановок // Дискретная математика. — 2008. — Т. 20, вып. 4. — С.

21. Волков С. А. Конечная порождаемоеть некоторых групп рекурсивных перестановок // Проблемы теоретической кибернетики. Тезисы конференции. — Казань, 2008. — С. 15.

22. Волков С. А. Порождение некоторых классов рекурсивных функций суперпозициями простых арифметических функций // Доклады академии наук. 2007. - Т. 415, N. 4. - С. 439-440.

23. Волков С. А. Пример простой квазиуниверсальной функции в классе £2 иерархии Гжегорчика // Дискретная математика . — 2006. — Т. 18, вып. 4. С. 31-44.

24. Волков С. А. Экспоненциальное расширение класса функций, элементарных по Сколему, и ограниченные суперпозиции простых арифметических функций // Математические вопросы кибернетики. М.: Физ-матлит, 2007. вып. 16. - С. 163-190.61.78.