On Subcreative Sets and S-Reducibility,
Abstract
Subcreative 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. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1973
- Accession Number
- AD0773386
Entities
People
- John T. Gill
- Paul H. Morris
Organizations
- University of California, Irvine