Please use this identifier to cite or link to this item: https://doi.org/10.1145/2287718.2287724
DC FieldValue
dc.titleArithmetic complexity via effective names for random sequences
dc.contributor.authorKjos-Hanssen, B.
dc.contributor.authorStephan, F.
dc.contributor.authorTeutsch, J.
dc.date.accessioned2014-10-28T02:30:47Z
dc.date.available2014-10-28T02:30:47Z
dc.date.issued2012-08
dc.identifier.citationKjos-Hanssen, B., Stephan, F., Teutsch, J. (2012-08). Arithmetic complexity via effective names for random sequences. ACM Transactions on Computational Logic 13 (3) : -. ScholarBank@NUS Repository. https://doi.org/10.1145/2287718.2287724
dc.identifier.issn15293785
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/102881
dc.description.abstractWe 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. © 2012 ACM 1529-3785/2012/08-ART24.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1145/2287718.2287724
dc.sourceScopus
dc.subjectArithmetical hierarchy
dc.subjectComputable randomness
dc.subjectSchnorr randomness
dc.typeArticle
dc.contributor.departmentMATHEMATICS
dc.description.doi10.1145/2287718.2287724
dc.description.sourcetitleACM Transactions on Computational Logic
dc.description.volume13
dc.description.issue3
dc.description.page-
dc.identifier.isiut000308370100006
Appears in Collections:Staff Publications

Show simple item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

3
checked on Jul 1, 2022

WEB OF SCIENCETM
Citations

2
checked on Jun 23, 2022

Page view(s)

130
checked on Jun 23, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.