Abstract:
We consider the class $\mathrm{EP}_{\mathbb N}$ of exponentially-polynomial functions which can be obtained by arbitrary superpositions of the constants 0, 1 and arithmetic operations of addition, multiplication, and powering. For this class, we solve the algorithmic equality problem of two functions that assume a finite number of values. Next, this class is restricted to the class $\mathrm{PEP}_{\mathbb N}$, in which the function $x^y$ is replaced by a sequence of functions $\{p_i^x\}$, where $p_0, p_1,\ldots$ are all prime numbers. For the class $\mathrm{PEP}_{\mathbb N}$, the problem of membership of a function to a finitely generated class is effectively reduced to the equality problem of two functions. In turn, the last problem is effectively solved for the set of all one-place $\mathrm{PEP}_{\mathbb N}$-functions.
Fulltext:
PDF file (465 kB)