Конечный базис по суперпозиции в классе функций, вычислимых на нестирающих машинах Тьюринга с выходом

Актуальность и цели. Более 60 лет назад А. Гжегорчик сформулировал проблему о существовании конечных базисов по суперпозиции в классах рекурсивных функций, образующих иерархию множества всех примитивно-рекурсивных функций. Эта проблема была положительно решена различными авторами для многих крупных и содержательно интересных классов рекурсивных функций. В последние годы в связи с возросшим интересом к изучению полиномиально вычислимых функций эта проблема вновь стала рассматриваться для сравнительно небольших классов подобных функций. В частности, интерес вызывают классы функций, которые полиномиально вычислимы на различных вариантах машин Тьюринга, подчиняющихся сильным ограничениям на строение и способы оперирования с внешней памятью. Решение задачи о существовании конечного базиса по суперпозиции в таких классах функций позволило бы глубже понять природу полиномиальных вычислений и, возможно, привнести дополнительные аргументы в решение проблемы о соотношении детерминированных и недетерминированных полиномиальных вычислений. Целью работы является построение конечного базиса по суперпозиции в классе C функций, вычислимых на нестирающих машинах Тьюринга с выходом. Класс C недавно был введен С. С. Марченковым для получения «верхней границы» сложности вычисления функций, получаемых с помощью ограниченной префиксной конкатенации, и практически не подвергался детальному изучению. Материалы и методы. В работе используется метод доказательства существования конечного базиса по суперпозиции, основанный на использовании квазиуниверсальной функции. Результаты и выводы. Проведено построение квазиуниверсальной функции для класса C функций, вычислимых на нестирающих машинах Тьюринга с выходом. Полученная функция использована для нахождения конечного базиса по суперпозиции в классе C. Данный результат может быть применен для решения аналогичных задач в классах вычислимых функций, близких к классу C.