An incomplete set of shortest descriptions

• Verfasst von: Stephan, Frank [VerfasserIn]
• Verfasst von: Teutsch, Jason [VerfasserIn]
• Titel: An incomplete set of shortest descriptions
• Verf.angabe: Frank Stephan and Jason Teutsch
• E-Jahr: 2014
• Jahr: 12 March 2014
• Jahr des Originals: 2012
• Umfang: 17 S.
• Fussnoten: Published online by Cambridge University Press: 12 March 2014 ; Gesehen am 26.08.2020
• Titel Quelle: Enthalten in: The journal of symbolic logic
• Ort Quelle: Cambridge : Cambridge Univ. Press, 1936
• Jahr Quelle: 2012
• Band/Heft Quelle: 77(2012), 1, Seite 291-307
• ISSN Quelle: 1943-5886
• DOI: doi:10.2178/jsl/1327068704
• Datenträger: Online-Ressource
• Sprache: eng
• K10plus-PPN: 1572580305

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.