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
5
checked on May 25, 2022
WEB OF SCIENCETM
Citations
5
checked on May 25, 2022
Page view(s)
154
checked on May 12, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.