О замкнутых классах финально периодичных функций
Семигородских А.В.
Замкнутым классам функций над счетным множеством к настоящему времени
посвящен целый ряд работ.
В частности, большое внимание было уделено
замкнутым классам рекурсивных функций.
Обзор результатов, в основном касающихся базисов таких классов,
можно найти в работе [1]. Поиск базисов ведется для классов, интересных
в том или ином смысле.
При этом к стандартным итеративным операциям, определенным в [2], нередко
добавляют какой-нибудь вид рекурсии. Следуя этим путем,
мы найдем базис для ряда замкнутых классов,
тесно связанных с понятием периодичности.
Периодические функции часто возникают в математике и ее
приложениях. Также нередко встречаются непериодические функции,
ограничения которых на множества достаточно больших аргументов
являются периодическими. Понятие периодичности можно распространить
и на функции от многих переменных. Мы сделаем это следующим образом.
Функцию $f(x_1,...,x_k)$ назовем
финально периодичной с периодом $p\in \Bbb N$,
если существует $n_f \in \NZ$ такое, что для любых $i \le k$
и $a_1,...,a_k \in \NZ$ функция
$$g(x)=f(a_1,...,a_{i-1},x+n_f,a_{i+1},...,a_k)$$
периодична с периодом делящим $p$.
Через $\Class{f_1,f_2,...}$ обозначим наименьший класс,
содержащий множество функций $\{f_1,f_2,...\}$ и
замкнутый относительно примитивной рекурсии и
стандартных итеративных операций.
Справедлива следующая теорема.
{\bf Теорема.}
{\it Пусть $c_1,...,c_n$ --- $n$ попарно различных констант
из множества $\NZ$. Тогда $\Class{c_1,...,c_n}$ есть в точности
класс всех принимающих значения из $\{ c_1,..., c_n\}$
финально периодичных функций с периодами, делящими натуральные
степени числа $n!$.}
Из теоремы вытекает
{\bf Следствие.}{\it Класс финально периодичных функций есть в точности
класс $\Class{\NZ}$.}
Отсюда легко получаем, что любая периодическая
функция получается из констант с помощью примитивной
рекурсии и итеративных операций.
$$\mbox{\bf Литература}$$
1. Марченков С. С. Базисы по суперпозиции в классах рекурсивных функций //
Математические вопросы кибернетики, вып. 3. --- 1991. --- с. 115--139.
2. Мальцев А.И. Итеративные алгебры Поста. Новосибирск, 1974.