An incomplete set of shortest descriptions

Journal of Symbolic Logic 77 (1):291-307 (2012)
  Copy   BIBTEX

Abstract

The truth-table degree of the set of shortest programs remains an outstanding problem in recursion theory. We examine two related sets, the set of shortest descriptions and the set of domain-random strings, and show that the truth-table degrees of these sets depend on the underlying acceptable numbering. We achieve some additional properties for the truth-table incomplete versions of these sets, namely retraceability and approximability. We give priority-free constructions of bounded truth-table chains and bounded truth-table antichains inside the truth-table complete degree by identifying an acceptable set of domain-random strings within each degree

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,310

External links

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

Through your library

Similar books and articles

Incomplete Descriptions.Marga Reimer - 1992 - Erkenntnis 37 (3):347 - 363.
Descriptions: Points of Reference.Kent Bach - 2004 - In Marga Reimer & Anne Bezuidenhout (eds.), Descriptions and Beyond. Clarendon Press. pp. 189-229.
Essentially Incomplete Descriptions.Carlo Penco - 2010 - European Journal of Analytic Philosophy 6 (2):47 - 66.
The Real Distinction Between Descriptions and Indexicals.Manuel García-Carpintero - 2005 - Teorema: International Journal of Philosophy 24 (3):49-74.
Assertion and Incomplete Definite Descriptions.Nathan U. Salmon - 1982 - Philosophical Studies 42 (1):37--45.
Incomplete Definite Descriptions.Scott Soames - 1986 - Notre Dame Journal of Formal Logic 27 (3):349--375.
Almost Weakly 2-Generic Sets.Stephen A. Fenner - 1994 - Journal of Symbolic Logic 59 (3):868-887.

Analytics

Added to PP
2012-01-21

Downloads
37 (#312,651)

6 months
1 (#415,900)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers.Piergiorgio Odifreddi - 1989 - Sole Distributors for the Usa and Canada, Elsevier Science Pub. Co..
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 8 references / Add more references