Volume 16, No 2, 2009, P. 42-60

UDC 519.712
S. A. Volkov
The class of skolem elementary functions

Abstract:
In this paper, we consider different equivalent definitions of the class of Skolem elementary functions (these definitions are analogous to the well-known definitions of the Kalmar elementary function class) and some results concerned with this class which are obtained by different mathematicians. Some definitions of this class were investigated by mathematicians independently. In this paper we prove equivalence of these definitions. Also, we study the problem on existence of superposition bases for this class. We prove that this problem is equivalent to one problem from complexity theory.
Bibl. 26.

Keywords: classification of recursive functions, computational complexity.

Volkov Sergey Alexandrovich ¹
1. Lomonosov Moscow State University,
Vorob’evy ghory, 119992 Moscow, Russia