
Accession Number : AD0773386
Title : On Subcreative Sets and SReducibility,
Corporate Author : CALIFORNIA UNIV IRVINE DEPT OF MATHEMATICS
Personal Author(s) : Gill,John T. ; Morris,Paul H.
Report Date : JUL 1973
Pagination or Media Count : 26
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 Sreducibility, 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 qcylindrification is an orderpreserving map from the r.e. Tdegrees to the r.e. Sdegrees. Consequently, Tcomplete sets are precisely the r.e. sets whose qcylindrifications are Scomplete. (Author)
Descriptors : *Set theory, *Recursive functions, Computations, Theorems
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE