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 define a program size complexity function H∞ as a variant of the prefix-free Kolmogorov complexity, based on Turing monotone machines performing possibly unending computations. We consider definitions of randomness and triviality for sequences in {0, 1}ω relative to the H∞ complexity. We prove that the classes of Martin-Löf random sequences and H∞-random sequences coincide and that the H∞-trivial sequences are exactly the recursive ones. We also study some properties of H∞ and compare it with other complexity functions. In particular, H∞ is different from H A, the prefix-free complexity of monotone machines with oracle A. © 2005 University of Notre Dame.

Registro:

Documento: Artículo
Título:Program size complexity for possibly infinite computations
Autor:Becher, V.; Figueira, S.; Nies, A.; Picchi, S.
Filiación:Depto. Computación, Facultad Cs. Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Department of Computer Science, University of Auckland, New Zealand
Palabras clave:Infinite computations; KOLMOGOROV complexity; Program size complexity
Año:2005
Volumen:46
Número:1
Página de inicio:51
Página de fin:64
DOI: http://dx.doi.org/10.1305/ndjfl/1107220673
Título revista:Notre Dame Journal of Formal Logic
Título revista abreviado:Notre Dam J. Logic.
ISSN:00294527
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00294527_v46_n1_p51_Becher

Referencias:

  • Becher, V., Daicz, S., Chaitin, G., A highly random number (2001) Combinatorics, Computability and Logic: Proceedings of the Third Discrete Mathematics and Theoretical Computer Science Conference (DMTCS'01), pp. 55-68. , edited by C. S. Calude and M. J. Dineen and S. Sburlan, Springer-Verlag, London. Zbl 0967.00065. MR 2003d:00011. 54, 55
  • Chaitin, G.J., A theory of program size formally identical to information theory (1975) Journal of the Association for Computing Machinery, 22, pp. 329-340. , Zbl 0309.68045. MR 53:15557. 51, 54, 55, 62
  • Chaitin, G.J., Algorithmic entropy of sets (1976) Computers & Mathematics with Applications, 2, pp. 233-245. , Zbl 0367.68036. 52
  • Chaitin, G.J., Information-theoretic characterizations of recursive infinite strings (1976) Theoretical Computer Science, 2, pp. 45-48. , Zbl 0328.02029. MR 54:1709. 60
  • Downey, R.G., Hirschfeldt, D.R., Nies, A., Stephan, F., Trivial reals (2003) Proceedings of the 7th and 8th Asian Logic Conferences, pp. 103-131. , Singapore University Press, Singapore. Zbl 02063218. MR 2051976. 59, 60
  • Ferbus-Zanda, M., Grigorieff, S., (2003) Church, Cardinal and Ordinal Representations of Integers and Kolmogorov Complexity, , in preparation, 59
  • Gacs, P., On the symmetry of algorithmic information (1974) Soviet Mathematics, Doklady (Akademiia Nauk SSSR. Doklady), 15, pp. 1477-1480. , Zbl 0314.94019. 54
  • Levin, L.A., The concept of a random sequence (1973) Doklady Akademii Nauk SSSR, 212, pp. 548-550. , Zbl 0312.94006. MR 51:2346. 52, 62
  • Levin, L.A., Laws on the conservation (zero increase) of information, and questions on the foundations of probability theory (1974) Problemy Peredači Informacii, 10, pp. 30-35. , Zbl 0312.94007. MR 57:9298. 51, 54
  • Li, M., Vitanyi, P., (1997) An Introduction to Kolmogorov Complexity and Its Applications 2d Edition Graduate Texts in Computer Science, , Springer-Verlag, New York. Zbl 0866.68051. MR 97k:68086. 51
  • Martin-Löf, P., The definition of random sequences (1966) Information and Control, 9, pp. 602-619. , Zbl 0244.62008. MR 36:6228. 62
  • Schnorr, C.-P., Process complexity and effective random tests Journal of Computer and System Sciences, 7 (1973), pp. 376-388
  • (1972) Fourth Annual ACMSymposium on the Theory of Computing, , (Denver, Colo.). Zbl 0273.68036. MR 48:3713. 51
  • Solovay, R.M., (1974) Draft of A Paper (Or Series of Papers) on Chaitin's Work Done for the Most Part during the Period Sept. to Dec. 1974, , 60, 61
  • Uspensky, V.A., Shen, A., Relations between varieties of Kolmogorov complexities (1996) Mathematical Systems Theory, 29, pp. 271-292. , Zbl 0849.68059. MR 97c:68074. 51
  • Zvonkin, A.K., Levin, L.A., The complexity of finite objects and the basing of the concepts of information and randomness on the theory of algorithms (1970) Uspekhi Matematicheskikh Nauk, 25, pp. 85-127. , Zbl 0222.02027. MR 46:7004. 51, 54

Citas:

---------- APA ----------
Becher, V., Figueira, S., Nies, A. & Picchi, S. (2005) . Program size complexity for possibly infinite computations. Notre Dame Journal of Formal Logic, 46(1), 51-64.
http://dx.doi.org/10.1305/ndjfl/1107220673
---------- CHICAGO ----------
Becher, V., Figueira, S., Nies, A., Picchi, S. "Program size complexity for possibly infinite computations" . Notre Dame Journal of Formal Logic 46, no. 1 (2005) : 51-64.
http://dx.doi.org/10.1305/ndjfl/1107220673
---------- MLA ----------
Becher, V., Figueira, S., Nies, A., Picchi, S. "Program size complexity for possibly infinite computations" . Notre Dame Journal of Formal Logic, vol. 46, no. 1, 2005, pp. 51-64.
http://dx.doi.org/10.1305/ndjfl/1107220673
---------- VANCOUVER ----------
Becher, V., Figueira, S., Nies, A., Picchi, S. Program size complexity for possibly infinite computations. Notre Dam J. Logic. 2005;46(1):51-64.
http://dx.doi.org/10.1305/ndjfl/1107220673