Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Transactions of the ...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article
Data sources: zbMATH Open
Transactions of the American Mathematical Society
Article . 1972 . Peer-reviewed
Data sources: Crossref
Transactions of the American Mathematical Society
Article . 1972 . Peer-reviewed
Data sources: Crossref
versions View all 3 versions
addClaim

Sequences Having an Effective Fixed-Point Property

Sequences having an effective fixed-point property
Authors: Payne, T. H.;

Sequences Having an Effective Fixed-Point Property

Abstract

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.

Keywords

Recursively (computably) enumerable sets and degrees, Other degrees and reducibilities in computability and recursion theory, Recursive functions and relations, subrecursive hierarchies

  • BIP!
    Impact byBIP!
    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
Powered by OpenAIRE graph
Found an issue? Give us feedback
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).
BIP!Citations provided by BIP!
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.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
bronze
Beta
sdg_colorsSDGs:
Related to Research communities