Navegar

Colección

Datos Estadísticas

Artículo

Becher, V.; Figueira, S.; Grigorieff, S.; Miller, J.S. "Randomness and halting probabilities" (2006) Journal of Symbolic Logic. 71(4):1411-1430
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 consider the question of randomness of the probability ΩU[X] that an optimal Turing machine U halts and outputs a string in a fixed set X. The main results are as follows: ΩU[X] is random whenever X is Σn0-complete or Πn0-complete for some n ≥ 2. However, for n ≥ 2, ΩU[X] is not n-random when X is Σn0 or Πn0. Nevertheless, there exists Δn+10 sets such that ΩU[X] is n-random. There are Δ20 sets X such that ΩU[X] is rational. Also, for every n ≥ 1, there exists a set X which is Δn+10 and Σn 0-hard such that ΩU[X] is not random. We also look at the range of ΩU as an operator. We prove that the set {ΩU[X]: X ⊆ 2<ω} is a finite union of closed intervals. It follows that for any optimal machine U and any sufficiently small real r, there is a set X ⊆ 2<ω recursive in ∅′ ⊕ r, such that ΩU[X] = r. The same questions are also considered in the context of infinite computations, and lead to similar results. © 2006, Association for Symbolic Logic.

Registro:

Documento: Artículo
Título:Randomness and halting probabilities
Autor:Becher, V.; Figueira, S.; Grigorieff, S.; Miller, J.S.
Filiación:Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina
CONICET, Argentina
LIAFA, Université Paris 7, CNRS, France
Department of Mathematics, University of Connecticut, United States
Año:2006
Volumen:71
Número:4
Página de inicio:1411
Página de fin:1430
DOI: http://dx.doi.org/10.2178/jsl/1164060463
Título revista:Journal of Symbolic Logic
Título revista abreviado:J. Symb. Logic
ISSN:00224812
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00224812_v71_n4_p1411_Becher

Referencias:

  • Becher, V., Grigorieff, S., (2005) Random Reals and Possibly Infinite Computations. Part I: Randomness in ∅′, 70 (3), pp. 891-913. , this JOURNAL
  • Random Reals and Possibly Infinite Computations. Part II: From Index Sets to Higher Order Randomness, , In preparation
  • Calude, C., Hertling, P., Khoussainov, B., Wang, Y., Recursively enumerable reals and Chaitin Omega numbers (2001) Theoretical Computer Science, 255 (1-2), pp. 125-149
  • Chaitin, G.J., A theory of program size formally identical to information theory (1975) Journal of the ACM, 22, pp. 329-340
  • (1988) Algorithmic Information Theory, , Cambridge University Press
  • Downey, R., Hirschfeldt, D., Algorithmic Randomness and Complexity, , to appear
  • Downey, R., Hirschfeldt, D., Nies, A., Randomness, computability and density (2002) SIAM Journal on Computing, 31, pp. 1169-1183
  • Figueira, S., Stephan, F., Wu, G., Randomness and universal machines (2005) CCA 2005, Second International Conference on Computability and Complexity in Analysis, Kyoto, Fernuniversität Hagen, Informatik Berichte, 326, pp. 103-116
  • Kučera, A., Slaman, T.A., Randomness and recursive enumerability (2001) SIAM Journal on Computing, 31, pp. 199-211
  • Odifreddi, P., (1990) Classical Recursion Theory, , North-Holland
  • Rogers Jr., H., (1968) Theory of Recursive Functions and Effective Computability, , McGraw Hill, New York
  • Solovay, R.M., (1974) Draft of Paper (Or Series of Papers) on Chaitin's Work, Done for the Most Part during the Period of Sept.-Dec., , unpublished manuscript, IBM Thomas Watson Research Center, Yorktown Heights, NY, 215 pages

Citas:

---------- APA ----------
Becher, V., Figueira, S., Grigorieff, S. & Miller, J.S. (2006) . Randomness and halting probabilities. Journal of Symbolic Logic, 71(4), 1411-1430.
http://dx.doi.org/10.2178/jsl/1164060463
---------- CHICAGO ----------
Becher, V., Figueira, S., Grigorieff, S., Miller, J.S. "Randomness and halting probabilities" . Journal of Symbolic Logic 71, no. 4 (2006) : 1411-1430.
http://dx.doi.org/10.2178/jsl/1164060463
---------- MLA ----------
Becher, V., Figueira, S., Grigorieff, S., Miller, J.S. "Randomness and halting probabilities" . Journal of Symbolic Logic, vol. 71, no. 4, 2006, pp. 1411-1430.
http://dx.doi.org/10.2178/jsl/1164060463
---------- VANCOUVER ----------
Becher, V., Figueira, S., Grigorieff, S., Miller, J.S. Randomness and halting probabilities. J. Symb. Logic. 2006;71(4):1411-1430.
http://dx.doi.org/10.2178/jsl/1164060463