Abstract:
Consider a Martin-Löf random Δ02 set Z. We give lower bounds for the number of changes of Zs|n for computable approximations of Z. We show that each nonempty Π0 1 class has a low member Z with a computable approximation that changes only o(2n ) times. We prove that each superlow ML-random set already satisfies a stronger randomness notion called balanced randomness, which implies that for each computable approximation and each constant c, there are infinitely many n such that Zs|n changes more than c2 n times. © 2010 Springer-Verlag Berlin Heidelberg.
Registro:
Documento: |
Artículo
|
Título: | Counting the changes of random Δ02 sets |
Autor: | Figueira, S.; Hirschfeldt, D.; Miller, J.S.; Ng, K.M.; Nies, A. |
Ciudad: | Ponta Delgada, Azores |
Filiación: | Dept. of Computer Science, FCEyN, University of Buenos Aires, Argentina Dept. of Mathematics, University of Chicago, United States Dept. of Mathematics, University of Wisconsin-Madison, United States Dept. of Computer Science, University of Auckland, New Zealand
|
Palabras clave: | Lower bounds; Random set; Random processes |
Año: | 2010
|
Volumen: | 6158 LNCS
|
Página de inicio: | 162
|
Página de fin: | 171
|
DOI: |
http://dx.doi.org/10.1007/978-3-642-13962-8_18 |
Título revista: | 6th Conference on Computability in Europe, CiE 2010
|
Título revista abreviado: | Lect. Notes Comput. Sci.
|
ISSN: | 03029743
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v6158LNCS_n_p162_Figueira |
Referencias:
- Nies, A., (2009) Computability and Randomness, 51. , Oxford Logic Guides, Oxford University Press, Oxford
- Greenberg, N., Nies, A., Benign Cost Functions and Lowness Properties, , to appear
- Kücera, A., Nies, A., Demuth Randomness and Computational Complexity, , to appear 20xx
- Jockusch Jr., C., Soare, R., Degrees of members of 0 1 classes (1972) Pacific J. Math., 40, pp. 605-616
- Franklin, J.N., Ng, K.M., Difference randomness Proceedings of the American Mathematical Society, , to appear
Citas:
---------- APA ----------
Figueira, S., Hirschfeldt, D., Miller, J.S., Ng, K.M. & Nies, A.
(2010)
. Counting the changes of random Δ02 sets. 6th Conference on Computability in Europe, CiE 2010, 6158 LNCS, 162-171.
http://dx.doi.org/10.1007/978-3-642-13962-8_18---------- CHICAGO ----------
Figueira, S., Hirschfeldt, D., Miller, J.S., Ng, K.M., Nies, A.
"Counting the changes of random Δ02 sets"
. 6th Conference on Computability in Europe, CiE 2010 6158 LNCS
(2010) : 162-171.
http://dx.doi.org/10.1007/978-3-642-13962-8_18---------- MLA ----------
Figueira, S., Hirschfeldt, D., Miller, J.S., Ng, K.M., Nies, A.
"Counting the changes of random Δ02 sets"
. 6th Conference on Computability in Europe, CiE 2010, vol. 6158 LNCS, 2010, pp. 162-171.
http://dx.doi.org/10.1007/978-3-642-13962-8_18---------- VANCOUVER ----------
Figueira, S., Hirschfeldt, D., Miller, J.S., Ng, K.M., Nies, A. Counting the changes of random Δ02 sets. Lect. Notes Comput. Sci. 2010;6158 LNCS:162-171.
http://dx.doi.org/10.1007/978-3-642-13962-8_18