О сложности полиномиальных возвратных последовательностей

Рассмотрены возвратные последовательности над множеством целых чисел, у которых в качестве порождающих функций используются произвольные суперпозиции полиномиальных функций и функции sg, — полиномиальные возвратные последовательности. Определены полиномиально-регистровые машины (PR-машины), близкие к машинам с произвольным доступом к памяти. Доказано, что вычисления на PR-машинах можно промоделировать полиномиальными возвратными последовательностями. С другой стороны, вычисление элементов полиномиальной возвратной последовательности можно выполнить с помощью подходящей PR-машины.