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