научная статья по теме ПОРОЖДЕНИЕ НЕКОТОРЫХ КЛАССОВ РЕКУРСИВНЫХ ФУНКЦИЙ СУПЕРПОЗИЦИЯМИ ПРОСТЫХ АРИФМЕТИЧЕСКИХ ФУНКЦИЙ Математика

Текст научной статьи на тему «ПОРОЖДЕНИЕ НЕКОТОРЫХ КЛАССОВ РЕКУРСИВНЫХ ФУНКЦИЙ СУПЕРПОЗИЦИЯМИ ПРОСТЫХ АРИФМЕТИЧЕСКИХ ФУНКЦИЙ»

ДОКЛАДЫ АКАДЕМИИ НАУК, 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 рублей.

Показать целиком