
Minimal Weak Truth Table Degrees and Computably Enumerable Turing Degrees
American Mathematical Society (Publisher)
Published on 30. January 2021
Book
Paperback/Softback
90 pages
978-1-4704-4162-3 (ISBN)
Description
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.
This book considers 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.
This book considers 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.
More details
Series
Language
English
Place of publication
Providence
United States
Target group
Professional and scholarly
Dimensions
Height: 254 mm
Width: 178 mm
Weight
195 gr
ISBN-13
978-1-4704-4162-3 (9781470441623)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Persons
Rodney G. Downey, Victoria University of Wellington, New Zealand.
Keng Meng NgNanyang Technological University, Singapore.
Reed Solomon, University of Connecticut, Storrs, CT USA.
Keng Meng NgNanyang Technological University, Singapore.
Reed Solomon, University of Connecticut, Storrs, CT USA.