Аннотация:Рассмотрены возвратные последовательности над множеством целых чисел, у которых в качестве порождающих функций используются произвольные суперпозиции полиномиальных функций и функций, близких к полиномиальным, - почти полиномиальные возвратные последовательности. Выделена серия функций вида bj_i(x). Каждая из этих функций вместе с полиномиальными функциями позволяет строить порождающие функции, которые дают возможность определять почти полиномиальные возвратные последовательности, моделирующие вычисления на машинах Минского. На основе этого результата сформулированы алгоритмически неразрешимые проблемы, связанные с данными почти полиномиальными возвратными последовательностями. Получены следствия, которые существенно расширяют круг функций, способных порождать возвратные последовательности с алгоритмически неразрешимыми проблемами.