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

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.

В работе [19] А. Гжегорчик определил иерархию классов &euro-п, п € 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 Гжегорчика, без использования нумераций машин Тьюринга;

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

Результаты [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¹) (с использованием вспомогательных функций из квазиуниверсальной функции можно выделить ту часть информации, которая соответствует некоторой конкретной функции, и, воспользовавшись другими вспомогательными функциями, построить нужную функцию). Для классов перестановок такой метод не работает, для доказательства конечной порождаемости 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, ., ж&bdquo-, у) < • • •, Жп, у).

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

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

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

Лн-1(0,у) = /&bdquo-(у + 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.

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

1- Qt = [.

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

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

4. Если f (yi,., ym) е Q и gi (xu., xn), gm (xi,., xn) G [Q]%x (№)¦ то жп),., gm{xi., жп)) 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,., ж&bdquo-) G Р&bdquoи д (х i,., хП7 у, z) G S такие, что жь ., жп)(2/) = ., хп, у, т{х 1,., Я7&bdquo-)). 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 и NoA, NoB регулярны в 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. Классы FPFL, 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.