Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Remote Access
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)


Sequences having an effective fixed-point property

Author: T. H. Payne
Journal: Trans. Amer. Math. Soc. 165 (1972), 227-237
MSC: Primary 02F25
MathSciNet review: 0389560
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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

References [Enhancements On Off] (What's this?)

Similar Articles

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

Retrieve articles in all journals with MSC: 02F25

Additional Information

PII: S 0002-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

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia