Navegar

Colección

Datos Estadísticas

Artículo

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 obtain a large class of significant examples of n-random reals (i.e.. Martin-Löf random in oracle Ø (n-1) à la Chaitin. Any such real is defined as the probability that a universal monotone Turing machine performing possibly infinite computations on infinite (resp. finite large enough, resp. finite self-delimited) inputs produces an output in a given set @ ⊆ B (N). In particular, we develop methods to transfer ∑ n 0 or Π n 0 many-one completeness results of index sets to n-randomness of associated probabilities. © 2009, Association for Symbolic Logic.

Registro:

Documento: Artículo
Título:From index sets to randomness in Ø n: Random reals and possibly infinite computations part II
Autor:Becher, V.; Grigorieff, S.
Filiación:Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina
CONICET, Argentina
LIAFA, Université Paris 7 and CNRS, France
Año:2009
Volumen:74
Número:1
Página de inicio:124
Página de fin:156
DOI: http://dx.doi.org/10.2178/jsl/1231082305
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_v74_n1_p124_Becher

Referencias:

  • BECHER, V., CHAITIN, G., Another example of higher order randomness (2002) Fundamenta Informaticae, 51 (4), pp. 325-338
  • BECHER, V., CHAITIN, G., DAICZ, S., A highly random number (2001) Proceedings of the Third Discrete Mathematics and Theoretical Computer Science Conference (DMTCS'01), pp. 55-68. , C.S. Calude, M.J. Dineen, and S. Sburlan, editors, Springer-Verlag
  • BECHER, V., FIGUEIRA, S., GRIGORIEFF, S., MILLER, J.S., Randomness and halting probabilities (2006) this JOURNAL, 71 (4), pp. 1411-1430
  • BECHER, V., GRIGORIEFF, S., Recursion and topology on 2 ≤ω for possibly infinite computations (2004) Theoretical Computer Science, 322, pp. 85-136
  • BECHER, V., GRIGORIEFF, S., Random reals and possibly infinite computations. Part 1: Randomness in Ø l (2005) this JOURNAL, 70 (3), pp. 891-913
  • BECHER, V., GRIGORIEFF, S., Random reals à la Chaitin with no prefix-freeness (2007) Theoretical Computer Science, 385, pp. 193-201
  • (2008) Randomness and Outputs in a computable ordered set (Random reals and possibly infinite computations: Part III), , in preparation
  • C.S. CALUDE, P.H. HERTLING, and B. KHOUSSAINOV Y. WANG, Recursively enumerable reals and Chaitin Ω numbers, Stacs 98 (Paris, 1998), Lecture Notes in Computer Science, 1373, Springer-Verlag, 1998, pp. 596-606; CHAITIN, G., A theory of program size formally identical to information theory (1975) Journal of the ACM, 22, pp. 329-340. , Available on Chaitin's home page
  • DOWNEY, R., HIRSCHFELDT, D., (2008) Algorithmic randomness and complexity, , Springer, to appear
  • HJORTH, G., NIES, A., Randomness via effective descriptive set theory (2007) The Journal of the London Mathematical Society, 75 (2), pp. 495-508
  • KREISEL, G., SHOENFIELD, J.R., WANG, H., Number theoretic concepts and recursive wett-orderings, Archiv fur math (1960) Logik und Grundlagenforschung, 5, pp. 42-64
  • ROGERS, H., (1967) Theory of recursive functions and effective computability, , McGraw-Hill
  • SACKS, G.E., (1966) Degrees of unsolvability, Annals of Mathematical Studies, , Princeton University Press
  • SCOTT, D.S., Continuous lattices (1972) Lecture Notes in Math, 2, pp. 97-136. , Toposes, algebraic geometry analogic RW. Lawvered, editor, Springer
  • SELIVANOV, V.L., Hierarchies in φ-spaces and applications (2005) Mathematical Logic Quaterly, 51 (1), pp. 45-61
  • SOARE, R., (1986) Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, , Springer
  • STILLWELL, J., Decidability of the almost all theory of degrees (1972) this JOURNAL, 37, pp. 501-506
  • WADGE, W.W., Degrees of complexity of subsets of the Baire space (1972) Notices of the American Mathematical Society, pp. A-714

Citas:

---------- APA ----------
Becher, V. & Grigorieff, S. (2009) . From index sets to randomness in Ø n: Random reals and possibly infinite computations part II. Journal of Symbolic Logic, 74(1), 124-156.
http://dx.doi.org/10.2178/jsl/1231082305
---------- CHICAGO ----------
Becher, V., Grigorieff, S. "From index sets to randomness in Ø n: Random reals and possibly infinite computations part II" . Journal of Symbolic Logic 74, no. 1 (2009) : 124-156.
http://dx.doi.org/10.2178/jsl/1231082305
---------- MLA ----------
Becher, V., Grigorieff, S. "From index sets to randomness in Ø n: Random reals and possibly infinite computations part II" . Journal of Symbolic Logic, vol. 74, no. 1, 2009, pp. 124-156.
http://dx.doi.org/10.2178/jsl/1231082305
---------- VANCOUVER ----------
Becher, V., Grigorieff, S. From index sets to randomness in Ø n: Random reals and possibly infinite computations part II. J. Symb. Logic. 2009;74(1):124-156.
http://dx.doi.org/10.2178/jsl/1231082305