Аннотация:Рассматриваются возвратные последовательности над множеством целых чисел с полиномиальными порождающими функциями. С помощью данных последовательностей моделируются вычисления на детерминированных машинах Тьюринга. Устанавливается, что некоторые алгоритмические проблемы для рассматриваемых возвратных последовательностей могут быть EXPSPACE-полными.