On the Turing degrees of minimal index sets

Annals of Pure and Applied Logic 148 (1):63-80 (2007)

Abstract

We study generalizations of shortest programs as they pertain to Schaefer’s problem. We identify sets of -minimal and -minimal indices and characterize their truth-table and Turing degrees. In particular, we show , , and that there exists a Kolmogorov numbering ψ satisfying both and . This Kolmogorov numbering also achieves maximal truth-table degree for other sets of minimal indices. Finally, we show that the set of shortest descriptions, , is 2-c.e. but not co-2-c.e. Some open problems are left for the reader

Download options

PhilArchive



    Upload a copy of this work     Papers currently archived: 72,805

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Analytics

Added to PP
2013-12-30

Downloads
17 (#642,193)

6 months
1 (#386,499)

Historical graph of downloads
How can I increase my downloads?

References found in this work

A Guided Tour of Minimal Indices and Shortest Descriptions.Marcus Schaefer - 1998 - Archive for Mathematical Logic 37 (8):521-548.
Bounded Immunity and Btt‐Reductions.Stephen Fenner & Marcus Schaefer - 1999 - Mathematical Logic Quarterly 45 (1):3-21.
On Btt-Degrees of Sets of Minimal Numbers in Gödel Numberings.Jefim Kinber - 1977 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 23 (13-15):201-212.
On Btt‐Degrees of Sets of Minimal Numbers in Gödel Numberings.Jefim Kinber - 1976 - Mathematical Logic Quarterly 23 (13‐15):201-212.

View all 9 references / Add more references

Citations of this work

An Incomplete Set of Shortest Descriptions.Frank Stephan & Jason Teutsch - 2012 - Journal of Symbolic Logic 77 (1):291-307.

Add more citations

Similar books and articles

Immunity and Hyperimmunity for Sets of Minimal Indices.Frank Stephan & Jason Teutsch - 2008 - Notre Dame Journal of Formal Logic 49 (2):107-125.
Wtt-Degrees and T-Degrees of R.E. Sets.Michael Stob - 1983 - Journal of Symbolic Logic 48 (4):921-930.
Kleene Index Sets and Functional M-Degrees.Jeanleah Mohrherr - 1983 - Journal of Symbolic Logic 48 (3):829-840.
On a Problem of Ishmukhametov.Chengling Fang, Guohua Wu & Mars Yamaleev - 2013 - Archive for Mathematical Logic 52 (7-8):733-741.
The Degrees of Conditional Problems.Su Gao - 1994 - Journal of Symbolic Logic 59 (1):166-181.
A Hyperimmune Minimal Degree and an ANR 2-Minimal Degree.Mingzhong Cai - 2010 - Notre Dame Journal of Formal Logic 51 (4):443-455.
On the Symmetric Enumeration Degrees.Charles M. Harris - 2007 - Notre Dame Journal of Formal Logic 48 (2):175-204.
Turing Degrees and Many-One Degrees of Maximal Sets.Manuel Lerman - 1970 - Journal of Symbolic Logic 35 (1):29-40.
Benign Cost Functions and Lowness Properties.Noam Greenberg & André Nies - 2011 - Journal of Symbolic Logic 76 (1):289 - 312.
Maximal Chains in the Turing Degrees.C. T. Chong & Liang Yu - 2007 - Journal of Symbolic Logic 72 (4):1219 - 1227.