ДОКЛАДЫ АКАДЕМИИ НАУК, 2007, том 415, № 4, с. 439-440
МАТЕМАТИКА
УДК 519.7
ПОРОЖДЕНИЕ НЕКОТОРЫХ КЛАССОВ РЕКУРСИВНЫХ ФУНКЦИЙ СУПЕРПОЗИЦИЯМИ ПРОСТЫХ АРИФМЕТИЧЕСКИХ ФУНКЦИЙ
© 2007 г. С. А. Волков
Представлено академиком Ю.И. Журавлёвым 05.03.2007 г. Поступило 20.03.2007 г.
Конечные базисы по суперпозиции в классе К функций, элементарных по Кальмару (см. [1, 5]), состоящие из "простых" арифметических функций, построены в работах [2, 4, 7]. Однако для классов функций с существенно меньшими скоростями роста и вычислительной сложностью методы, использованные в этих работах, оказываются непригодными. В данном сообщении определяется конечный базис по суперпозиции в классе FFOM, существенно меньшем, чем класс К (теорема 1). Кроме того, при ограничениях на строение суперпозиций конечные базисы удается построить в классах иерархий {XSn} и {FFOMn}, покрывающих класс К (теорема 2). В построениях используются простые арифметические функции и функции, стандартные в большинстве языков программирования.
Рассматриваются функции на множестве N = = {0, 1, 2, ...}.
Положим:
х(у) = у-му разряду двоичной записи числа х, х+у = тах(0, х - у),
целой части от деления х на у, если у > 0, 0 иначе.
[x/y ] =
Определим функцию x л у. Пусть
ana
n n - 1
...an
bnbn-1 ... b0
суть двоичные представления чисел х и у (если длины двоичных представлений различны, то старшие разряды двоичного представления меньшего числа равны нулю). Тогда двоичное представление числа х л у есть
(а„ ■ Ьп)(ап_! - Ъп_!)...(ао ■ Ъ).
Московский государственный университет им. М.В. Ломоносова
Определим класс S функций, элементарных по Сколему (см. [5, 8]), как множество всех функций, получаемых из функций 0, x + 1, x+у с помощью операций суперпозиции и ограниченного суммирования вида ^.
x < у
Пусть {0, 1}+- множество всех конечных непустых слов в алфавите {0, 1}. Если X - некоторое слово в алфавите {0, 1}, то будем обозначать |X| длину этого слова.
ЕслиXе {0, 1}+ и 1 < t < X|, то определим предикат X{t) соотношением
X{t) = (t-й символ слова X равен 1).
Положим
BIT (i, j ) = ( i < j) = 1).
Пусть p(X) - предикат, определенный на множестве {0, 1}+. Предикат р принадлежит классу FOM (см. [6]), если p(X) представим формулой первого порядка с атомарными предикатами (t1 < t2), X<tj), BIT(tx, t2), где t1, t2 - термы (термами считаем символы числовых переменных, 1 и |X|), и ограниченными кванторами вида (3xi) 1 < < д , (Vxi) 1 < < щ ,
(MX)i <x< |X , где
(Mxi )1 < x < |X Ф = ( количество xi,
IX
при которых Ф истинно, не меньше — ^.
Если хь х2, ..., хт - натуральные числа, то будем обозначать CODE(x1, х2, ..., хт) слово 01510152015т01, где
пустому слову, если х, = 0, слову, получаемому из двоичной записи х, заменой каждой единицы на 11, а каждого нуля на 00, если х, Ф 0.
440
ВОЛКОВ
Класс FOMN определим как множество всех всюду определенных на множестве N предикатов ф(х1, x2, ..., xn), для которых существует предикат е FOM такой, что при любых x1, x2, ..., xn выполнено
ф(x1; x2, ..., xn) = y(CODE(x1; x2, ..., xn)).
Класс FFOM определим как множество всех всюду определенных на множестве N функций f (x1, x2, ..., xn), ограниченных сверху функциями
вида 2
Р([ log2x1]
> [ log2xn])
, где p - полином, таких, что
N
BIT(f (xi, x*..., xn), y) е FOM .
Пусть Q - некоторый класс функций натурального аргумента. Будем обозначать через [0] замыкание класса Q по суперпозиции.
Определим последовательности классов ^ и ^]"}у (п = 0, 1, 2, ...) индуктивно.
1. [Q £ = ^ £ = [Q].
2. Если / е [Q]" (е [Q]" ), то / е [Q]",+ 1
(е [Q ^ ).
4. Если ff^y^ У2, ym) е Q и gl(xl, x2, xm), , gm(x1, x2, xm) е [Q £ (е [Q ]ny), то
f(g 1 (x1, x2, •••, xn), •••, gm(x1, x2, •••, xn)) е
е [Q]"2, (е [Q]).
5. Если f е [Q]" + 1, g е [Q]" , h е [Q]2
2h е [Q]2
V
иfg е [Q Г
то
"2х "■> ~ ■ Пусть Р0 - класс всех полиномов с натуральными коэффициентами, и для любого п (п > 0) Рп + 1 есть класс всех функций вида 2/, где /е Рп.
Определим XSn (п = 0, 1, 2, ...) как класс всех ограниченных сверху функциями из Рп + 1 функ-
ций f(x1, x2, ..., xn), для которых существуют функции m(x1, x2, ..., xn) е Pn и g(x1, x2, ..., xn, y, z) е S, такие, что
f(x1, X2, • ■■, xn)<y) —
— g ( x1, x2, ..., xn, y, m ( x1, x2, •••, xn)).
Определим FFOMn (n = 1, 2, ...) как класс всех ограниченных сверху функциями из Pn функций f(x1, x2, ..., xn), для которых существуют функция m(x1, x2, ..., xn) е Pn и предикат p(x1, x2, ..., xn, y, z) е е FOMN, такие, что
BIT(f(xb x2, ..., xn),y) =
= p(x1, x2, •.., xn, y, m(x1, x2, • • •, xn)) .
Положим
T — {x + 1, xy, x+y, x Ay, [x/y]},
Теорема 1. Имеют место равенства
FFOM — [x +1, xy, x+y, x a y, [x/y], 2
[log2x]
] =
[l°g2y]n
3. Если/е [2£ (/е ^) и g получается из/
перестановкой или отождествлением переменных, а также введением фиктивных переменных,
то g е ^£ ^ е й£).
— [x + 1, xy, x+y, x A y, [x/y], x~].
Теорема 2. При любом n > 0 имеют место равенства
XSn — [ T f — [ T ]nJl — FFOMn + 1.
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект 06-01-00438).
СПИСОК ЛИТЕРАТУРЫ
1. Гжегорчик А. В кн.: Проблемы математической логики. М.: Мир, 1970. С. 9-49.
2. Марченков С.С. // Мат. заметки. 1980. Т. 27. № 3. С. 321-332.
3. Марченков С.С. // Banach Center Publ. Warsaw, 1989. Т. 25. С. 119-126.
4. Марченков С.С. // Мат. вопросы кибернетики. 1991. В. 3. С. 115-139.
5. Марченков С.С. Элементарные рекурсивные функции. М.: МЦНМО, 2003.
6. Barrington D.A.M., Immerman N, Straubing H. // J. Comput. and Syst. Sci. 1990. V. 41. P. 274-306.
7. Mazzanti S. // Math. Logic Quart. 2002. V. 48. P. 93104.
8. Skolem Th. In: Abstract of Short Communications. Intern. Congr. Math. Stockholm, 1962. P. 11.
ДОКЛАДЫ АКАДЕМИИ НАУК том 415 < 4 2007
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.