Status: Bibliographieeintrag
Standort: ---
Exemplare:
---
| Online-Ressource |
Verfasst von: | Stephan, Frank [VerfasserIn]  |
| Teutsch, Jason [VerfasserIn]  |
Titel: | An incomplete set of shortest descriptions |
Verf.angabe: | Frank Stephan and Jason Teutsch |
E-Jahr: | 2014 |
Jahr: | 12 March 2014 |
Jahr des Originals: | 2012 |
Umfang: | 17 S. |
Fussnoten: | Published online by Cambridge University Press: 12 March 2014 ; Gesehen am 26.08.2020 |
Titel Quelle: | Enthalten in: The journal of symbolic logic |
Ort Quelle: | Cambridge : Cambridge Univ. Press, 1936 |
Jahr Quelle: | 2012 |
Band/Heft Quelle: | 77(2012), 1, Seite 291-307 |
ISSN Quelle: | 1943-5886 |
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 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. |
DOI: | doi:10.2178/jsl/1327068704 |
URL: | Bitte beachten Sie: Dies ist ein Bibliographieeintrag. Ein Volltextzugriff für Mitglieder der Universität besteht hier nur, falls für die entsprechende Zeitschrift/den entsprechenden Sammelband ein Abonnement besteht oder es sich um einen OpenAccess-Titel handelt.
Volltext ; Verlag: http://dx.doi.org/10.2178/jsl/1327068704 |
| Volltext: https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/an-incomplete-set-of-shortest-descriptions/5D2 ... |
| DOI: https://doi.org/10.2178/jsl/1327068704 |
Datenträger: | Online-Ressource |
Sprache: | eng |
K10plus-PPN: | 1572580305 |
Verknüpfungen: | → Zeitschrift |
¬An¬ incomplete set of shortest descriptions / Stephan, Frank [VerfasserIn]; 12 March 2014 (Online-Ressource)
68248889