DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
Accession Number:
AD0773386
Title:
On Subcreative Sets and S-Reducibility,
Corporate Author:
CALIFORNIA UNIV IRVINE DEPT OF MATHEMATICS
Report Date:
1973-07-01
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
Supplementary Note:
Prepared in cooperation with Stanford Univ., Calif. Dept. of Electrical Engineering Contract N00014-67-A-0112-0044. Sponsored in part by Grant NSF-GJ-708.
Pages:
0026
Contract Number:
AF-AFOSR-2118-71
File Size:
0.00MB
