An incomplete set of shortest descriptions
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 numbe...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
12 March 2014
|
| In: |
The journal of symbolic logic
Year: 2012, Volume: 77, Issue: 1, Pages: 291-307 |
| ISSN: | 1943-5886 |
| DOI: | 10.2178/jsl/1327068704 |
| Online Access: | Verlag, Volltext: http://dx.doi.org/10.2178/jsl/1327068704 Verlag, Volltext: https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/an-incomplete-set-of-shortest-descriptions/5D221BE1DDA033208A8D215C8369C7CC 
|
| Author Notes: | Frank Stephan and Jason Teutsch |
| Summary: | 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 numbering. 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. |
|---|---|
| Item Description: | Published online by Cambridge University Press: 12 March 2014 Gesehen am 26.08.2020 |
| Physical Description: | Online Resource |
| ISSN: | 1943-5886 |
| DOI: | 10.2178/jsl/1327068704 |