Arbor, Vol 189, No 764 (2013)

Alan Turing y los orígenes de la complejidad

Miguel Angel Martin-Delgado
Departamento de Física Teórica I, Universidad Complutense, España


El 75 aniversario del artículo seminal de Turing y el centenario de su nacimiento ocurren en 2011 y 2012, respectivamente. Es natural revisar y valorar las contribuciones que hizo Turing en campos muy diversos a la luz de los desarrollos que sus pensamientos han producido en muchas comunidades científicas. Aquí, la idea principal es discutir como el trabajo de Turing nos permite cambiar nuestra visión sobre los fundamentos de las Matemáticas, de forma similar a como la mecánica cuántica cambió nuestra concepción de la Física. Nociones básicas como compatibilidad y universalidad se discuten en un contexto amplio, haciendo énfasis especial en como a la noción de complejidad se le puede dar un significado preciso después de Turing, es decir, no solo cualitativo sino cuantitativo. Al trabajo de Turing se le da una perspectiva histórica en relación a algunos de sus precursores, contemporáneos y matemáticos que tomaron y llevaron sus ideas aún más allá.

Palabras clave

Máquina de Turing; Computabilidad; Complejidad Algorítmica; Complejidad Computacional; Clases de Complejidad; Omega de Chaitin; Entropía Algorítmica; Barrera de Turing

Texto completo:



Aaronson, S.; Kuperberg, G. and Granade, C. (2005). "The Complexity Zoo", retrieved from

Association for Computing Machinery (2001). Retrieved from

Bernstein, E. and Vazirani, U. (1997). "Quantum complexity theory". SIAM J. Comput., 26, pp. 1411-1473.

Berthiaume, A; van Dam, W. and Laplante, S. (2000). "Quantum Kolmogorov Complexity", arXiv: retrieved from quantph/005018.

Borel, E. (1909). "Les probabilités dénombrables et leurs applications arithmétiques". Rendiconti del Circolo Matematico di Palermo, 27, pp. 247-271.

Borel, E. (1952). Les nombres inaccessibles. Paris: Ed. Gauthier-Villars, 10 + 141 pp.

Bozkurt, B. (2011). Otomata - Online Generative Musical Sequencer. Retrieved from otomata

Chaitin, G. J. (1966). "On the length of programs for computing finite binary sequences". Journal of the ACM, 13, pp. 547-569.

Chaitin, G. J. (1975). "A theory of program size formally identical to information theory". J. ACM, 22, pp. 329-340.

Chaitin, G. J. (1987). Algorithmic Information Theory. Cambridge University Press.

Chaitin, G. J. (2001). Exploring randomness. London: Springer-Verlag.

Chaitin, G. J. (2003). The Limits of Mathematics. London: Springer-Verlag.

Chaitin, G. J. (2009). "Leibniz, Complexity and Incompleteness". APA Newsletter on Philosophy and Computers, 9 (1), pp. 7-10.

Chaitin, G. J. (2011). "To a mathematical theory of evolution and biological creativity"; preprint. Paper presented Monday 10 January 2011 at a workshop on "Randomness, Structure and Causality: Measures of Complexity from Theory to Applications" organized by Jim Crutcheld and Jon Machta at the Santa Fe Institute in New Mexico.

Chaitin, G. J. (2012). Proving Darwin. New York: Pantheon.

Chaitin, G. J. (2012b). "Life as evolving software". In H. Zenil, A Computable Universe. Singapore: World Scientific.

Calude, C. S. (2002). Information and Randomness. An Algorithmic Perspective. Second Edition. Berlin, Heidelberg, New York: Springer-Verlag.

Calude, C. S.; Dinneen, M. J. and Shu, C.-K. (2002). "Computing a glimpse of randomness". Exper. Math., 11, pp. 361-370.

Calude, C. S. and Pavlov, B. (2002). "Coins, Quantum Measurements, and Turing's Barrier". Quantum Information Processing, 1 (1-2).

