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...
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| 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 
|
| Verfasserangaben: | G. Barmpalias, R. Hölzl, A.E.M. Lewis, W. Merkle |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1737678411 | ||
| 003 | DE-627 | ||
| 005 | 20220819011426.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 201103s2013 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1016/j.ipl.2013.01.007 |2 doi | |
| 035 | |a (DE-627)1737678411 | ||
| 035 | |a (DE-599)KXP1737678411 | ||
| 035 | |a (OCoLC)1341375275 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 28 |2 sdnb | ||
| 100 | 1 | |a Barmpalias, George |e VerfasserIn |0 (DE-588)1205828605 |0 (DE-627)1691542067 |4 aut | |
| 245 | 1 | 0 | |a Analogues of Chaitinʼs Omega in the computably enumerable sets |c G. Barmpalias, R. Hölzl, A.E.M. Lewis, W. Merkle |
| 264 | 1 | |c 8 January 2013 | |
| 300 | |a 8 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Gesehen am 03.11.2020 | ||
| 520 | |a 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. | ||
| 650 | 4 | |a Completeness | |
| 650 | 4 | |a Computably enumerable sets | |
| 650 | 4 | |a Kolmogorov complexity | |
| 650 | 4 | |a Theory of computation | |
| 700 | 1 | |a Hölzl, Rupert |e VerfasserIn |0 (DE-588)143327291 |0 (DE-627)704454890 |0 (DE-576)336473923 |4 aut | |
| 700 | 1 | |a Lewis, Andrew E. M. |e VerfasserIn |4 aut | |
| 700 | 1 | |a Merkle, Wolfgang |e VerfasserIn |0 (DE-588)1049898400 |0 (DE-627)782852831 |0 (DE-576)40388201X |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |t Information processing letters |d Amsterdam [u.a.] : Elsevier, 1971 |g 113(2013), 5, Seite 171-178 |h Online-Ressource |w (DE-627)265783771 |w (DE-600)1466301-6 |w (DE-576)074890921 |x 1872-6119 |7 nnas |a Analogues of Chaitinʼs Omega in the computably enumerable sets |
| 773 | 1 | 8 | |g volume:113 |g year:2013 |g number:5 |g pages:171-178 |g extent:8 |a Analogues of Chaitinʼs Omega in the computably enumerable sets |
| 856 | 4 | 0 | |u https://doi.org/10.1016/j.ipl.2013.01.007 |x Verlag |x Resolving-System |z lizenzpflichtig |3 Volltext |
| 856 | 4 | 0 | |u http://www.sciencedirect.com/science/article/pii/S0020019013000136 |x Verlag |z lizenzpflichtig |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20201103 | ||
| 993 | |a Article | ||
| 994 | |a 2013 | ||
| 998 | |g 1049898400 |a Merkle, Wolfgang |m 1049898400:Merkle, Wolfgang |d 110000 |d 110300 |e 110000PM1049898400 |e 110300PM1049898400 |k 0/110000/ |k 1/110000/110300/ |p 4 |y j | ||
| 999 | |a KXP-PPN1737678411 |e 379175243X | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"recId":"1737678411","language":["eng"],"type":{"media":"Online-Ressource","bibl":"article-journal"},"note":["Gesehen am 03.11.2020"],"person":[{"display":"Barmpalias, George","roleDisplay":"VerfasserIn","role":"aut","family":"Barmpalias","given":"George"},{"roleDisplay":"VerfasserIn","display":"Hölzl, Rupert","role":"aut","family":"Hölzl","given":"Rupert"},{"roleDisplay":"VerfasserIn","display":"Lewis, Andrew E. M.","role":"aut","family":"Lewis","given":"Andrew E. M."},{"given":"Wolfgang","family":"Merkle","role":"aut","roleDisplay":"VerfasserIn","display":"Merkle, Wolfgang"}],"title":[{"title_sort":"Analogues of Chaitinʼs Omega in the computably enumerable sets","title":"Analogues of Chaitinʼs Omega in the computably enumerable sets"}],"relHost":[{"physDesc":[{"extent":"Online-Ressource"}],"origin":[{"dateIssuedDisp":"1971-","publisher":"Elsevier","dateIssuedKey":"1971","publisherPlace":"Amsterdam [u.a.]"}],"id":{"zdb":["1466301-6"],"eki":["265783771"],"issn":["1872-6119"]},"pubHistory":["1.1971/72 -"],"part":{"year":"2013","issue":"5","pages":"171-178","volume":"113","text":"113(2013), 5, Seite 171-178","extent":"8"},"type":{"media":"Online-Ressource","bibl":"periodical"},"note":["Gesehen am 28.05.2020"],"disp":"Analogues of Chaitinʼs Omega in the computably enumerable setsInformation processing letters","recId":"265783771","language":["eng"],"title":[{"title_sort":"Information processing letters","title":"Information processing letters","subtitle":"devoted to the rapid publication of short contributions to information processing"}]}],"physDesc":[{"extent":"8 S."}],"name":{"displayForm":["G. Barmpalias, R. Hölzl, A.E.M. Lewis, W. Merkle"]},"id":{"eki":["1737678411"],"doi":["10.1016/j.ipl.2013.01.007"]},"origin":[{"dateIssuedKey":"2013","dateIssuedDisp":"8 January 2013"}]} | ||
| SRT | |a BARMPALIASANALOGUESO8201 | ||