Alan Turing y los orígenes de la complejidad

Miguel Angel Martin-Delgado

doi:10.3989/arbor.2013.764n6006

Authors

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

DOI:

https://doi.org/10.3989/arbor.2013.764n6006

Keywords:

Turing Machine, Computability, Algorithmic Complexity, Computational Complexity, Complexity Classes, Chaitin Omega, Algorithmic Entropy, Turing Barrier

Abstract

The 75th anniversary of Turing’s seminal paper and his centennial anniversary occur in 2011 and 2012, respectively. It is natural to review and assess Turing’s contributions in diverse fields in the light of new developments that his thought has triggered in many scientific communities. Here, the main idea is to discuss how the work of Turing allows us to change our views on the foundations of Mathematics, much as quantum mechanics changed our conception of the world of Physics. Basic notions like computability and universality are discussed in a broad context, placing special emphasis on how the notion of complexity can be given a precise meaning after Turing, i.e., not just qualitatively but also quantitatively Turing’s work is given some historical perspective with respect to some of his precursors, contemporaries and mathematicians who took his ideas further.

Downloads

Download data is not yet available.

References

Aaronson, S.; Kuperberg, G. and Granade, C. (2005). "The Complexity Zoo", retrieved from https://complexityzoo.uwaterloo.ca/ComplexityZoo

Association for Computing Machinery (2001). Retrieved from http://awards.acm.org/

Bernstein, E. and Vazirani, U. (1997). "Quantum complexity theory". SIAM J. Comput., 26, pp. 1411-1473. http://dx.doi.org/10.1137/S0097539796300921

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. http://dx.doi.org/10.1007/BF03019651

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

Bozkurt, B. (2011). Otomata - Online Generative Musical Sequencer. Retrieved from http://www.earslap.com/projectslab/ otomata

Chaitin, G. J. (1966). "On the length of programs for computing finite binary sequences". Journal of the ACM, 13, pp. 547-569. http://dx.doi.org/10.1145/321356.321363

Chaitin, G. J. (1975). "A theory of program size formally identical to information theory". J. ACM, 22, pp. 329-340. http://dx.doi.org/10.1145/321892.321894

Chaitin, G. J. (1987). Algorithmic Information Theory. Cambridge University Press. http://dx.doi.org/10.1017/CBO9780511608858

Chaitin, G. J. (2001). Exploring randomness. London: Springer-Verlag. http://dx.doi.org/10.1007/978-1-4471-0307-3

Chaitin, G. J. (2003). The Limits of Mathematics. London: Springer-Verlag. http://dx.doi.org/10.1007/978-1-4471-0015-7

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. http://dx.doi.org/10.1142/9789814374309_0015

Calude, C. S. (2002). Information and Randomness. An Algorithmic Perspective. Second Edition. Berlin, Heidelberg, New York: Springer-Verlag. http://dx.doi.org/10.1007/978-3-662-04978-5

Calude, C. S.; Dinneen, M. J. and Shu, C.-K. (2002). "Computing a glimpse of randomness". Exper. Math., 11, pp. 361-370. http://dx.doi.org/10.1080/10586458.2002.10504481

Calude, C. S. and Pavlov, B. (2002). "Coins, Quantum Measurements, and Turing's Barrier". Quantum Information Processing, 1 (1-2). http://dx.doi.org/10.1023/A:1019623616675

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. http://dx.doi.org/10.1073/pnas.50.6.1143

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. http://dx.doi.org/10.1038/scientificamerican0499-98

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. http://dx.doi.org/10.1007/BF02650179

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. http://dx.doi.org/10.1103/RevModPhys.74.347

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. http://dx.doi.org/10.1007/BF01700692

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. http://dx.doi.org/10.1016/S0019-9958(66)80018-9

Millen, D. (1990). "Cellular Automata Music". In International Computer Music Conference, Glasgow. Retrieved from http://comp.uark.edu/dmillen/cam.html

Minsky, M. L., (1962). "Size and Structure of Universal Turing Machines Using Tag Systems". Proc. Sympos. Pure Math. 5, pp. 229-238. http://dx.doi.org/10.1090/pspum/005/0142452

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). http://dx.doi.org/10.1103/PhysRevLett.95.200503

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: http://www.ntnu.no/ub/spesialsamlingene/ebok/02a019654.html.

Oliveira e Silva, T. (2012). Retrieved from http://www.ieeta.pt/tos/3x+1.html

Radó, T. (1962). "On non-computable functions". Bell System Technical Journal, 41 (3), pp. 877-884. http://dx.doi.org/10.1002/j.1538-7305.1962.tb00480.x

Rogozhin, Y. (1996). "Small Universal Turing Machines". Theoret. Comput. Sci., 168, pp. 215-240. http://dx.doi.org/10.1016/S0304-3975(96)00077-1

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. http://dx.doi.org/10.1016/S0019-9958(64)90223-2

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 http://www.abelard.org/turpap2/tp2-ie.asp.

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. http://dx.doi.org/10.1103/PhysRevA.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 http://tones.wolfram.com/

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