DEEP Π CLASSES.
A set of infinite binary sequences C ⊆ 2 is negligible if there is no partial probabilistic algorithm that produces an element of this set with positive probability. The study of negligibility is of particular interest in the context of Π classes. In this paper, we introduce the notion of depth for...
| Published in: | Bulletin of Symbolic Logic Vol. 22; no. 2; pp. 249 - 287 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Published: |
Cambridge University Press
Jun2016
|
| Subjects: | |
| Online Access: | View this record in EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=116681681&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 116681681 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 10798986 1BA jtl: Bulletin of Symbolic Logic issn: 10798986 maglogo: N pubinfo: dt: Jun2016 vid: 22 iid: 2 pid: 15979 pub: Cambridge University Press artinfo: ui: 116681681 10.1017/bsl.2016.9 ppf: 249 ppct: 38 formats: tig: atl: DEEP Π CLASSES. aug: au: BIENVENU, LAURENT PORTER, CHRISTOPHER P. affil: LABORATOIRE CNRS J.-V. PONCELET 119002, BOLSHOY VLASYEVSKIY PEREULOK 11 MOSCOW, RUSSIA DEPARTMENT OF MATHEMATICS UNIVERSITY OF FLORIDA GAINESVILLE, FLORIDA 32611- 8105, USA su: Binary sequences Algorithms Probability theory Computable functions Algorithmic randomness sug: subj: Binary sequences Algorithms Probability theory Computable functions Algorithmic randomness keyword: Π10 classes algorithmic randomness computability theory probabilistic computation ab: A set of infinite binary sequences C ⊆ 2 is negligible if there is no partial probabilistic algorithm that produces an element of this set with positive probability. The study of negligibility is of particular interest in the context of Π classes. In this paper, we introduce the notion of depth for Π classes, which is a stronger form of negligibility. Whereas a negligible Π class C has the property that one cannot probabilistically compute a member of C with positive probability, a deep Π class C has the property that one cannot probabilistically compute an initial segment of a member of C with high probability. That is, the probability of computing a length n initial segment of a deep Π class converges to 0 effectively in n. We prove a number of basic results about depth, negligibility, and a variant of negligibility that we call tt-negligibility. We provide a number of examples of deep Π classes that occur naturally in computability theory and algorithmic randomness. We also study deep classes in the context of mass problems, examine the relationship between deep classes and certain lowness notions in algorithmic randomness, and establish a relationship between members of deep classes and the amount of mutual information with Chaitin's Ω. pubtype: Academic Journal doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2016 holdings: @attributes: islocal: N |
|---|