
Let a be any function whose domain is the set N of all natural numbers. A subset B of Nprecompletes the sequence a if and only if for every partial recursive function (p.r.f.) b there is a recursive function f such that af extends ao and f [N-Dom 0] ebB. An object e in the range of a completes a if and only if a -I[{e}] precompletes a. The theory of completed sequences was introduced by A. I. Mal'cev as an abstraction of the theory of standard enumerations. In this paper several results are obtained by refining and extending his methods. It is shown that a sequence is precompleted (by some B) if and only if it has a certain effective fixed-point property. The completed sequences are characterized, up to a recursive permutation, as the composition Frp of an arbitrary function F defined on the p.r.f.'s with a fixed standard enumeration p of the p.r.f.'s. A similar characterization is given for the precompleted sequences. The standard sequences are characterized as the precompleted indexings which satisfy a simple uniformity condition. Several further properties of completed and precompleted sequences are presented, for example, if B precompletes a and S and Tare r.e. sets such that a f[a[S]] # Nand a '[a[T]] N, then B-(S U T) precompletes a. 1. Preliminaries. Let Ax, y [ ] be a recursive pairing function which is monotonic in each of its arguments, and let p and g denote the corresponding projection functions, A [x] and A [y], respectively. For any set Sc: N, {x I E S} is called the ith row of S and is denoted by St. The sequence Ai [St] is called the row sequence of S and is denoted by S*. A sequence is said to be recursively enumerable (r.e.) if and only if it is the row sequence of an r.e. set. Every partial function 0 will be identified with its graph { I +(x) is defined and equals y}; hence b*(i) = ot = {+(i)} when i E Dom b, and 0*(i) = oi = 0 otherwise. (Thus b is a p.r.f. if and only if 0* is an r.e. sequence of sets of cardinality less than two.) A p.r.f. b is called a selector for a set Sc N if and only if 0bcS and Dom b {i E N I Si =A 0 }. Note that if 8 is a partial function on N and b is a selector for Received by the editors January 30, 1970 and, in revised form, February 22, 1970. AMS 1969 subject classifications. Primary 0270; Secondary 0274.
Recursively (computably) enumerable sets and degrees, Other degrees and reducibilities in computability and recursion theory, Recursive functions and relations, subrecursive hierarchies
Recursively (computably) enumerable sets and degrees, Other degrees and reducibilities in computability and recursion theory, Recursive functions and relations, subrecursive hierarchies
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
