Navegar

Colección

Datos Estadísticas

Artículo

Figueira, S.; Hirschfeldt, D.; Miller, J.S.; Ng, K.M.; Nies, A. "Counting the changes of random Δ02 sets" (2010) 6th Conference on Computability in Europe, CiE 2010. 6158 LNCS:162-171
La versión final de este artículo es de uso interno. El editor solo permite incluir en el repositorio el artículo en su versión post-print. Por favor, si usted la posee enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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