Arithmetic complexity via effective names for random Sequences
We investigate enumerability properties for classes of sets which permit recursive, lexicographically increasing approximations, or left-r.e. sets. In addition to pinpointing the complexity of left-r.e. Martin-Löf, computably, Schnorr, and Kurtz random sets, weakly 1-generics and their complementar...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
August 2012
|
| In: |
ACM transactions on computational logic
Year: 2012, Volume: 13, Issue: 3 |
| ISSN: | 1529-3785 |
| DOI: | 10.1145/2287718.2287724 |
| Online Access: | Verlag, Volltext: http://dx.doi.org/10.1145/2287718.2287724 Verlag, Volltext: http://doi.acm.org/10.1145/2287718.2287724 
|
| Author Notes: | Bjørn Kjos-Hanssen, Frank Stephan, Jason Teutsch |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1587206072 | ||
| 003 | DE-627 | ||
| 005 | 20220815095757.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 190204s2012 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1145/2287718.2287724 |2 doi | |
| 035 | |a (DE-627)1587206072 | ||
| 035 | |a (DE-576)517206072 | ||
| 035 | |a (DE-599)BSZ517206072 | ||
| 035 | |a (OCoLC)1341034849 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 27 |2 sdnb | ||
| 100 | 1 | |a Kjos-Hanssen, Bjørn |e VerfasserIn |0 (DE-588)1176728318 |0 (DE-627)1047753820 |0 (DE-576)516776789 |4 aut | |
| 245 | 1 | 0 | |a Arithmetic complexity via effective names for random Sequences |c Bjørn Kjos-Hanssen, Frank Stephan, Jason Teutsch |
| 264 | 1 | |c August 2012 | |
| 300 | |a 18 | ||
| 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 04.02.2019 | ||
| 520 | |a We investigate enumerability properties for classes of sets which permit recursive, lexicographically increasing approximations, or left-r.e. sets. In addition to pinpointing the complexity of left-r.e. Martin-Löf, computably, Schnorr, and Kurtz random sets, weakly 1-generics and their complementary classes, we find that there exist characterizations of the third and fourth levels of the arithmetic hierarchy purely in terms of these notions. More generally, there exists an equivalence between arithmetic complexity and existence of numberings for classes of left-r.e. sets with shift-persistent elements. While some classes (such as Martin-Löf randoms and Kurtz nonrandoms) have left-r.e. numberings, there is no canonical, or acceptable, left-r.e. numbering for any class of left-r.e. randoms. Finally, we note some fundamental differences between left-r.e. numberings for sets and reals. | ||
| 650 | 4 | |a arithmetical hierarchy | |
| 650 | 4 | |a computable randomness | |
| 650 | 4 | |a Schnorr randomness | |
| 700 | 1 | |a Stephan, Frank |e VerfasserIn |0 (DE-588)1125914025 |0 (DE-627)880490810 |0 (DE-576)483630047 |4 aut | |
| 700 | 1 | |a Teutsch, Jason |e VerfasserIn |0 (DE-588)1157025145 |0 (DE-627)1020025492 |0 (DE-576)502579501 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |a Association for Computing Machinery |t ACM transactions on computational logic |d New York, NY : Association for Computing Machinery, 2000 |g 13(2012,3) Article 24, 13 Seiten |h Online-Ressource |w (DE-627)320648303 |w (DE-600)2025647-4 |w (DE-576)09442375X |x 1529-3785 |7 nnas |
| 773 | 1 | 8 | |g volume:13 |g year:2012 |g number:3 |g extent:18 |a Arithmetic complexity via effective names for random Sequences |
| 856 | 4 | 0 | |u http://dx.doi.org/10.1145/2287718.2287724 |x Verlag |x Resolving-System |3 Volltext |
| 856 | 4 | 0 | |u http://doi.acm.org/10.1145/2287718.2287724 |x Verlag |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20190204 | ||
| 993 | |a Article | ||
| 994 | |a 2012 | ||
| 998 | |g 1157025145 |a Teutsch, Jason |m 1157025145:Teutsch, Jason |p 3 |y j | ||
| 999 | |a KXP-PPN1587206072 |e 3053754789 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"language":["eng"],"recId":"1587206072","note":["Gesehen am 04.02.2019"],"type":{"media":"Online-Ressource","bibl":"article-journal"},"title":[{"title":"Arithmetic complexity via effective names for random Sequences","title_sort":"Arithmetic complexity via effective names for random Sequences"}],"person":[{"family":"Kjos-Hanssen","given":"Bjørn","display":"Kjos-Hanssen, Bjørn","roleDisplay":"VerfasserIn","role":"aut"},{"given":"Frank","family":"Stephan","role":"aut","roleDisplay":"VerfasserIn","display":"Stephan, Frank"},{"role":"aut","roleDisplay":"VerfasserIn","display":"Teutsch, Jason","given":"Jason","family":"Teutsch"}],"relHost":[{"recId":"320648303","corporate":[{"role":"aut","display":"Association for Computing Machinery","roleDisplay":"VerfasserIn"}],"language":["eng"],"disp":"Association for Computing MachineryACM transactions on computational logic","type":{"media":"Online-Ressource","bibl":"periodical"},"note":["Gesehen am 15.06.20"],"part":{"extent":"18","volume":"13","text":"13(2012,3) Article 24, 13 Seiten","issue":"3","year":"2012"},"titleAlt":[{"title":"Transactions on computational logic"},{"title":"TOCL"}],"pubHistory":["1.2000 -"],"title":[{"title_sort":"ACM transactions on computational logic","title":"ACM transactions on computational logic","subtitle":"TOCL"}],"physDesc":[{"extent":"Online-Ressource"}],"id":{"eki":["320648303"],"zdb":["2025647-4"],"issn":["1529-3785"]},"origin":[{"publisherPlace":"New York, NY","publisher":"Association for Computing Machinery","dateIssuedKey":"2000","dateIssuedDisp":"2000-"}]}],"physDesc":[{"extent":"18 S."}],"id":{"eki":["1587206072"],"doi":["10.1145/2287718.2287724"]},"origin":[{"dateIssuedDisp":"August 2012","dateIssuedKey":"2012"}],"name":{"displayForm":["Bjørn Kjos-Hanssen, Frank Stephan, Jason Teutsch"]}} | ||
| SRT | |a KJOSHANSSEARITHMETIC2012 | ||