
doi: 10.2307/2272852
AbstractSubcreative sets, introduced by Blum, are known to coincide with the effectively speedable sets. Subcreative sets are shown to be the complete sets with respect to S-reducibility, a special case of Turing reducibility. Thus a set is effectively speedable exactly when it contains the solution to the halting problem in an easily decodable form. Several characterizations of subcreative sets are given, including the solution of an open problem of Blum, and are used to locate the subcreative sets with respect to the complete sets of other reducibilities. It is shown that q-cylindrification is an order-preserving map from the r.e. T-degrees to the r.e. S-degrees. Consequently, T-complete sets are precisely the r.e. sets whose q-cylindrifications are S-complete.
Recursively (computably) enumerable sets and degrees, Other degrees and reducibilities in computability and recursion theory
Recursively (computably) enumerable sets and degrees, Other degrees and reducibilities in computability and recursion theory
| 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). | 27 | |
| 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. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
