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.
Fulltext:
PDF file (769 kB)