Computable enumeration and the problem of repetition
Stephan Wehner · Summit (Simon Fraser University) · 1995
The thesis is concerned with the question of characterizing those computably enumerable (c.e.) classes of computably enumerable sets which have a computable enumeration without repetition (an injective enumeration). This problem can be traced back to 1958, when Friedberg proved that the class of all computably enumerable sets can be injectively enumerated. We go beyond the scope of the literature by extending the study to the problem of characterizing the c.e. classes which are c.e. with a bounded number of repetitions and with finite repetitions. An investigation of the question restricted to classes of cofinite sets leads to a satisfying answer in a special case but demonstrates the difficulties of the general problem. The property of a class of being c.e. with at most finite repetitions is shown to behave more naturally than injective enumerability. We prove an extension theorem with a characterization as a corollary. We also show that the corresponding statement does not hold for t...