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...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Chapter/Article Conference Paper |
| Language: | English |
| Published: |
1996
|
| In: |
Proceedings
Year: 1996, Pages: 63-74 |
| Online Access: |
|
| Author Notes: | Klaus Ambos-Spies, Elvira Mayordomo, Yongge Wang, Xizhong Zheng |
| Summary: | 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. |
|---|---|
| Item Description: | Elektronische Reproduktion der Druck-Ausgabe 1. Januar 2005 Gesehen am 18.04.2023 |
| Physical Description: | Online Resource |
| ISBN: | 9783540497233 |