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/