В этом докладе мы опишем проблему 'трудно описуемых' классов возвратных последовательностей, то есть таких, что предсказание поведения таких последовательностей - алгоритмически неразрешимая задача. Будут рассматриваться классы целочисленных последовательностей, порождающие функции которых составлены композициями из полиномов (с целыми коэффициентами) и некоторой функции f. Основной рассматриваемый вопрос - какой должна быть эта f, чтобы получившийся класс был трудно описуемым. Такие функции f мы называем граничными. Будут изложены доказательства того, что несколько широких семейств функций являются граничными. Все эти доказательства проистекают из одной 'центральной' теоремы, для доказательства которой используется моделирование машин Минского последовательностями, т.е. конструктивно доказывается, что из системы функций 'полиномы плюс f' (для каждой из рассмотренных f) можно 'построить' универсальное вычислительное устройство.

Макеев Сергей Данилович,  МГУ имени М.В. Ломоносова