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

Descripción completa

Detalles Bibliográficos
Autores principales: Downey, Rodney G, Ng, Keng Meng, Solomon, Reed
Lenguaje:eng
Publicado: American Mathematical Society 2020
Materias:
XX
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