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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.