О полиномиально-модульных возвратных последовательностях

Рассмотрены возвратные последовательности над множеством целых чисел, у которых в качестве порождающих функций используются произвольные суперпозиции полиномиальных функций и функции $|x|$, — полиномиально-модульные возвратные последовательности. Показано, как вычисления на трехленточных машинах Минского можно промоделировать с помощью полиномиально-модульных возвратных последовательностей. На основе этого результата сформулированы алгоритмически неразрешимые проблемы, связанные с полиномиально-модульными возвратными последовательностями. Рассмотрены также возвратные последовательности, в которых в качестве порождающих функций используются функции, образованные некоторыми суперпозициями полиномиальных функций и функции $[\sqrt{x}]$. Для множества таких возвратных последовательностей указана алгоритмически неразрешимая проблема.