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

Изучаются возвратные последовательности над конечными множествами и множеством $\mathbf N_0=\{0,1,2,\dots\}$. Сложность возвратных последовательностей над конечными множествами оценивается через сложность вычислений на детерминированных линейно ограниченных автоматах. Вводится понятие ветвящейся возвратной последовательности. Сложность ветвящихся возвратных последовательностей над конечными множествами оценивается через сложность вычислений на недетерминированных линейно ограниченных автоматах. Возвратными последовательностями над множеством $\mathbf N_0$ моделируются вычисления на многоленточных машинах Минского. Устанавливается неразрешимость некоторых проблем, относящихся к этому типу возвратных последовательностей.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 00–01–00351.