Cargando…
Minimal weak truth table degrees and computably enumerable turing degrees
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...
Autores principales: | , , |
---|---|
Lenguaje: | eng |
Publicado: |
American Mathematical Society
2020
|
Materias: | |
Acceso en línea: | http://cds.cern.ch/record/2744816 |
_version_ | 1780968658081677312 |
---|---|
author | Downey, Rodney G Ng, Keng Meng Solomon, Reed |
author_facet | Downey, Rodney G Ng, Keng Meng Solomon, Reed |
author_sort | Downey, Rodney G |
collection | CERN |
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. 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. |
id | cern-2744816 |
institution | Organización Europea para la Investigación Nuclear |
language | eng |
publishDate | 2020 |
publisher | American Mathematical Society |
record_format | invenio |
spelling | cern-27448162021-04-21T16:44:53Zhttp://cds.cern.ch/record/2744816engDowney, Rodney GNg, Keng MengSolomon, ReedMinimal weak truth table degrees and computably enumerable turing degreesXXTwo 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.American Mathematical Societyoai:cds.cern.ch:27448162020 |
spellingShingle | XX Downey, Rodney G Ng, Keng Meng Solomon, Reed Minimal weak truth table degrees and computably enumerable turing degrees |
title | Minimal weak truth table degrees and computably enumerable turing degrees |
title_full | Minimal weak truth table degrees and computably enumerable turing degrees |
title_fullStr | Minimal weak truth table degrees and computably enumerable turing degrees |
title_full_unstemmed | Minimal weak truth table degrees and computably enumerable turing degrees |
title_short | Minimal weak truth table degrees and computably enumerable turing degrees |
title_sort | minimal weak truth table degrees and computably enumerable turing degrees |
topic | XX |
url | http://cds.cern.ch/record/2744816 |
work_keys_str_mv | AT downeyrodneyg minimalweaktruthtabledegreesandcomputablyenumerableturingdegrees AT ngkengmeng minimalweaktruthtabledegreesandcomputablyenumerableturingdegrees AT solomonreed minimalweaktruthtabledegreesandcomputablyenumerableturingdegrees |