ON UNIVERSAL NUMBERINGS OF GENERALIZED COMPUTABLE FAMILIES
Issakhov A.A. Kalmurzayev B.S. Rakymzhankyzy F.
31 March 2022al-Farabi Kazakh State National University
KazNU Bulletin. Mathematics, Mechanics, Computer Science Series
2022#113Issue 125 - 32 pp.
The paper investigates the existence of universal generalized computable numberings of different families of sets and total functions. It was known that for every set A such that (Formula Presented), a finite family S of A-c.e. sets has an A-computable universal numbering if and only if S contains the least set under inclusion. This criterion is not true for infinite families. For any set A there is an infinite A-computable family of sets S without the least element under inclusion that has an A-computable universal numbering; moreover, the family S consist pairwise not intersect sets. If A is a hyperimmune set, then an A-computable family F of total functions which contains at least two elements has no A-computable universal numbering. And if degT (A) is hyperimmune-free, then every A-computable finite family of total functions has an A-computable universal numbering. In this paper for a hyperimmune-free oracle A we show that any infinite effectively discrete family of sets has an A-computable universal numbering. It is also proved that if family S contains all co-finite sets and does not contain at least one co-c.e. set, then this family has no (Formula Presented) -computable universal numbering.
computable numbering , Ershov hierarchy , hyperimmune set , Rogers semilattice , universal numbering
Text of the article Перейти на текст статьи
Kazakh-British Technical University, Almaty, Kazakhstan
Kazakh-British Technical University
10 лет помогаем публиковать статьи Международный издатель
Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026