Geodesic
On polynomial-modular recursive sequences
Diskretnaya Matematika, Tome 34 (2022) no. 2, pp. 43-49.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider recursive sequences over the set of integers, where as rules of generation we take arbitrary superpositions of polynomial functions and the function $|x|$; such sequences are referred to as polynomial-modular recursive sequences. We show how evaluations on three-tape Minsky machines can be simulated via polynomial-modular recursive sequences. Based on this result, we formulate algorithmically unsolvable problems related to polynomial-modular recursive sequences. We also consider recursive sequences in which the rules of generation are functions formed by some superpositions of polynomial functions and the function $[\sqrt{x}]$. For the set of such recursive sequences, an algorithmically unsolvable problem is indicated.
Keywords: recursive sequence, polynomial-modular function. 
@article{DM_2022_34_2_a4,
     author = {S. S. Marchenkov},
     title = {On polynomial-modular recursive sequences},
     journal = {Diskretnaya Matematika},
     pages = {43--49},
     publisher = {mathdoc},
     volume = {34},
     number = {2},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2022_34_2_a4/}
}
TY  - JOUR
AU  - S. S. Marchenkov
TI  - On polynomial-modular recursive sequences
JO  - Diskretnaya Matematika
PY  - 2022
SP  - 43
EP  - 49
VL  - 34
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2022_34_2_a4/
LA  - ru
ID  - DM_2022_34_2_a4
ER  - 
%0 Journal Article
%A S. S. Marchenkov
%T On polynomial-modular recursive sequences
%J Diskretnaya Matematika
%D 2022
%P 43-49
%V 34
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2022_34_2_a4/
%G ru
%F DM_2022_34_2_a4
S. S. Marchenkov. On polynomial-modular recursive sequences. Diskretnaya Matematika, Tome 34 (2022) no. 2, pp. 43-49. http://geodesic.mathdoc.fr/item/DM_2022_34_2_a4/

[1] Maltsev A. I., Algoritmy i rekursivnye funktsii, Nauka, M., 1986, 368 pp.

[2] Marchenkov S. S., “On the complexity of recurring sequences”, Discrete Math. Appl., 13:2 (2003), 167–178 | DOI | MR | Zbl

[3] Marchenkov S. S., “On the complexity of polynomial recurrence sequences”, Problems of Information Transmission, 54:3 (2018), 258–262 | DOI | MR | Zbl

[4] Marchenkov S. S., Savitskii I. V., Mashiny v teorii vychislimykh funktsii, MAKS Press, M., 2018, 88 pp.

[5] Matiyasevich Yu. V., “Diofantovo predstavlenie perechislimykh predikatov”, Izv. AN SSSR. Ser. matem., 35:1 (1971), 3–30 | Zbl

[6] Matiyasevich Yu. V., Desyataya problema Gilberta, Nauka, M., 1993, 224 pp. | MR

[7] Nechaev V. I., Elementy kriptografii. Osnovy teorii zaschity informatsii, Vysshaya shkola, M., 1999, 112 pp. | MR

[8] Kholl M., Kombinatorika, Mir, M., 1970, 424 pp. | MR