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.
Fulltext:
PDF file (400 kB)