Being low along a sequence and elsewhere
Let an oracle be called low for prefix-free complexity on a set in case access to the oracle improves the prefix-free complexities of the members of the set at most by an additive constant. Let an oracle be called weakly low for prefix-free complexity on a set in case the oracle is low for prefix-fr...
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
June 2019
|
| In: |
The journal of symbolic logic
Year: 2019, Jahrgang: 84, Heft: 2, Pages: 497-516 |
| ISSN: | 1943-5886 |
| DOI: | 10.1017/jsl.2018.63 |
| Online-Zugang: | Verlag, Volltext: https://doi.org/10.1017/jsl.2018.63 Verlag, Volltext: https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/being-low-along-a-sequence-and-elsewhere/CDF7234A367F2EA644289033A04C4BA2 
|
| Verfasserangaben: | Wolfgang Merkle and Liang Yu |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1688812296 | ||
| 003 | DE-627 | ||
| 005 | 20220817215758.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 200129s2019 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1017/jsl.2018.63 |2 doi | |
| 035 | |a (DE-627)1688812296 | ||
| 035 | |a (DE-599)KXP1688812296 | ||
| 035 | |a (OCoLC)1341299563 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 28 |2 sdnb | ||
| 100 | 1 | |a Merkle, Wolfgang |e VerfasserIn |0 (DE-588)1049898400 |0 (DE-627)782852831 |0 (DE-576)40388201X |4 aut | |
| 245 | 1 | 0 | |a Being low along a sequence and elsewhere |c Wolfgang Merkle and Liang Yu |
| 264 | 1 | |c June 2019 | |
| 300 | |a 20 | ||
| 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 29.01.2020 | ||
| 520 | |a Let an oracle be called low for prefix-free complexity on a set in case access to the oracle improves the prefix-free complexities of the members of the set at most by an additive constant. Let an oracle be called weakly low for prefix-free complexity on a set in case the oracle is low for prefix-free complexity on an infinite subset of the given set. Furthermore, let an oracle be called low and weakly for prefix-free complexity along a sequence in case the oracle is low and weakly low, respectively, for prefix-free complexity on the set of initial segments of the sequence. Our two main results are the following characterizations. An oracle is low for prefix-free complexity if and only if it is low for prefix-free complexity along some sequences if and only if it is low for prefix-free complexity along all sequences. An oracle is weakly low for prefix-free complexity if and only if it is weakly low for prefix-free complexity along some sequence if and only if it is weakly low for prefix-free complexity along almost all sequences. As a tool for proving these results, we show that prefix-free complexity differs from its expected value with respect to an oracle chosen uniformly at random at most by an additive constant, and that similar results hold for related notions such as a priori probability. Furthermore, we demonstrate that on every infinite set almost all oracles are weakly low but are not low for prefix-free complexity, while by Shoenfield absoluteness there is an infinite set on which uncountably many oracles are low for prefix-free complexity. Finally, we obtain no-gap results, introduce weakly low reducibility, or WLK-reducibility for short, and show that all its degrees except the greatest one are countable. | ||
| 650 | 4 | |a 03D28 | |
| 650 | 4 | |a 03D30 | |
| 650 | 4 | |a 03D32 | |
| 650 | 4 | |a 68Q30 | |
| 650 | 4 | |a Kolmogorov complexity | |
| 650 | 4 | |a lowness | |
| 650 | 4 | |a randomness | |
| 700 | 1 | |a Yu, Liang |e VerfasserIn |0 (DE-588)1195784872 |0 (DE-627)1677830344 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |t The journal of symbolic logic |d Cambridge : Cambridge Univ. Press, 1936 |g 84(2019), 2, Seite 497-516 |h Online-Ressource |w (DE-627)312113447 |w (DE-600)2010607-5 |w (DE-576)094449333 |x 1943-5886 |7 nnas |a Being low along a sequence and elsewhere |
| 773 | 1 | 8 | |g volume:84 |g year:2019 |g number:2 |g pages:497-516 |g extent:20 |a Being low along a sequence and elsewhere |
| 856 | 4 | 0 | |u https://doi.org/10.1017/jsl.2018.63 |x Verlag |x Resolving-System |3 Volltext |
| 856 | 4 | 0 | |u https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/being-low-along-a-sequence-and-elsewhere/CDF7234A367F2EA644289033A04C4BA2 |x Verlag |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20200129 | ||
| 993 | |a Article | ||
| 994 | |a 2019 | ||
| 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 1 |x j | ||
| 999 | |a KXP-PPN1688812296 |e 3583160371 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"title":[{"title":"Being low along a sequence and elsewhere","title_sort":"Being low along a sequence and elsewhere"}],"person":[{"family":"Merkle","given":"Wolfgang","display":"Merkle, Wolfgang","roleDisplay":"VerfasserIn","role":"aut"},{"family":"Yu","given":"Liang","roleDisplay":"VerfasserIn","display":"Yu, Liang","role":"aut"}],"recId":"1688812296","language":["eng"],"note":["Gesehen am 29.01.2020"],"type":{"media":"Online-Ressource","bibl":"article-journal"},"id":{"doi":["10.1017/jsl.2018.63"],"eki":["1688812296"]},"origin":[{"dateIssuedKey":"2019","dateIssuedDisp":"June 2019"}],"name":{"displayForm":["Wolfgang Merkle and Liang Yu"]},"relHost":[{"origin":[{"publisherPlace":"Cambridge ; Urbana, Ill.","dateIssuedDisp":"1936-","publisher":"Cambridge Univ. Press ; Assoc.","dateIssuedKey":"1936"}],"id":{"zdb":["2010607-5"],"eki":["312113447"],"issn":["1943-5886"]},"name":{"displayForm":["publ. quarterly by the Association for Symbolic Logic. Ed. by Alonzo Church [u.a.]"]},"physDesc":[{"extent":"Online-Ressource"}],"title":[{"title_sort":"journal of symbolic logic","title":"The journal of symbolic logic"}],"pubHistory":["1.1936 -"],"part":{"year":"2019","pages":"497-516","issue":"2","volume":"84","text":"84(2019), 2, Seite 497-516","extent":"20"},"type":{"media":"Online-Ressource","bibl":"periodical"},"disp":"Being low along a sequence and elsewhereThe journal of symbolic logic","note":["Gesehen am 14.11.24"],"recId":"312113447","corporate":[{"role":"isb","roleDisplay":"Herausgebendes Organ","display":"Association for Symbolic Logic"}],"language":["eng"]}],"physDesc":[{"extent":"20 S."}]} | ||
| SRT | |a MERKLEWOLFBEINGLOWAL2019 | ||