Resource-bounded balanced genericity, stochasticity and weak randomness
We introduce balanced t(n)-genericity which is a refinement of the genericity concept of Ambos-Spies, Fleischhack and Huwig [2] and which in addition controls the frequency with which a condition is met. We show that this concept coincides with the resource-bounded version of Church's stochasti...
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Chapter/Article Conference Paper |
| Lingua: | inglese |
| Pubblicazione: |
1996
|
| In: |
Proceedings
Year: 1996, Pages: 63-74 |
| Accesso online: |
|
| Note sull'autore: | Klaus Ambos-Spies, Elvira Mayordomo, Yongge Wang, Xizhong Zheng |
| Riassunto: | We introduce balanced t(n)-genericity which is a refinement of the genericity concept of Ambos-Spies, Fleischhack and Huwig [2] and which in addition controls the frequency with which a condition is met. We show that this concept coincides with the resource-bounded version of Church's stochasticity [6]. By uniformly describing these concepts and weaker notions of stochasticity introduced by Wilber [19] and Ko [11] in terms of prediction functions, we clarify the relations among these resource-bounded stochasticity concepts. Moreover, we give descriptions of these concepts in the framework of Lutz's resource-bounded measure theory [13] based on martingales: We show that t(n)-stochasticity coincides with a weak notion of t(n)-randomness based on so-called simple martingales but that it is strictly weaker than t(n)-randomness in the sense of Lutz. |
|---|---|
| Descrizione del documento: | Elektronische Reproduktion der Druck-Ausgabe 1. Januar 2005 Gesehen am 18.04.2023 |
| Descrizione fisica: | Online Resource |
| ISBN: | 9783540497233 |