Cover, T. M. and Thomas, J. A. (2006). Elements of Information Theory. Second Edition. New Jersey: John Wiley & Sons, Inc.

Cantor, G. (1891). See (Suppes, 1960).

Cohen, P. J. (1963). "The Independence of the Continuum Hypothesis". Proceedings of the National Academy of Sciences of the United States of America, 50 (6), pp. 1143-1148.

Collatz, L. (1937). Unpublished.

Cook, M. (2004). "Universality in Elementary Cellular Automata". Complex Systems, 15, pp. 1-40.

Copeland, J. and Proudfoot, D. (1999). "Alan Turing's forgotten ideas in computer science". Scientific American, April issue.

Copeland, J. (ed.) (2004). The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma. Oxford UK: Clarendon Press (Oxford University Press).

Dauben, J. W. (1979). Georg Cantor: his mathematics and philosophy of the infinite. Boston: Harvard University Press.

Davis, M. (1958). Computability and Unsolvability. New York: McGraw-Hill.

De las Cuevas, G.; Dür, W.; Van den Nest, M. and Martin-Delgado, M. A. (2011). "Quantum algorithms for classical lattice models", arXiv:1104.2517. New J. of Physics 13:093021.

Euwe, M. (1929). "Mengentheoretische Betrachtungen über das Schachspiel". Proc. Konin. Akad. Wetenschappen (Amsterdam), 32 (5), pp. 633-642.

Feynman, R. P. (1982). "Simulating physics with computers". Int. J. Theor. Phys., 21, pp. 467-488.

Gács, P. (2000). "Quantum Algorithmic Entropy", (2001). arXiv: retrieved from quantph/0011046 v2.

Galindo, A. and Martin-Delgado, M. A. (2002). "Information and Computation: Classical and Quantum Aspects". Rev.Mod.Phys., 74, pp. 347-423; arXiv:quant-ph/0112105.

Gödel, K. F. (1931). "Fiber formal unentscheidbare Sátze der Principia Mathematica and verwandter Systeme, I". Monatshefte fu.r Mathematik and Physik, 38, pp. 173-98.

Gödel, K. F. (1940). The Consistency of the Axiom of Choice and of the Generalized Continuum Hypothesis with the Axioms of Set Theory. Princeton University Press.

Hilbert, D. (1927). "The foundations of mathematics", translated by Stephan Bauer-Menglerberg and Dagfinn Follesdal (pp. 464-479). In: van Heijenoort, J. (1967, 3rd printing 1976), From Frege to Godel: A Source Book in Mathematical Logic. Cambridge, MA: Harvard University Press, pp. 1879-1931.

Kieu, T. D. (2003). "Quantum Algorithm for Hilbert's Tenth Problem", retrieved from arXiv:quant-ph/0310052v2.

Knuth, D. E. (2000). Selected Papers on Analysis of Algorithms. Ed. Stanford, California: Center for the Study of Language and Information - CSLI Lecture Notes, no. 102.

Kolmogorov, A. N. (1965). "Three Approaches to the Quantitative Definition of Information". Problems Inform. Transmission, 1 (1), pp. 1-7.

Kurtz, S. A. and Simon, J. (2007). "The Undecidability of the Generalized Collatz Problem". In Cai, J.-Y.; Cooper, S.B.; Zhu, H., Proceedings of the 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007, held in Shanghai, China in May 2007. pp. 542-553.

Leibniz, G. W. (1686). Discours de métaphysique. Li, M. and Vitanyi, P. (1990). "Kolmogorov complexity and its applications". In: J. van Leeuven (ed.), Handbook of Theoretical Computer Science, Vol. A, pp. 187-254.

Martin-Delgado, M. A. (2011). "On Quantum Effects in a Theory of Biological Evolution". Scientific Reports, 2, 302 (2012). Retrieved from arxive arXiv:1109.0383.

Martin-Löf, P. (1966). "The Definition of Random Sequences." Information and Control, 9 (6), pp. 602-619.

Millen, D. (1990). "Cellular Automata Music". In International Computer Music Conference, Glasgow. Retrieved from

