
doi: 10.1007/bf00966561
For one partial function to be partial recursive in another requires a partial recursive operator; this relation yields the partial degrees [see \textit{H. Rogers jun.}, Theory of recursive functions and effective computability. Maidenhead, Berksh.: McGraw-Hill Publishing Company, Ltd. (1967; Zbl 0183.01401)]. The stronger requirement of a recursive operator, one defined on all partial functions of one variable, gives the relation of recursive reducibility between partial functions; this yields the \(r\)-degrees, a refinement of the partial degrees. Like the partial degrees, the \(r\)-degrees (under the ordering induced by recursive reducibility) form an upper semilattice that is not a lattice. Some of the paper's results: There are uncountably many (using Zorn's Lemma) pairwise incomparable partial degrees each of which contains only one \(r\)-degree (alternatively, each of which contains more than one \(r\)-degree). Every partial degree with a nonrecursive total function contains more than one \(r\)-degree. Any partial degree has as its minimal \(r\)-degree that one consisting of those partial functions that can be extended to partial recursive functions. With the help of a theorem of Sacks: For any countable partial ordering \(\pi\), there are uncountably many partial degrees \(\underline{d}\) with the property that \(\pi\) is isomorphically embeddable in the \(r\)-degrees in \(\underline{d}\).
Other degrees and reducibilities in computability and recursion theory, Recursive functions and relations, subrecursive hierarchies
Other degrees and reducibilities in computability and recursion theory, Recursive functions and relations, subrecursive hierarchies
| 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). | 1 | |
| 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 |
