Эффективно бесконечные классы нумераций и теоремы о неподвижной точке

Эффективно бесконечные классы нумераций

Аннотация

В статье получено достаточное условие эффективной бесконечности классов полных и предполных нумераций, а также нумераций, удовлетворяющих теореме рекурсии, вычислимых семейств. Также получено достаточное условие эффективной бесконечности классов непредполных нумераций вычислимых семейств, удовлетворяющих теореме рекурсии. Этим условиям удовлетворяют семейства всех в.п. множеств и графиков всех частично вычислимых функций. Для конечных семейств в.п. множеств доказан критерий эффективной бесконечности классов их нумераций, удовлетворяющих теореме рекурсии. Наконец, установлено, что классы полных и предполных нумераций конечных семейств в.п. множеств не являются эффективно бесконечными.