Please use this identifier to cite or link to this item:
|Title:||An incomplete set of shortest descriptions|
|Authors:||Stephan, F. |
|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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on May 18, 2018
checked on May 11, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.