Almost polynomial recurrent sequences with algorithmically unsolvable problems

Recieved: 01/09/2023

Accepted: 03/05/2023

Published: 09/20/2023

Keywords: almost polynomial recurrent sequences

To cite this article

Marchenkov S.S. Almost polynomial recurrent sequences with algorithmically unsolvable problems. // Moscow University Journal. Series 15. Computational Mathematics and Cybernetics. 2023. N 3, p.49-55 https://doi.org/10.55959/MSU/0137–0782–15–2023–47–3–49–55.

This work is licensed under a Сreative Commons Atribiution - NonCommercial 4.0 International (CC BY-NC 4.0)

Marchenkov S.S. (Lomonosov Moscow State University (MSU))

Abstract

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.