Об аппроксимации классов сведения УИП разрешимыми классами

Рассматриваются предваренные формулы УИП; одинаковыми считаются все формулы, получающиеся друг из друга переименованиями предметных и предикатных переменных и вычеркиванием фиктивных кванторов. Длиной формулы называется количество вхождений атомарных формул; $|M^{(n)}|$ обозначает количество тех формул множества $M$, которые имеют длину $n$. $M$ называется аппроксимируемым по выводимости, если существует алгорифм, который по каждому положительному $\varepsilon$, выдает разрешимое множество формул $N$ и число $n_0$ такие что для всех $n>n_0|N^{(n)}|/|M^{(n)}|>1-\varepsilon$. Число $\alpha$ называется числом выводимости класса формул $A$, если последовательность
$$ \frac{|\widetilde A^{(n)}|}{|A^{(n)}|},\quad n=1,2,3,\dots, $$
где $\widetilde A$ – множество выводимых формул из $A$, эффективно сходится к $\alpha$.
Для ряда известных классов сведения УИП найдено число выводимости или, по крайней мере, доказана аппроксимируемость. Библ. 2.