Описание проекта
Одной из важных задач теоретического программирования является задача эффективного построения по набору программ вычисления функций (перечисления множеств) на одном устройстве программ вычисления тех же функций (перечисления тех же множеств) на другом устройстве. Практическая реализация этих трансляций оказывается весьма сложной, а часто пока и не осуществлённой. В рамках проекта ожидается получить продвижения в разработке фундаментального аппарата реализации описанных программных трансляций.
Для разъяснения трудностей трансляций между реализациями эквивалентных алгоритмов на разных устройствах будет использован подход, основанный на понятиях вычислимой нумерации и сводимостей нумераций. Причём кроме классической сводимости нумераций мы будем рассматривать как позитивные сводимости (e- и p-сводимости), так и более приближенные к практике понятия, возникающие при рассмотрении алгоритмов в ограниченными ресурсами (полиномиальные алгоритмы, примитивно рекурсивные алгоритмы и т.д.).
В рамках проекта ставится задача изучения решёточных свойств структур, индуцируемых сводимостями на вычислимых нумерациях. Для этого будут рассмотрены конкретные частные подзадачи: исследование минимальных нумераций, исследование универсальных нумераций и т.д.
