Book contents
- Frontmatter
- Contents
- Turing's legacy: developments from Turing's ideas in logic
- Computability and analysis: the legacy of Alan Turing
- Alan Turing and the other theory of computation (expanded)
- Turing in Quantumland
- Computability theory, algorithmic randomness and Turing's anticipation
- Computable model theory
- Towards common-sense reasoning via conditional simulation: legacies of Turing in Artificial Intelligence
- Mathematics in the age of the Turing machine
- Turing and the development of computational complexity
- Turing machines to word problems
- Musings on Turing's Thesis
- Higher generalizations of the Turing Model
- Step by recursive step: Church's analysis of effective calculability
- Turing and the discovery of computability
- Transfinite machine models
- References
Alan Turing and the other theory of computation (expanded)
Published online by Cambridge University Press: 05 June 2014
By
Edited by
Book contents
- Frontmatter
- Contents
- Turing's legacy: developments from Turing's ideas in logic
- Computability and analysis: the legacy of Alan Turing
- Alan Turing and the other theory of computation (expanded)
- Turing in Quantumland
- Computability theory, algorithmic randomness and Turing's anticipation
- Computable model theory
- Towards common-sense reasoning via conditional simulation: legacies of Turing in Artificial Intelligence
- Mathematics in the age of the Turing machine
- Turing and the development of computational complexity
- Turing machines to word problems
- Musings on Turing's Thesis
- Higher generalizations of the Turing Model
- Step by recursive step: Church's analysis of effective calculability
- Turing and the discovery of computability
- Transfinite machine models
- References
Summary
Abstract. We recognize Alan Turing's work in the foundations of numerical computation (in particular, his 1948 paper “Rounding-Off Errors in Matrix Processes”), its influence in modern complexity theory, and how it helps provide a unifying concept for the two major traditions of the theory of computation.
§1. Introduction. The two major traditions of the theory of computation, each staking claim to similar motivations and aspirations, have for the most part run a parallel non-intersecting course. On one hand, we have the tradition arising from logic and computer science addressing problems with more recent origins, using tools of combinatorics and discrete mathematics. On the other hand, we have numerical analysis and scientific computation emanating from the classical tradition of equation solving and the continuous mathematics of calculus. Both traditions are motivated by a desire to understand the essence of computation, of algorithm; both aspire to discover useful, even profound, consequences.
While the logic and computer science communities are keenly aware of Alan Turing's seminal role in the former (discrete) tradition of the theory of computation, most remain unaware of Alan Turing's role in the latter (continuous) tradition, this notwithstanding the many references to Turing in the modern numerical analysis/computational mathematics literature, e.g., [Bur 10, Hig02, Kah66, TB97, Wil71]. These references are not to recursive/computable analysis (suggested in Turing's seminal 1936 paper), usually cited by logicians and computer scientists, but rather to the fundamental role that the notion of “condition” (introduced in Turing's seminal 1948 paper) plays in real computation and complexity.
- Type
- Chapter
- Information
- Turing's LegacyDevelopments from Turing's Ideas in Logic, pp. 48 - 69Publisher: Cambridge University PressPrint publication year: 2014
References
[BMvN63] , , and , >Solu-tion[s] of linear systems of high order, John von Neumann collected works (, editor), vol. 5, Macmillan, New York, 1963, report prepared for Navy Bureau of Ordnance, 1946, pp. 421-478.
[BL12] and , Certified numerical homotopy tracking, Experimental Mathematics, vol. 21 (2012), no. 1, pp. 69-83.Google Scholar
[BP11] and , Fast linear homotopy to find approximate zeros of polynomial systems, Foundations of Computational Mathematics, vol. 11 (2011), no. 1, pp. 95-129.Google Scholar
[BS09] and , Complexity of Bezout's theorem VII: Distance estimates in the condition metric, Foundations of Computational Mathematics, vol. 9 (2009), no. 2, pp. 179-195.Google Scholar
[BS12] and , The complexity and geometry of numerically solving polynomial systems, 2012, preprint submitted November 7, 2012, arXiv:1211.1528 [math.NA].
[Blu90] , Lectures on a theory of computation and complexity over the reals (or an arbitrary ring), 1989 Lectures in the sciences of complexity II (, editor), Addison Wesley, 1990, pp. 1-47.
[Blu91] , A theory of computation and complexity over the real numbers, Proceedings of the International Congress of Mathematicians (ICM1990) (, editor), vol. 2, Springer-Verlag, 1991, pp. 1492-1507.
[Blu04] , Computing over the reals: Where Turing meets Newton, Notices of the American Mathematical Society, vol. 51 (2004), pp. 1024-1034, http://www.ams.org/notices/200409/fea-blum.pdf.Google Scholar
[Blu13] , Alan Turing and the other theory of computation, Alan Turing: His work and impact ( and , editors), Elsevier, 2013, pp. 377-384.
[BCSS96] , , , and , Algebraic settings for the problem “P ≠ NP?”, The mathematics of numerical analysis, Lectures in Applied Mathematics, vol. 32, American Mathematical Society, 1996, pp. 125-144.
[BCSS98] , Complexity and real computation, Springer, New York, 1998.
[BS86] and , Evaluating rational functions: Infinite precision is finite cost and tractable on average, SIAM Journal on Computing, vol. 15 (1986), no. 2, pp. 384-398.Google Scholar
[BSS89] , , and , On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bulletin of the American Mathematical Society, vol. 21 (1989), pp. 1-46.Google Scholar
[Bur10] , Smoothed analysis of condition numbers, Proceedings of the International Congress of Mathematicians (ICM 2010), vol. 4, World Scientific, 2010, pp. 2609-2633.
[BC11] and , On a problem posed by Steve Smale, Annals of Mathematics, vol. 174 (2011), no. 3, pp. 1785-1836.Google Scholar
[BC13] and , Condition, Grundlehren der mathematischen Wissenschaften, Springer-Verlag, 2013.
[BCL08] , , and , The probability that a slightly perturbed numerical analysis problem is difficult, Mathematics of Computation, vol. 77 (2008), no. 263, pp. 1559-1583.Google Scholar
[Cuc02] , Real computations with fake numbers, Journal of Complexity, vol. 18 (2002), no. 1, pp. 104-134.Google Scholar
[CSS94] , , and , Separation of complexity classes in Koiran's weak model, Theoretical Computer Science, vol. 133 (1994), no. 1, pp. 3-14.Google Scholar
[Dan47] , Origins of the simplex method, A history of scientific computing (, editor), ACM Press, New York, 1990 (1947), pp. 141-151.
[Dem87] , On condition numbers and the distance to the nearest ill-posed problem, Numerische Mathematik, vol. 51 (1987), pp. 251-289, 10.1007/BF01400115.Google Scholar
[DSTT02] , , and , Smoothed analysis of Renegar's condition number for linear programming, SIAM Conference on Optimization, 2002.
[EY36] and , The approximation of one matrix by another of lower rank, Psychometrika, vol. 1 (1936), no. 3, pp. 211-218.Google Scholar
[Ede88] , Eigenvalues andcondition numbers ofrandom matrices, SIAM Journal on Matrix Analysis and Applications, vol. 9 (1988), no. 4, pp. 543-560.Google Scholar
[Ede89] , Eigenvalues and condition numbers of random matrices, PhD Dissertation, MIT, 1989, http://math.mit.edu/~edelman/thesis/thesis.pdf.
[Fed69] , Geometric measure theory, Grundlehren der mathematischen Wissenschaften, Springer, 1969.
[FHW48] , , and , Notes on the solution of algebraic linear simultaneous equations, Quarterly Journal of Mechanics and Applied Mathematics, vol. 1 (1948), pp. 149-173.Google Scholar
[Gau03] , Letter to Gerling, December 26, 1823, Werke, vol. 9 (1903), pp. 278-281, English translation, by George E. Forsythe, Mathematical tables and other aids to computation, vol. 5 (1951) pp. 255–258.Google Scholar
[GvN63] and , On the principles of large scale computingmachines (unpublished), John von Neumann collected works (, editor), vol. 5, Macmillan, New York, 1963, pp. 1-33.
[Grc11] , John von Neumann's analysis of Gaussian elimination and the origins of modern numerical analysis, SIAM Review, vol. 53 (2011), pp. 607-682.Google Scholar
[Hig02] , Accuracy and stability of numerical algorithms, second ed., Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2002.
[Hod92] , Alan Turing: The enigma, Vintage, 1992.
[Hot43] , Some new methods in matrix calculation, Annals of Mathematical Statistics, vol. 14 (1943), no. 1, pp. 1-34.Google Scholar
[Hou58] , A class of methods for inverting matrices, Journal of the Society for Industrial and Applied Mathematics, vol. 6 (1958), pp. 189-195.Google Scholar
[Kah66] , Numerical linear algebra, Canadian Mathematical Bulletin, vol. 9 (1966), pp. 757-801.Google Scholar
[KM72] and , How good is the simplex algorithm?, Inequalities III. Proceedings of the third symposium on inequalities (New York) (, editor), Academic Press, 1972, pp. 159-175.
[Kos88] , Complexity theory of numerical linear algebra, Journal of Computational and Applied Mathematics, vol. 22 (1988), no. 2–3, pp. 219-230.Google Scholar
[New55] , Alan Mathison Turing. 1912–1954, Biographical Memoirs of Fellows of the Royal Society, vol. 1 (1955), pp. 253-263.Google Scholar
[PER89] and , Computability in analysis and physics, Perspectives in mathematical logic, Springer Verlag, 1989.
[Ren88a] , A faster PSPACE algorithm for deciding the existential theory of the reals, Proceedings of the 29th annual symposium on Foundations of Computer Science, IEEE Computer Society, 1988, pp. 291-295.
[Ren88b] , A polynomial-time algorithm, basedon Newton's method,for linear programming, Mathematical Programming, vol. 40 (1988), pp. 59-93.Google Scholar
[Ren89] , On the worst-case arithmetic complexity of approximating zeros of systems of polynomials, SIAM Journal on Computing, vol. 18 (1989), no. 2, pp. 350-370.Google Scholar
[Ren95a] , Incorporating condition measures into the complexity theory of linear programming, SIAM Journal on Optimization, vol. 5 (1995), no. 3, pp. 506-524.Google Scholar
[Ren95b] , Linear programming, complexity theory and elementary functional analysis, Mathematical Programming, vol. 70 (1995), pp. 279-351.Google Scholar
[San04] , Integral geometry and geometric probability, Cambridge Mathematical Library, Cambridge University Press, 2004.
[Shu94] , Mysteries of mathematics and computation, The Mathematical Intelligencer, vol. 16 (1994), pp. 10-15.Google Scholar
[Shu09] , Complexity of Bezout's theorem VI: Geodesies in the condition (number) metric, Foundations of Computational Mathematics, vol. 9 (2009), no. 2, pp. 171-178.Google Scholar
[SS94] and , Complexity of Bezout's theorem V: Polynomial time, Theoretical Computer Science, vol. 133 (1994), pp. 141-164.Google Scholar
[Sma81] , The fundamental theorem of algebra and complexity theory, American Mathematical Society. Bulletin, vol. 4 (1981), no. 1, pp. 1-36.Google Scholar
[Sma97] , Complexity theory and numerical analysis, Acta Numerica, vol. 6 (1997), pp. 523-551.Google Scholar
[Sma00] , Mathematical problems for the next century, Mathematics: Frontiers and perspectives (, , , and , editors), American Mathematical Society, 2000, pp. 271-294.
[ST01] and , Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, Journal of the ACM, (2001), pp. 296-305.Google Scholar
[Tar51] , A decision method for elementary algebra and geometry, University of California Press, 1951.
[Tod50] , The condition of a certain matrix, Proceedings of the Cambridge Philosophical Society, vol. 46 (1950), pp. 116-118.Google Scholar
[Tod68] , On condition numbers, Programmation en mathématiques numériques, Besançon, 1966, vol. 7, Éditions du Centre National de la Recherche Scientifique, Paris, no. 165, 1968, pp. 141-159.
[TB97] and , Numerical linear algebra, SIAM, 1997.
[Tur36] , On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society. Second Series, vol. 42 (1936), no. 1, pp. 230-265.Google Scholar
[Tur45] , Proposal for development in the Mathematics Division of an Automatic Computing Engine (ACE), Report E.882, Executive Committee, inst-NPL, 1945.
[Tur48] , Rounding-off errors in matrix processes, Quarterly Journal of Mechanics and Applied Mathematics, vol. 1 (1948), pp. 287-308.Google Scholar
[vN89] , The principles of large-scale computing machines, Annals of the History of Computing, vol. 10 (1989), no. 4, pp. 243-256, transcript of lecture delivered on May 15, 1946.Google Scholar
[vNG47] and , Numerical inverting of matrices of high order, Bulletin of the American Mathematical Society, vol. 53 (1947), no. 11, pp. 1021-1099.Google Scholar
[Wei00] , Computable analysis: An introduction, Texts in Theoretical Computer Science, Springer, 2000.
[Wey39] , On the volume of tubes, American Journal of Mathematics, vol. 61 (1939), pp. 461-472.Google Scholar
[Wil63] , Rounding errors in algebraic processes, Notes on Applied Science No. 32, Her Majesty's Stationery Office, London, 1963, also published by Prentice-Hall, Englewood Cliffs, NJ, USA and reprinted by Dover, New York, 1994.
[Wil71] , Some comments from a numerical analyst, Journal of the ACM, vol. 18 (1971), no. 2, pp. 137-147, 1970 Turing Lecture.Google Scholar
[Wit36] , Einfluß der Änderung einer Matrix auf die Losung des zugehörigen Gleichungssystems, sowie auf die charakteristischen Zahlen und die Eigenvektoren, Zeitscrift für Angewandte Mathematik und Mechanik, vol. 16 (1936), pp. 287-300.Google Scholar
- 1
- Cited by