| Softcover ISBN: | 978-1-4704-4162-3 |
| Product Code: | MEMO/265/1284 |
| List Price: | $85.00 |
| MAA Member Price: | $76.50 |
| AMS Member Price: | $68.00 |
| eBook ISBN: | 978-1-4704-6136-2 |
| Product Code: | MEMO/265/1284.E |
| List Price: | $85.00 |
| MAA Member Price: | $76.50 |
| AMS Member Price: | $68.00 |
| Softcover ISBN: | 978-1-4704-4162-3 |
| eBook: ISBN: | 978-1-4704-6136-2 |
| Product Code: | MEMO/265/1284.B |
| List Price: | $170.00 $127.50 |
| MAA Member Price: | $153.00 $114.75 |
| AMS Member Price: | $136.00 $102.00 |
| Softcover ISBN: | 978-1-4704-4162-3 |
| Product Code: | MEMO/265/1284 |
| List Price: | $85.00 |
| MAA Member Price: | $76.50 |
| AMS Member Price: | $68.00 |
| eBook ISBN: | 978-1-4704-6136-2 |
| Product Code: | MEMO/265/1284.E |
| List Price: | $85.00 |
| MAA Member Price: | $76.50 |
| AMS Member Price: | $68.00 |
| Softcover ISBN: | 978-1-4704-4162-3 |
| eBook ISBN: | 978-1-4704-6136-2 |
| Product Code: | MEMO/265/1284.B |
| List Price: | $170.00 $127.50 |
| MAA Member Price: | $153.00 $114.75 |
| AMS Member Price: | $136.00 $102.00 |
-
Book DetailsMemoirs of the American Mathematical SocietyVolume: 265; 2020; 90 ppMSC: Primary 03
Two of the central concepts for the study of degree structures in computability theory are computably enumerable degrees and minimal degrees. For strong notions of reducibility, such as \(m\)-deducibility or truth table reducibility, it is possible for computably enumerable degrees to be minimal. For weaker notions of reducibility, such as weak truth table reducibility or Turing reducibility, it is not possible to combine these properties in a single degree. We consider how minimal weak truth table degrees interact with computably enumerable Turing degrees and obtain three main results. First, there are sets with minimal weak truth table degree which bound noncomputable computably enumerable sets under Turing reducibility. Second, no set with computable enumerable Turing degree can have minimal weak truth table degree. Third, no \(\Delta^0_2\) set which Turing bounds a promptly simple set can have minimal weak truth table degree.
-
Table of Contents
-
Chapters
-
1. Introduction
-
2. Informal Construction
-
3. Formal Construction
-
4. Limiting Results
-
-
Additional Material
-
RequestsReview Copy – for publishers of book reviewsPermission – for use of book, eBook, or Journal contentAccessibility – to request an alternate format of an AMS title
- Book Details
- Table of Contents
- Additional Material
- Requests
Two of the central concepts for the study of degree structures in computability theory are computably enumerable degrees and minimal degrees. For strong notions of reducibility, such as \(m\)-deducibility or truth table reducibility, it is possible for computably enumerable degrees to be minimal. For weaker notions of reducibility, such as weak truth table reducibility or Turing reducibility, it is not possible to combine these properties in a single degree. We consider how minimal weak truth table degrees interact with computably enumerable Turing degrees and obtain three main results. First, there are sets with minimal weak truth table degree which bound noncomputable computably enumerable sets under Turing reducibility. Second, no set with computable enumerable Turing degree can have minimal weak truth table degree. Third, no \(\Delta^0_2\) set which Turing bounds a promptly simple set can have minimal weak truth table degree.
-
Chapters
-
1. Introduction
-
2. Informal Construction
-
3. Formal Construction
-
4. Limiting Results
