Sequences having an effective fixedpoint property
Author:
T. H. Payne
Journal:
Trans. Amer. Math. Soc. 165 (1972), 227237
MSC:
Primary 02F25
MathSciNet review:
0389560
Fulltext PDF Free Access
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 fixedpoint 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 0140409
(25 #3829)
 [2]
A.
H. Lachlan, Standard classes of recursively enumerable sets,
Z. Math. Logik Grundlagen Math. 10 (1964), 23–42. MR 0161790
(28 #4994)
 [3]
A.
H. Lachlan, On the indexing of classes of recursively enumerable
sets, J. Symbolic Logic 31 (1966), 10–22. MR 0202589
(34 #2451)
 [4]
A.
I. Mal′cev, Totally enumerated sets, Algebra i Logika
Sem. 2 (1963), no. 2, 4–29 (Russian). MR 0201295
(34 #1179)
 [5]
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
(34 #48)
 [6]
John
Myhill, Creative sets, Z. Math. Logik Grundlagen Math.
1 (1955), 97–108. MR 0071379
(17,118g)
 [7]
Willaim
E. Ritter, Notation systems and an effective
fixed point property, Proc. Amer. Math.
Soc. 17 (1966),
390–395. MR 0201297
(34 #1181), http://dx.doi.org/10.1090/S00029939196602012973
 [8]
Hartley
Rogers Jr., Gödel numberings of partial recursive
functions, J. Symb. Logic 23 (1958), 331–341.
MR
0103821 (21 #2585)
 [9]
Hartley
Rogers Jr., On universal functions, Proc. Amer. Math. Soc. 16 (1965), 39–44. MR 0171705
(30 #1932), http://dx.doi.org/10.1090/S00029939196501717054
 [10]
Hartley
Rogers Jr., Theory of recursive functions and effective
computability, McGrawHill Book Co., New York, 1967. MR 0224462
(37 #61)
 [11]
Raymond
M. Smullyan, Theory of formal systems, Revised edition,
Princeton University Press, Princeton, N. J., 1961. MR 0152429
(27 #2409)
 [1]
 J. P. Cleave, Creative functions, Z. Math. Logik Grundlagen Math. 7 (1961), 205212. MR 25 #3829. MR 0140409 (25:3829)
 [2]
 A. H. Lachlan, Standard classes of recursively enumerable sets, Z. Math. Logik Grundlagen Math. 10 (1964), 2342. MR 28 #4994. MR 0161790 (28:4994)
 [3]
 , On the indexing of classes of recursively enumerable sets, J. Symbolic Logic 31 (1966), 1022. MR 34 #2451. MR 0202589 (34:2451)
 [4]
 A. I. Mal'cev, Totally enumerated sets, Algebra i Logika Sem. 2 (1963), 429. (Russian) MR 34 #1179. MR 0201295 (34:1179)
 [5]
 , On the theory of computable families of objects, Algebra i Logika Sem. 3 (1964), 531. (Russian) MR 34 #48. MR 0200149 (34:48)
 [6]
 J. Myhill, Creative sets, Z. Math. Logik Grundlagen Math. 1 (1955), 97108. 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), 390395. MR 34 #1181. MR 0201297 (34:1181)
 [8]
 H. Rogers, Jr., Gödel numberings of partial recursive functions, J. Symbolic Logic 23 (1958), 331341. MR 21 #2585. MR 0103821 (21:2585)
 [9]
 , On universal functions, Proc. Amer. Math. Soc. 16 (1965), 3944. MR 30 #1932. MR 0171705 (30:1932)
 [10]
 , Theory of recursive functions and effective computability, McGrawHill, 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)
Similar Articles
Retrieve articles in Transactions of the American Mathematical Society
with MSC:
02F25
Retrieve articles in all journals
with MSC:
02F25
Additional Information
DOI:
http://dx.doi.org/10.1090/S00029947197203895604
PII:
S 00029947(1972)03895604
Keywords:
Precompleted sequence,
completed sequence,
effective fixedpoint property,
recursive isomorphism,
recursive reduction,
standard sequence,
indexing,
universal sequence,
creative function,
universal function
Article copyright:
© Copyright 1972 American Mathematical Society
