Sequences having an effective fixed-point property

Author:
T. H. Payne

Journal:
Trans. Amer. Math. Soc. **165** (1972), 227-237

MSC:
Primary 02F25

DOI:
https://doi.org/10.1090/S0002-9947-1972-0389560-4

MathSciNet review:
0389560

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let be any function whose domain is the set *N* of all natural numbers. A subset *B* of *N precompletes* the sequence if and only if for every partial recursive function (p.r.f.) there is a recursive function *f* such that extends and . An object *e* in the range of completes if and only if precompletes . 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 of an arbitrary function *F* defined on the p.r.f.'s with a fixed standard enumeration 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 and *S* and *T* are r.e. sets such that and , then precompletes .

**[1]**J. P. Cleave,*Creative functions*, Z. Math. Logik Grundlagen Math.**7**(1961), 205-212. MR**25**#3829. MR**0140409 (25:3829)****[2]**A. H. Lachlan,*Standard classes of recursively enumerable sets*, Z. Math. Logik Grundlagen Math.**10**(1964), 23-42. MR**28**#4994. MR**0161790 (28:4994)****[3]**-,*On the indexing of classes of recursively enumerable sets*, J. Symbolic Logic**31**(1966), 10-22. MR**34**#2451. MR**0202589 (34:2451)****[4]**A. I. Mal'cev,*Totally enumerated sets*, Algebra i Logika Sem.**2**(1963), 4-29. (Russian) MR**34**#1179. MR**0201295 (34:1179)****[5]**-,*On the theory of computable families of objects*, Algebra i Logika Sem.**3**(1964), 5-31. (Russian) MR**34**#48. MR**0200149 (34:48)****[6]**J. Myhill,*Creative sets*, Z. Math. Logik Grundlagen Math.**1**(1955), 97-108. MR**17**,118. MR**0071379 (17:118g)****[7]**W. E. Ritter,*Notation systems and an effective fixed point property*, Proc. Amer. Math. Soc.**17**(1966), 390-395. MR**34**#1181. MR**0201297 (34:1181)****[8]**H. Rogers, Jr.,*Gödel numberings of partial recursive functions*, J. Symbolic Logic**23**(1958), 331-341. MR**21**#2585. MR**0103821 (21:2585)****[9]**-,*On universal functions*, Proc. Amer. Math. Soc.**16**(1965), 39-44. MR**30**#1932. MR**0171705 (30:1932)****[10]**-,*Theory of recursive functions and effective computability*, McGraw-Hill, New York, 1967. MR**37**#61. MR**0224462 (37:61)****[11]**R. M. Smullyan,*Theory of formal systems*, Ann. Math. Studies, no. 47, Princeton Univ. Press, Princeton, N. J., 1961. MR**22**#12042. MR**0152429 (27:2409)**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
02F25

Retrieve articles in all journals with MSC: 02F25

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1972-0389560-4

Keywords:
Precompleted sequence,
completed sequence,
effective fixed-point property,
recursive isomorphism,
recursive reduction,
standard sequence,
indexing,
universal sequence,
creative function,
universal function

Article copyright:
© Copyright 1972
American Mathematical Society