Navegar

Colección

Datos Estadísticas

Artículo

Figueira, S.; Hirschfeldt, D.R.; Miller, J.S.; Ng, K.M.; Nies, A. "Counting the changes of random Δ20 sets" (2011) Journal of Logic and Computation. 25(4):1073-1089
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We study the number of changes of the initial segment Zs ⌈n for computable approximations of a Martin-Löf random Δ20 set Z. We establish connections between this number of changes and various notions of computability theoretic lowness, as well as the fundamental thesis that, among random sets, randomness is antithetical to computational power. We introduce a new 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 c2n times. We establish various connections with ω-c.e. tracing and ω-c.e. jump domination, a new lowness property. We also examine some relationships to randomness theoretic notions of highness, and give applications to the study of (weak) Demuth cuppability. © The Author, 2013. Published by Oxford University Press. All rights reserved.

Registro:

Documento: Artículo
Título:Counting the changes of random Δ20 sets
Autor:Figueira, S.; Hirschfeldt, D.R.; Miller, J.S.; Ng, K.M.; Nies, A.
Filiación:Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Pabellón I, Buenos Aires, C1428EGA, Argentina
Department of Mathematics, University of Chicago, 5734 S. University Avenue, Chicago, IL 60637, United States
Department of Mathematics, University of Wisconsin - Madison, 480 Lincoln Drive, Madison, WI 53706-1388, United States
Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, 21 Nanyang Link, Singapore, S637371, Singapore
Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand
Palabras clave:balanced randomness; computable approximation; lowness; Matin-Löf randomness; ω-c.e. jump domination; ω-c.e. tracing; Formal logic; Logic programming; balanced randomness; computable approximation; Computational power; lowness; Random set; Random processes
Año:2011
Volumen:25
Número:4
Página de inicio:1073
Página de fin:1089
DOI: http://dx.doi.org/10.1093/logcom/exs083
Título revista:Journal of Logic and Computation
Título revista abreviado:J Logic Comput
ISSN:0955792X
CODEN:JLCOE
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0955792X_v25_n4_p1073_Figueira

Referencias:

  • Barmpalias, G., Tracing and domination in the Turing degrees (2012) Annals of Pure and Applied Logic, 163, pp. 500-505
  • Downey, R.G., Hirschfeldt, D.R., (2010) Algorithmic Randomness and Complexity, , Springer
  • Figueira, S., Hirschfeldt, D., Miller, J.S., Ng, K.M., Nies, A., Counting the changes of random Δ<inf>2</inf>0 sets (2010) Lecture Notes in Computer Science, 6158, pp. 162-171. , CiE'10, F. Ferreira, B. Löwe, E. Mayordomo, L. M. Gomes, eds Springer
  • Franklin, J.N.Y., Ng, K.M., Difference randomness (2011) Proceedings of the American Mathematical Society, 139, pp. 345-360
  • Greenberg, N., Nies, A., Benign cost functions and lowness properties (2011) Journal of Symbolic Logic, 76, pp. 289-312
  • Jockusch, C.G., Jr., Soare, R.I., Degrees of members of Π<inf>1</inf>0 classes (1972) Pacific Journal of Mathematics, 40, pp. 605-616
  • Kučera, A., Nies, A., Demuth randomness and computational complexity (2011) Annals of Pure and Applied Logic, 162, pp. 504-513
  • Lewis, A., Montalbán, A., Nies, A., A weakly 2-random set that is not generalized low (2007) CiE '07: Proceedings of the 3rd Conference on Computability in Europe, pp. 474-477. , S. B. Cooper, B. Löwe, A. Sorbi, eds Springer-Verlag
  • Martin-Löf, P., The definition of random sequences (1966) Information and Control, 9, pp. 602-619
  • Miller, J., Nies, A., Randomness and computability: Open questions (2006) Bulletin of Symbolic Logic, 12, pp. 390-410
  • Nies, A., Computability and Randomness (2009) Oxford Logic Guides, 51. , Oxford University Press
  • Nies, A., (2012) Computably Enumerable Sets below Random Sets. Annals of Pure and Applied Logic, 163, pp. 1596-1610
  • Nies, A., Stephan, F., Terwijn, S.A., Randomness, relativization and Turing degrees (2005) Journal of Symbolic Logic, 70, pp. 515-535

Citas:

---------- APA ----------
Figueira, S., Hirschfeldt, D.R., Miller, J.S., Ng, K.M. & Nies, A. (2011) . Counting the changes of random Δ20 sets. Journal of Logic and Computation, 25(4), 1073-1089.
http://dx.doi.org/10.1093/logcom/exs083
---------- CHICAGO ----------
Figueira, S., Hirschfeldt, D.R., Miller, J.S., Ng, K.M., Nies, A. "Counting the changes of random Δ20 sets" . Journal of Logic and Computation 25, no. 4 (2011) : 1073-1089.
http://dx.doi.org/10.1093/logcom/exs083
---------- MLA ----------
Figueira, S., Hirschfeldt, D.R., Miller, J.S., Ng, K.M., Nies, A. "Counting the changes of random Δ20 sets" . Journal of Logic and Computation, vol. 25, no. 4, 2011, pp. 1073-1089.
http://dx.doi.org/10.1093/logcom/exs083
---------- VANCOUVER ----------
Figueira, S., Hirschfeldt, D.R., Miller, J.S., Ng, K.M., Nies, A. Counting the changes of random Δ20 sets. J Logic Comput. 2011;25(4):1073-1089.
http://dx.doi.org/10.1093/logcom/exs083