Please use this identifier to cite or link to this item:
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.
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
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.


checked on May 18, 2018

Page view(s)

checked on May 11, 2018

Google ScholarTM



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