Buchumschlag

Analogues of Chaitinʼs Omega in the computably enumerable sets

We show that there are computably enumerable (c.e.) sets with maximum initial segment Kolmogorov complexity amongst all c.e. sets (with respect to both the plain and the prefix-free version of Kolmogorov complexity). These c.e. sets belong to the weak truth table degree of the halting problem, but n...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Hauptverfasser: Barmpalias, George (VerfasserIn) , Hölzl, Rupert (VerfasserIn) , Lewis, Andrew E. M. (VerfasserIn) , Merkle, Wolfgang (VerfasserIn)
Dokumenttyp: Article (Journal)
Sprache:Englisch
Veröffentlicht: 8 January 2013
In: Information processing letters
Year: 2013, Jahrgang: 113, Heft: 5, Pages: 171-178
ISSN:1872-6119
DOI:10.1016/j.ipl.2013.01.007
Online-Zugang:Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1016/j.ipl.2013.01.007
Verlag, lizenzpflichtig, Volltext: http://www.sciencedirect.com/science/article/pii/S0020019013000136
Volltext
Verfasserangaben:G. Barmpalias, R. Hölzl, A.E.M. Lewis, W. Merkle
Beschreibung
Zusammenfassung:We show that there are computably enumerable (c.e.) sets with maximum initial segment Kolmogorov complexity amongst all c.e. sets (with respect to both the plain and the prefix-free version of Kolmogorov complexity). These c.e. sets belong to the weak truth table degree of the halting problem, but not every weak truth table complete c.e. set has maximum initial segment Kolmogorov complexity. Moreover, every c.e. set with maximum initial segment prefix-free complexity is the disjoint union of two c.e. sets with the same property; and is also the disjoint union of two c.e. sets of lesser initial segment complexity.
Beschreibung:Gesehen am 03.11.2020
Beschreibung:Online Resource
ISSN:1872-6119
DOI:10.1016/j.ipl.2013.01.007

Ähnliche Einträge