Minimal weak truth table degrees and computably enumerable Turing degrees

Minimal weak truth table degrees and computably enumerable Turing degrees / Rodney G. Downey, Keng Meng Ng, Reed Solomon.

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 we...

Full description

Saved in:
Bibliographic Details
Main Authors: Downey, R. G. (Rod G.) (Author), Ng, Keng Meng (Author), Solomon, Reed (Author)
Format: eBook
Language:English
Published: Providence, RI : American Mathematical Society, [2020].
Series:Memoirs of the American Mathematical Society ; no. 1284.
Subjects:
Unsolvability (Mathematical logic)
Recursively enumerable sets.
Computable functions.
Funciones computables
Teoría de conjuntos
Computable functions
Recursively enumerable sets
Mathematical logic and foundations > Computability and recursion theory > Recursively (computably) enumerable sets and degrees.
Mathematical logic and foundations > Computability and recursion theory > Other Turing degree structures.
Mathematical logic and foundations > Computability and recursion theory > Other degrees and reducibilities.
Online Access:Click for online access
Description
Summary: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, the.
Item Description:"May 2020" per title page.
Physical Description:1 online resource (vii, 90 pages) : illustrations.
Bibliography:Includes bibliographical references.
ISBN:9781470461379
1470461374
9781470461362
1470461366
Source of Description, Etc. Note:Description based on online resource; title from digital title page (viewed on July 31, 2020).

Similar Items