Minsky, M. L., (1962). "Size and Structure of Universal Turing Machines Using Tag Systems". Proc. Sympos. Pure Math. 5, pp. 229-238.

Moore, G. E. (1965). "Cramming more components onto integrated circuits". Electronics, 38 (8), April 19.

Mora, C. and Briegel, H. J. (2004). "Algorithmic complexity of quantum states", retrieved from arXiv:quantph/0412172.

Mora, C. and Briegel, H. (2005). "Algorithmic complexity and entanglement of quantum states". Phys. Rev. Lett., 95 (20).

Mora, C.; Briegel, H. and Kraus, B. (2006). "Quantum Kolmogorov complexity and its applications", retrieved from arXiv:quant-ph/0610109.

Newton, I. (1687). Philosophiae Naturalis Principia Mathematica. London Online version:

Oliveira e Silva, T. (2012). Retrieved from

Radó, T. (1962). "On non-computable functions". Bell System Technical Journal, 41 (3), pp. 877-884.

Rogozhin, Y. (1996). "Small Universal Turing Machines". Theoret. Comput. Sci., 168, pp. 215-240.

Shannon, C. E. (1956). "A Universal Turing Machine with Two Internal States". In Automata Studies. Princeton, NJ: Princeton University Press, pp. 157-165.

Solomonoff, R. (1964). "A Formal Theory of Inductive Inference Part I". Information and Control, 7 (1), pp. 1-22.

Suppes, P. (1972, 1960). Axiomatic Set Theory. New York: Dover.

Svozil, K. (1995). "Quantum algorithmic information theory", eprint arXiv:quantph/9510005

Svozil, K. (1995b). "Halting probability amplitude of quantum computers". Journal of Universal Computer Science, 1 (3).

Turing, A. M. (1936). "On computable numbers, with an application to the Entscheidungsproblem". Proc. London Math. Soc. { [2] } 42 (1936-37), 230-265; Correction, ibid., 43 (1937), 544-546. Online open access

Turing, A. M. (1946). "Proposed Electronic Calculator" (ACE), National Physical Laboratory internal document (1946). The original copy is in the (British) National Archives, in the file DSIR 10/385. first published as the NPL report, Com. Sci. 57 (1972), with a foreword by Donald W. Davies.

Thue, A. (1906). "Fiber unendliche Zeichenreihen". Norske vid. Selsk. Skr. Mat. Nat. Kl., 7, pp. 1-22. Reprinted in Selected Mathematical Papers of Axel Thue (Ed. T. Nagell). Oslo: Universitetsforlaget, pp. 139-158, 1977. M. Morse, "Recurrent Geodesics on a Surface of Negative Curvature." Trans. Amer. Math. Soc. 22, 84-100, (1921).

Van den Nest, M.; Du.r, W.; Raussendorf, R. and Briegel, H. J. (2009). "Quantum algorithms for spin models and simulable gate sets for quantum computation". Phys. Rev. A, 80, 052334.

Vitanyi, P. (2000). "Three Approaches to the Quantitative Definition of Information in an Individual Pure Quantum State", arXiv: retrieved from quantph/9907035.

Weyl, H. (1927). Philosophy of Mathematics and Natural Science, translated by Olaf Helmer with a new introduction by Franck Wilczek. Princeton University Press, New Jersey (1949). Parts of this book were originally published by R. Oldenbourg in German in 1927 in Handbuch der Philosophie under the title "Philosophie der Mathematik and Naturwissenschaft".

Wolfram, S. (2002). Wolfram Tones. Retrieved from

Yao, A. (1993). Proceedings of the 34th IEEE Symposium on the Foundations of Computer Science (IEEE Computer Society, Los Alamitos, CA), p. 352.

Copyright (c) 2013 Consejo Superior de Investigaciones Científicas (CSIC)

Licencia de Creative Commons
Esta obra está bajo una licencia de Creative Commons Reconocimiento 4.0 Internacional.

Contacte con la revista

Soporte técnico