|
This article is cited in 2 scientific papers (total in 2 papers)
On polynomial-modular recursive sequences
S. S. Marchenkov Lomonosov Moscow State University
Abstract:
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.
Received: 30.08.2021
Citation:
S. S. Marchenkov, “On polynomial-modular recursive sequences”, Diskr. Mat., 34:2 (2022), 43–49; Discrete Math. Appl., 33:5 (2023), 293–298
Linking options:
https://www.mathnet.ru/eng/dm1667https://doi.org/10.4213/dm1667 https://www.mathnet.ru/eng/dm/v34/i2/p43
|
Statistics & downloads: |
Abstract page: | 199 | Full-text PDF : | 24 | References: | 42 | First page: | 10 |
|