Sequences having an effective fixed-point property
HTML articles powered by AMS MathViewer
- by T. H. Payne PDF
- Trans. Amer. Math. Soc. 165 (1972), 227-237 Request permission
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
- J. P. Cleave, Creative functions, Z. Math. Logik Grundlagen Math. 7 (1961), 205–212. MR 140409, DOI 10.1002/malq.19610071108
- A. H. Lachlan, Standard classes of recursively enumerable sets, Z. Math. Logik Grundlagen Math. 10 (1964), 23–42. MR 161790, DOI 10.1002/malq.19640100203
- A. H. Lachlan, On the indexing of classes of recursively enumerable sets, J. Symbolic Logic 31 (1966), 10–22. MR 202589, DOI 10.2307/2270617
- A. I. Mal′cev, Totally enumerated sets, Algebra i Logika Sem. 2 (1963), no. 2, 4–29 (Russian). MR 0201295
- A. I. Mal′cev, On the theory of computable families of objects, Algebra i Logika Sem. 3 (1964), no. 4, 5–31 (Russian). MR 0200149
- John Myhill, Creative sets, Z. Math. Logik Grundlagen Math. 1 (1955), 97–108. MR 71379, DOI 10.1002/malq.19550010205
- Willaim E. Ritter, Notation systems and an effective fixed point property, Proc. Amer. Math. Soc. 17 (1966), 390–395. MR 201297, DOI 10.1090/S0002-9939-1966-0201297-3
- Hartley Rogers Jr., Gödel numberings of partial recursive functions, J. Symbolic Logic 23 (1958), 331–341. MR 103821, DOI 10.2307/2964292
- Hartley Rogers Jr., On universal functions, Proc. Amer. Math. Soc. 16 (1965), 39–44. MR 171705, DOI 10.1090/S0002-9939-1965-0171705-4
- Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
- Raymond M. Smullyan, Theory of formal systems, Revised edition, Princeton University Press, Princeton, N. J., 1961. MR 0152429
Additional Information
- © Copyright 1972 American Mathematical Society
- 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