Randomness and halting probabilities
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 i...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , , |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
2006
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 04555caa a22004937a 4500 | ||
|---|---|---|---|
| 001 | PAPER-6871 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518203635.0 | ||
| 008 | 190411s2006 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-33845530817 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Becher, V. | |
| 245 | 1 | 0 | |a Randomness and halting probabilities |
| 260 | |c 2006 | ||
| 270 | 1 | 0 | |m Becher, V.; Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos AiresArgentina; email: vbecher@dc.uba.ar |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Becher, V., Grigorieff, S., (2005) Random Reals and Possibly Infinite Computations. Part I: Randomness in ∅′, 70 (3), pp. 891-913. , this JOURNAL | ||
| 504 | |a Random Reals and Possibly Infinite Computations. Part II: From Index Sets to Higher Order Randomness, , In preparation | ||
| 504 | |a 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 | ||
| 504 | |a Chaitin, G.J., A theory of program size formally identical to information theory (1975) Journal of the ACM, 22, pp. 329-340 | ||
| 504 | |a (1988) Algorithmic Information Theory, , Cambridge University Press | ||
| 504 | |a Downey, R., Hirschfeldt, D., Algorithmic Randomness and Complexity, , to appear | ||
| 504 | |a Downey, R., Hirschfeldt, D., Nies, A., Randomness, computability and density (2002) SIAM Journal on Computing, 31, pp. 1169-1183 | ||
| 504 | |a 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 | ||
| 504 | |a Kučera, A., Slaman, T.A., Randomness and recursive enumerability (2001) SIAM Journal on Computing, 31, pp. 199-211 | ||
| 504 | |a Odifreddi, P., (1990) Classical Recursion Theory, , North-Holland | ||
| 504 | |a Rogers Jr., H., (1968) Theory of Recursive Functions and Effective Computability, , McGraw Hill, New York | ||
| 504 | |a 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 | ||
| 520 | 3 | |a 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. |l eng | |
| 593 | |a Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina | ||
| 593 | |a CONICET, Argentina | ||
| 593 | |a LIAFA, Université Paris 7, CNRS, France | ||
| 593 | |a Department of Mathematics, University of Connecticut, United States | ||
| 700 | 1 | |a Figueira, S. | |
| 700 | 1 | |a Grigorieff, S. | |
| 700 | 1 | |a Miller, J.S. | |
| 773 | 0 | |d 2006 |g v. 71 |h pp. 1411-1430 |k n. 4 |p J. Symb. Logic |x 00224812 |w (AR-BaUEN)CENRE-249 |t Journal of Symbolic Logic | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-33845530817&doi=10.2178%2fjsl%2f1164060463&partnerID=40&md5=98090d037d640796c3c48c7bda34898a |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.2178/jsl/1164060463 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_00224812_v71_n4_p1411_Becher |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00224812_v71_n4_p1411_Becher |y Registro en la Biblioteca Digital |
| 961 | |a paper_00224812_v71_n4_p1411_Becher |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 999 | |c 67824 | ||