Marchenkov S.S.

Recurrent sequences over a set of integers are considered, in which arbitrary superpositions of polynomial functions and functions close to polynomial ones are used as generating functions, — almost polynomial recurrent sequences. A series of functions of the form b · ji(x) is distinguished. Each of these functions, together with polynomial functions, allows us to construct generating functions that make it possible to determine almost polynomial recurrent sequences that simulate calculations on Minsky machines. Based on this result, algorithmically unsolvable problems related to these almost polynomial recurrent sequences are formulated. Consequences are obtained that significantly expand the range of functions capable of generating recurrent sequences with algorithmically unsolvable problems.

The implicatively implicit extensions of all 27 single functions of three-valued logic are characterized. It is established that among them there are both extensions that coincide with the known implicatively closed classes, and extensions that are not closed with respect to the superposition operation. In addition, it is shown that for any k > 3, any implicatively implicit extension in Pk contains the class Hk of all homogeneous functions from Pk.