Об алгоритмической неразрешимости распознавания $A$-полноты для ограниченно-детерминированных функций

Рассматривается функциональная система $P$, элементами которой являются отображения, осуществляемые так называемыми конечными автоматами, ограниченно-детерминированные функции (о.-д. функции), а операциями — операции суперпозиции. Система $\mathfrak{M}$ о.-д. функций называется $A$-полной, если для любой о.-д. функции и для всякого натурального $\tau>0$ из о.-д. функции системы $\mathfrak{M}$ с помощью операций суперпозиции можно получить о.-д. функцию, совпадающую с заданной на словах длины $\tau$. Возникает вопрос: существует ли алгоритм для распознавания $A$-полноты произвольной конечной системы о.-д. функции? Показывается, что такого алгоритма не существует. Библ. 4 назв.