Степень неразрешимости проблемы полноты в алгебрах рекурсивных функций

Для алгебры $A$ рекурсивных функций определены множества $P_\text{К}(A)$ и $P_\text{Э}(A)$, характеризующие проблемы полноты всякого конечного и всякого эффективного подмножества алгебры. Установлено, что эти множества являются $\Sigma_3$-полными в иерархии Клини–Мостовского (и следовательно, принадлежат тьюринговой степени неразрешимости $0^{(3)}$) для алгебр одноместных частично рекурсивных функций с различными сигнатурами, содержащими операцию суперпозиции. Множество $P_\text{Э}(A)$ является $\Pi_4$-полным для алгебры $A$ тех же функций со слабыми сигнатурами (включающими только сложение или обращение функций). Множество $P_\text{К}(B)$ является $\Sigma_2$-полным для алгебры $B$ примитивно рекурсивных функций с операциями суперпозиции, суммирования и итерации. Библиогр. 11 назв.