Minimal Weak Truth Table Degrees and Computably Enumerable Turing Degrees (Paperback)

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.

General

Imprint:	American Mathematical Society
Country of origin:	United States
Series:	Memoirs of the American Mathematical Society
Release date:	2021
Authors:	Rodney G. Downey • Keng Meng Ng • Reed Solomon
Dimensions:	254 x 178mm (L x W)
Format:	Paperback
Pages:	90
ISBN-13:	978-1-4704-4162-3
Categories:	Books > Science & Mathematics > Mathematics > Mathematical foundations > Mathematical logic Books > Science & Mathematics > Mathematics > Calculus & mathematical analysis > General
LSN:	1-4704-4162-4
Barcode:	9781470441623

Is the information for this product incomplete, wrong or inappropriate? Let us know about it.

Does this product have an incorrect or missing image? Send us a new image.

Is this product missing categories? Add more categories.

Review This Product

No reviews yet - be the first to create one!