Navegar

Colección

Datos Estadísticas

Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We give a general theorem that provides examples of n-random reals à la Chaitin, for every n ≥ 1; these are halting probabilities of partial computable functions that are universal by adjunction for the class of all partial computable functions, The same result holds for the class functions of partial computable functions with prefix-free domain. Thus, the usual technical requirement of prefix-freeness on domains is an option which we show to be non-critical when dealing with universality by adjunction. We also prove that the condition of universality by adjunction (which, though particular, is a very natural case of optimality) is essential in our theorem. © 2007 Elsevier Ltd. All rights reserved.

Registro:

Documento: Artículo
Título:Random reals à la Chaitin with or without prefix-freeness
Autor:Becher, V.; Grigorieff, S.
Filiación:Departamento de Computación, FCEyN, Universidad de Buenos Aires, Argentina
Consejo Nacional de Investigaciones Científicas y Técnicas (CONICET), Argentina
LIAFA, CNRS and Université Paris 7, 2, pl. Jussieu, 75251 Paris Cedex 05, France
Palabras clave:Algorithmic randomness; Kolmogorov complexity; Omega numbers; Random reals; Function evaluation; Probability; Problem solving; Algorithmic randomness; Kolmogorov complexity; Omega numbers; Random reals; Theorem proving
Año:2007
Volumen:385
Número:1-3
Página de inicio:193
Página de fin:201
DOI: http://dx.doi.org/10.1016/j.tcs.2007.06.007
Título revista:Theoretical Computer Science
Título revista abreviado:Theor Comput Sci
ISSN:03043975
CODEN:TCSCD
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_03043975_v385_n1-3_p193_Becher.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v385_n1-3_p193_Becher

Referencias:

  • Becher, V., Figueira, S., Grigorieff, S., Miller, J.S., Randomness and halting probabilities (2006) Journal of Symbolic Logic, 71 (4), pp. 1394-1410
  • Becher, V., Grigorieff, S., Random reals and possibly infinite computations. Part I: Randomness in 0{combining long solidus overlay}′ (2005) Journal of Symbolic Logic, 70 (3), pp. 891-913
  • Calude, C., (1994) Information and Randomness, , Springer
  • Calude, C., Hertling, P., Khoussainov, B., Wang, Y., Recursively enumerable reals and Chaitin Ω numbers (1998) Lecture Notes in Computer Science, 1373, pp. 596-606. , STACS 98. Paris, 1998, Springer-Verlag
  • 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
  • Chaitin, G., (1987) Algorithmic Information Theory. 1st edition, , Cambridge University Press
  • Ershov, Yu.L., On a hierarchy of sets. III (1970) Algebra and Logic, 9, pp. 20-31
  • Figueira, S., Stephan, F., Wu, G., Randomness and universal machines (2006) Journal of Complexity, 22 (6), pp. 738-751. , Second International Conference on Computability and Complexity in Analysis, CCA 2005, Fernuniversität Hagen, Informatik Berichte, vol. 326, 2005, pp. 103-116
  • Harris, C.M., On the symmetric enumeration degrees (2007) Notre Dame Journal of Formal Logic, 48 (2), pp. 175-204
  • Levin, L., On the notion of random sequence (1973) Soviet Mathematics Doklady, 14 (5), pp. 1413-1416
  • Li, M., Vitanyi, P., (1997) An Introduction to Kolmogorov Complexity and its Applications. 2nd edition, , Springer
  • Mohrherr, J.-L., Kleene index sets and functional m-degrees (1983) Journal of Symbolic Logic, 48 (3), pp. 829-840
  • Schnorr, C.P., A unified approach to the definition of random sequences (1971) Mathematical Systems Theory, 5, pp. 246-258

Citas:

---------- APA ----------
Becher, V. & Grigorieff, S. (2007) . Random reals à la Chaitin with or without prefix-freeness. Theoretical Computer Science, 385(1-3), 193-201.
http://dx.doi.org/10.1016/j.tcs.2007.06.007
---------- CHICAGO ----------
Becher, V., Grigorieff, S. "Random reals à la Chaitin with or without prefix-freeness" . Theoretical Computer Science 385, no. 1-3 (2007) : 193-201.
http://dx.doi.org/10.1016/j.tcs.2007.06.007
---------- MLA ----------
Becher, V., Grigorieff, S. "Random reals à la Chaitin with or without prefix-freeness" . Theoretical Computer Science, vol. 385, no. 1-3, 2007, pp. 193-201.
http://dx.doi.org/10.1016/j.tcs.2007.06.007
---------- VANCOUVER ----------
Becher, V., Grigorieff, S. Random reals à la Chaitin with or without prefix-freeness. Theor Comput Sci. 2007;385(1-3):193-201.
http://dx.doi.org/10.1016/j.tcs.2007.06.007