Об универсальных нумерациях обобщенно вычислимых семейств

Аннотация

В работе исследуется вопросы существования универсальных обобщенновычислимых нумерации различных семейтв множеств и всюду определенных функций. Было известно, что для любого множество A такого, что ∅ 0 ≤T A, конечное семейство A -в.п. множеств S имеет A -вычислимую универсальную нумерацию тогда и только тогда, когда S содержит наименьшее по включению множество. Данный критерий не верно для бесконечных семейств. Для любого множества A существует бесконечное A-вычислимое семейство множеств S без наименьшего по включению элемента имеющий A-вычислимую универсальную нумерацию, более того в семействе S все элементы попарно не пересекаются. Если A — гипериммунное множество, тогда A-вычислимое семейство F всюду определенных функций содержащий не менее двух элементов не имеет универсальной A-вычислимой нумерации. А если degT (A) гипериммунно-свободно, тогда каждое A-вычислимое конечное семейство всюду определенных функций имеет A-вычислимую универсальную нумерацию. В данной работе показывается, что любое бесконечное эффективно дискретное семейство множеств с гипериммунно-свободным оракулом A имеет A-вычислимую универсальную нумерацию. Также доказывается, что если семейство S содержит все ко-конечные множества и не содержит хотябы один ко-в.п. множество, тогда данное семейство не имеет универсальную Σ −1 2 -вычислимую нумерацию