SOME EFFECTIVELY INFINITE CLASSES OF ENUMERATIONS

Citation
S. Goncharov et al., SOME EFFECTIVELY INFINITE CLASSES OF ENUMERATIONS, Annals of pure and applied Logic, 60(3), 1993, pp. 207-235
Citations number
12
Categorie Soggetti
Mathematics, Pure",Mathematics,Mathematics,Mathematics
ISSN journal
01680072
Volume
60
Issue
3
Year of publication
1993
Pages
207 - 235
Database
ISI
SICI code
0168-0072(1993)60:3<207:SEICOE>2.0.ZU;2-2
Abstract
This research partially answers the question raised by Goncharov about the size of the class of positive elements of a Roger's semilattice. We introduce a notion of effective infinity of classes of computable e numerations. Then, using finite injury priority method, we prove five theorems which give sufficient conditions to be effectively infinite f or classes of all enumerations without repetitions, positive undecidab le enumerations, negative undecidable enumerations and all computable enumerations of a family of r.e. sets. These theorems permit to streng then the results of Pour-El, Pour-El and Howard, Ershov and Khutoretsk ii about existence of enumerations without repetitions and positive un decidable enumerations.