Please use this identifier to cite or link to this item: https://doi.org/10.2178/jsl/1327068704
Title: An incomplete set of shortest descriptions
Authors: Stephan, F. 
Teutsch, J.
Issue Date: Mar-2012
Citation: Stephan, F., Teutsch, J. (2012-03). An incomplete set of shortest descriptions. Journal of Symbolic Logic 77 (1) : 291-307. ScholarBank@NUS Repository. https://doi.org/10.2178/jsl/1327068704
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 number-ing. 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. © 2012, Association for Symbolic Logic.
Source Title: Journal of Symbolic Logic
URI: http://scholarbank.nus.edu.sg/handle/10635/102839
ISSN: 00224812
DOI: 10.2178/jsl/1327068704
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

3
checked on May 18, 2018

Page view(s)

31
checked on May 11, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.