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...
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Dokumenttyp: | Kapitel/Artikel Konferenzschrift |
| Sprache: | Englisch |
| Veröffentlicht: |
1996
|
| In: |
Proceedings
Year: 1996, Pages: 63-74 |
| Online-Zugang: |
|
| Verfasserangaben: | Klaus Ambos-Spies, Elvira Mayordomo, Yongge Wang, Xizhong Zheng |
| Zusammenfassung: | 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. |
|---|---|
| Beschreibung: | Elektronische Reproduktion der Druck-Ausgabe 1. Januar 2005 Gesehen am 18.04.2023 |
| Beschreibung: | Online Resource |
| ISBN: | 9783540497233 |