On the complexity of integer polynomial recursive sequences

Background. Linear recursive sequences represent the “classic”' object of combinatorial analysis. To express an arbitrary term of a linear recursive sequence, there are exact formulas of exponential type as in the case of a field of complex numbers, and in the case of a finite Galois field. The next step in the study of recursive sequences would be to consider polynomial recursive sequences. However, even for recursive sequences over a set of natural numbers, this problem has not yet been solved. There is an assumption that when moving to the set of integers for of polynomial recursive sequences, algorithmically unsolvable problems may appear. Then, of course, no formulas for calculating the common term of a polynomial recursive sequence in the general case should be expected. So far this assumption has not been proven, and integer polynomial recursive sequences are practically an unexplored object. In the early 2000s, the author proposed to consider “almost polynomial” recursive sequences - sequences, the generating functions of which are defined by superpositions of polynomial functions and some simple “almost polynomial” functions. As it turned out, when adding to the set of polynomial functions, for example, functions of type $sg(x)$, recursive sequences with algorithmically unsolvable problems appear. This suggests that in the case of polynomial recursive sequences over a set of integers, the recursive sequences themselves should be rather complicated from an algorithmic point of view. The substantiation of this assumption is the purpose of this article. To talk about the complexity of recursive sequences, it is necessary first of all to determine the tool with which you can will evaluate the complexity of the sequences in question. A single-tape Turing machine operating in a three-letter alphabet was chosen as such a tool. Calculations on these Turing machines can be modeled by integer recursive sequences with a polynomial generating function. As a result, for a number of problems related to recursive sequences of this type, lower superexponential estimates of the complexity of their solution are obtained. Materials and methods. The constructions and proofs use techniques and methods from the theory of computable functions. Results and conclusions. We consider recursive sequences over a set of integers with polynomial generating functions. Calculations on deterministic Turing machines are modeled using these sequences. It follows from the modeling process that some algorithmic problems for the considered recursive sequences may be EXPSPACE-complete. Thus, integer polynomial recursive sequences from an algorithmic point of view represent a rather complex object.