Skip to main content Accessibility help
×
Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-09T05:46:00.762Z Has data issue: false hasContentIssue false

Computability and analysis: the legacy of Alan Turing

Published online by Cambridge University Press:  05 June 2014

Jeremy Avigad
Affiliation:
Carnegie Mellon University
Vasco Brattka
Affiliation:
University of Cape Town
Rod Downey
Affiliation:
Victoria University of Wellington
Get access

Summary

§1. Introduction. For most of its history, mathematics was algorithmic in nature. The geometric claims in Euclid's Elements fall into two distinct categories: “problems,” which assert that a construction can be carried out to meet a given specification, and “theorems,” which assert that some property holds of a particular geometric configuration. For example, Proposition 10 of Book I reads “To bisect a given straight line.” Euclid's “proof” gives the construction, and ends with the (Greek equivalent of) Q.E.F., for quod erat faciendum, or “that which was to be done.” Proofs of theorems, in contrast, end with Q.E.D., for quod erat demonstrandum, or “that which was to be shown”; but even these typically involve the construction of auxiliary geometric objects in order to verify the claim.

Similarly, algebra was devoted to developing algorithms for solving equations. This outlook characterized the subject from its origins in ancient Egypt and Babylon, through the ninth century work of al-Khwarizmi, to the solutions to the quadratic and cubic equations in Cardano's Ars Magna of 1545, and to Lagrange's study of the quintic in his Réflexions sur la résolution algébrique des équations of 1770.

The theory of probability, which was born in an exchange of letters between Blaise Pascal and Pierre de Fermat in 1654 and developed further by Christian Huygens and Jakob Bernoulli, provided methods for calculating odds related to games of chance.

Type
Chapter
Information
Turing's Legacy
Developments from Turing's Ideas in Logic
, pp. 1 - 47
Publisher: Cambridge University Press
Print publication year: 2014

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Oliver, Aberth, The failure in computable analysis of a classical existence theorem for differential equations, Proceedings of the American Mathematical Society, vol. 30 (1971), pp. 151-156.Google Scholar
[2] Oliver, Aberth, Computable analysis, McGraw-Hill, New York, 1980.
[3] N. L., Ackerman, C. E., Freer, and D. M., Roy, Noncomputable conditional distributions, Logic in Computer Science (LICS), 2011, IEEE Conference Presentations, Los Alamitos, California, 2011, pp. 107-116.
[4] Thorsten, Altenkirch, Proving strong normalization of CC by modifying realizability semantics, Types for proofs and programs (Nijmegen, 1993), Springer, Berlin, 1994, pp. 3-18.
[5] Jeremy, Avigad, Interpreting classical theories in constructive ones, The Journal of Symbolic Logic, vol. 65 (2000), pp. 1785-1812.Google Scholar
[6] Jeremy, Avigad, Uncomputably noisy ergodic limits, Notre Dame Journal of Formal Logic, vol. 53 (2012), pp. 347-350.Google Scholar
[7] Jeremy, Avigad and Solomon, Feferman, Gödel's functional (“Dialectica”) interpretation, Handbook of proof theory (Samuel R., Buss, editor), North-Holland, Amsterdam, 1998, pp. 337-405.
[8] Jeremy, Avigad, Philipp, Gerhardy, and Henry, Towsner, Local stability of ergodic averages, Transactions of the American Mathematical Society, vol. 362 (2010), pp. 261-288.Google Scholar
[9] Jeremy, Avigad and Ksenija, Simic, Fundamental notions of analysis in subsystems of second-order arithmetic, Annals of Pure and Applied Logic, vol. 139 (2006), pp. 138-184.Google Scholar
[10] G., Baigger, Die Nichtkonstruktivität des Brouwerschen Fixpunktsatzes, Archiv für Mathematische Logik und Grundlagenforschung, vol. 25 (1985), pp. 183-188.Google Scholar
[11] Stefan, Banach and Stanisław, Mazur, Sur les fonctions calculables, Annales de la Société Polonaise de Mathématique, vol. 16 (1937), p. 223.Google Scholar
[12] Andrej, Bauer, The realizability approach to computable analysis and topology, Ph.D. thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, 2000.
[13] Verónica, Becher, Santiago, Figueira, and Rafael, Picchi, Turing's unpublished algorithm for normal numbers, Theoretical Computer Science, vol. 377 (2007), pp. 126-138.Google Scholar
[14] Michael J., Beeson, Foundations of constructive mathematics, Springer, Berlin, 1985.
[15] Laurent, Bienvenu, Adam R., Day, Mathieu, Hoyrup, Ilya, Mezhirov, and Alexander, Shen, A constructive version of Birkhoffs ergodic theorem for Martin-Löf random points, Information and Computation, vol. 210 (2012), pp. 21-30.Google Scholar
[16] Errett, Bishop, Foundations of constructive analysis, McGraw-Hill, New York, 1967.
[17] Errett, Bishop and Douglas S., Bridges, Constructive analysis, Springer, Berlin, 1985.
[18] Émile, Borel, Le calcul des intégrales définies, Journal de Mathematiques Pures et Appliquees. Serie 6, vol. 8 (1912), pp. 159-210.Google Scholar
[19] Émile, Borel, La théorie de la mesure et al théorie de l'integration, Leçons sur la théorie des fonctions, Gauthier-Villars, Paris, 1950, pp. 214-256.Google Scholar
[20] Volker, Bosserhoff, Notions of probabilistic computability on represented spaces, Journal of Universal Computer Science, vol. 14 (2008), pp. 956-995.Google Scholar
[21] Vasco, Brattka, Effective Borel measurability and deducibility of functions, Mathematical Logic Quarterly, vol. 51 (2005), pp. 19-44.Google Scholar
[22] Vasco, Brattka and Guido, Gherardi, Effective choice and boundedness principles in computable analysis, The Bulletin of Symbolic Logic, vol. 17 (2011), pp. 73-117.Google Scholar
[23] Vasco, Brattka, Weihrauch degrees, omniscience principles and weak computability, The Journal of Symbolic Logic, vol. 76 (2011), pp. 143-176.Google Scholar
[24] Vasco, Brattka, Guido, Gherardi, and Alberto, Marcone, The Bolzano–Weierstrass theorem is the jump of weak Kőnig's lemma, Annals of Pure and Applied Logic, vol. 163 (2012), pp. 623-655.Google Scholar
[25] Vasco, Brattka, Peter, Hertling, and Klaus, Weihrauch, A tutorial on computable analysis, New computational paradigms: Changing conceptions of what is computable (S. Barry, Cooper, Benedikt, Löwe, and Andrea, Sorbi, editors), Springer, New York, 2008, pp. 425-491.
[26] Vasco, Brattka, Joseph S., Miller, and André, Nies, Randomness and differentiability, submitted; preliminary version at http://arxiv.org/abs/1104.4465.
[27] Mark, Braverman, Parabolic Julia sets are polynomial time computable, Nonlinearity, vol. 19 (2006), pp. 1383-1401.Google Scholar
[28] Mark, Braverman and Stephen, Cook, Computing over the reals: Foundations for scientific computing, Notices of the American Mathematical Society, vol. 53 (2006), pp. 318-329.Google Scholar
[29] Mark, Braverman and M., Yampolsky, Non-computable Julia sets, Journal of the American Mathematical Society, vol. 19 (2006), pp. 551-578.Google Scholar
[30] Mark, Braverman and Michael, Yampolsky, Computability of Julia sets, Springer, Berlin, 2008.
[31] Douglas, Bridges and Fred, Richman, Varieties of constructive mathematics, Cambridge University Press, Cambridge, 1987.
[32] L. E. J., Brouwer, Begründung der Mengenlehre unabhängig vom logischen Satz vom ausgeschlossen Dritten. Erster Teil: Allgemeine Mengenlehre, Koninklijke Nederlandse Akademie van Wetenschappen te Amsterdam, vol. 12 (1918), no. 5, reprinted in [35], pp. 150-190.Google Scholar
[33] L. E. J., Brouwer, Begründung der Mengenlehre unabhängig vom logischen Satz vom ausgeschlossen Dritten. Zweiter Teil: Theorie der Punkmengen, Koninklijke Nederlandse Akademie van Wetenschappen te Amsterdam, vol. 12 (1919), no. 7, reprinted in [35], pp. 191-221.Google Scholar
[34] L. E. J., Brouwer, Über Definitionsbereiche von Funktionen, Mathematische Annalen, vol. 97 (1927), no. 1, pp. 60-75.Google Scholar
[35] L. E. J., Brouwer, Collected works, volume I: Philosophy and foundations of mathematics, (A., Heyting, editor), North-Holland Publishing Company, Amsterdam, 1975.
[36] G. S., Ceitin, Algorithmic operators in constructive complete separable metric spaces, Doklady Akademii Nauk, vol. 128 (1959), pp. 49-52, (in Russian).Google Scholar
[37] Douglas, Cenzer and Jeffrey B., Remmel, Index sets in computable analysis, Theoretical Computer Science, vol. 219 (1999), pp. 111-150.Google Scholar
[38] Douglas, Cenzer, Effectively closed sets and graphs of computable real functions, Theoretical Computer Science, vol. 284 (2002), pp. 279-318.Google Scholar
[39] Douglas, Cenzer, Index sets for computable differential equations, Mathematical Logic Quarterly, vol. 50 (2004), pp. 329-344.Google Scholar
[40] Alonzo, Church, A formulation of the simple theory of types, The Journal of Symbolic Logic, vol. 5 (1940), pp. 56-68.Google Scholar
[41] Thierry, Coquand and Martin, Hofmann, A new method of establishing conservativity of classical systems over their intuitionistic version, Mathematical Structures in Computer Science, vol. 9 (1999), pp. 323-333.Google Scholar
[42] Thierry, Coquand and Gérard, Huet, The calculus of constructions, Information and Computation, vol. 76 (1988), pp. 95-120.Google Scholar
[43] Thierry, Coquand and Christine, Paulin, Inductively defined types, COLOG-88 (Tallinn, 1988), Springer, Berlin, 1990, pp. 50-66.
[44] Thierry, Coquand and Arnaud, Spiwack, A proof of strong normalisation using domain theory, Logical Methods in Computer Science, vol. 3 (2007), no. 4.Google Scholar
[45] Haskell B., Curry, Functionality in combinatory logic, Proceedings of the National Academy of Sciences, vol. 20 (1934), pp. 584-590.Google Scholar
[46] Haskell B., Curry and Robert, Feys, Combinatory logic, vol. I, North-Holland, Amsterdam, 1958.
[47] Martin, Davis, The universal computer: The road from Leibniz to Turing, W. W. Norton, New York, 2000.
[48] Osvald, Demuth, Constructive pseudonumbers, Commentationes Mathematicae Universitatis Carolinae, vol. 16 (1975), pp. 315-331, (in Russian).Google Scholar
[49] Osvald, Demuth, The differentiability of constructive functions of weakly bounded variation on pseudo numbers, Commentationes Mathematicae Universitatis Carolinae, vol. 16 (1975), pp. 583-599, (in Russian).Google Scholar
[50] Rodney G., Downey and Denis R., Hirschfeldt, Algorithmic randomness and complexity, Springer, New York, 2010.
[51] Albert, Dragalin, Mathematical intuitionism: Introduction to proof theory, American Mathematical Society, Providence, Rhode Island, 1988.
[52] Michael, Dummett, Elements of intuitionism, second ed., Oxford University Press, New York, 2000.
[53] Abbas, Edalat, A computable approach to measure and integration theory, Information and Computation, vol. 207 (2009), pp. 642-659.Google Scholar
[54] Abbas, Edalat and Philipp, Sünderhauf, A domain-theoretic approach to computability on the real line, Theoretical Computer Science, vol. 210 (1999), pp. 73-98.Google Scholar
[55] Harold M., Edwards, Kronecker's views on the foundations of mathematics, The history of modern mathematics (D. E., Rowe and J., McCleary, editors), Academic Press, San Diego, 1989, pp. 67-77.
[56] Harold M., Edwards, Kronecker's fundamental theorem of general arithmetic, Episodes in the history of modern algebra (1800–1950), American Mathematical Society, Providence, Rhode Island, 2007, pp. 107-116.
[57] Harold M., Edwards, Kronecker's algorithmic mathematics, Mathematical Intelligencer, vol. 31 (2009), pp. 11-14.Google Scholar
[58] William, Ewald (editor), From Kant to Hilbert: A source book in the foundations of mathematics, vol. 1 and 2, Oxford University Press, Oxford, 1996.
[59] Johanna, Franklin, Noam, Greenberg, Joseph S., Miller, and Keng, Mengng, Martin-Löf random points satisfy Birkhoff's ergodic theorem for effectively closed sets, Proceedings of the American Mathematical Society, vol. 140 (2012), pp. 3623-3628.Google Scholar
[60] Johanna, Franklin and Henry, Towsner, Randomness and non-ergodic systems, arXiv:1206.2682.
[61] Cameron, Freer, Bjørn, Kjos-Hanssen, André, Nies, and Frank, Stephan, Algorithmic aspects of Lipschitz functions, preprint.
[62] Cameron E., Freer and Daniel M., Roy, Computable de Finetti measures, Annals of Pure and Applied Logic, vol. 163 (2012), pp. 530-546.Google Scholar
[63] Gottlob, Frege, Grundgesetze der Arithmetik, Band I, Hermann Pohle, Jena, 1893.
[64] Harvey, Friedman, On the computational complexity of maximization and integration, Advances in Mathematics, vol. 53 (1984), pp. 80-98.Google Scholar
[65] Harvey M., Friedman, Classically and intuitionistically provable functions, Higher set theory (H., Müller and D., Scott, editors), Springer, Berlin, 1978, pp. 21-27.
[66] Peter, Gács, Uniform test of algorithmic randomness over a general space, Theoretical Computer Science, vol. 341 (2005), pp. 91-137.Google Scholar
[67] Peter, Gács, Mathieu, Hoyrup, and Cristóbal, Rojas, Randomness on computable probability spaces—a dynamical point of view, Theory of Computing Systems, vol. 48 (2011), pp. 465-485.Google Scholar
[68] Stefano, Galatolo, Mathieu, Hoyrup, and Cristóbal, Rojas, A constructive Borel–Cantelli lemma: constructing orbits with required statistical properties, Theoretical Computer Science, vol. 410 (2009), pp. 2207-2222.Google Scholar
[69] Stefano, Galatolo, Mathieu, Hoyrup, and Cristóbal, Rojas, Effective symbolic dynamics, random points, statistical behavior, complexity and entropy, Information and Computation, vol. 208 (2010), pp. 23-41.Google Scholar
[70] Gerhard, Gentzen, Die Widerspruchsfreiheit der reinen Zahlentheorie, Mathematische Annalen, vol. 112 (1936), pp. 493–465, translated as The consistency of elementary number theory in [71], pp. 132–213.Google Scholar
[71] Gerhard, Gentzen, Collected works, (M. E., Szabo, editor), North-Holland, Amsterdam, 1969.
[72] Guido, Gherardi, Alan Turing and the foundations of computable analysis, The Bulletin of Symbolic Logic, vol. 17 (2011), pp. 394-430.Google Scholar
[73] Guido, Gherardi and Alberto, Marcone, How incomputable is the separable Hahn–Banach theorem?, Notre Dame Journal of Formal Logic, vol. 50 (2009), pp. 393-425.Google Scholar
[74] Jean-Yves, Girard, Une extension de l'interprétation de Gödel à l'analyse, et son application à l'élimination des coupures dans l'analyse et la théorie des types, Proceedings of the second Scandinavian Logic Symposium, North-Holland, Amsterdam, 1971, pp. 63-92.
[75] Jean-Yves, Girard, Yves, Lafont, and Paul, Taylor, Proofs and types, Cambridge University Press, 1989.
[76] Kurt, Gödel, Zur intuitionistischen Arithmetik und Zahlentheorie, Ergebnisse eines mathematischen Kolloquiums, vol. 4 (1933), pp. 34-38, translated by Stefan, Bauer-Mengelberg and Jean, van Heijenoort as On intuitionistic arithmetic and number theory in [217], reprinted in [78] (1933e),pp. 287-295.
[77] Kurt, Gödel, Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes, Dialectica, vol. 12 (1958), pp. 280-287, reprinted with English translation in Feferman et al., (editors), Kurt Gödel: Collected Works, volume 2, Oxford University Press, New York, 1990, pp. 241-251.
[78] Kurt, Gödel, Collected works, (Solomon, Feferman et al., editors), vol. I, Oxford University Press, New York, 1986.
[79] R. L., Goodstein, Recursive number theory: A development of recursive arithmetic in a logic-free equation calculus, North-Holland, Amsterdam, 1957.
[80] R. L., Goodstein, Recursive analysis, North-Holland, Amsterdam, 1961.
[81] Timothy G., Griffin, A formulae-as-type notion of control, Proceedings of the 17th ACM SIGPLAN–SIGACT symposium on Principles of Programming Languages (POPL '90), Association for Computing Machinery, New York, 1990, pp. 47-58.
[82] Andrzej, Grzegorczyk, Computable functionals, Fundamenta Mathematicae, vol. 42 (1955), pp. 168-202.
[83] Andrzej, Grzegorczyk, On the definition of computable functionals, Fundamenta Mathematicae, vol. 42 (1955), pp. 232-239.Google Scholar
[84] Andrzej, Grzegorczyk, On the definitions of computable real continuous functions, Fundamenta Mathematicae, vol. 44 (1957), pp. 61-71.Google Scholar
[85] Andrzej, Grzegorczyk, Some approaches to constructive analysis, Constructivity in mathematics (A., Heyting, editor), North-Holland, Amsterdam, 1959, pp. 43-61.
[86] Jürgen, Hauck, Ein Kriterium für die Annahme des Maximums in der Berechenbaren Analysis, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 17 (1971), pp. 193-196.Google Scholar
[87] Jürgen, Hauck, Konstruktive Darstellungen reeller Zahlen und Folgen, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 24 (1978), pp. 365-374.Google Scholar
[88] Jürgen, Hauck, Konstruktive Darstellungen in topologischen Raumen mit rekursiver Basis, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 26 (1980), pp. 565-576.Google Scholar
[89] Peter, Hertling, Effectivity andeffective continuity offunctions between computable metric spaces, Combinatorics, complexity, and logic (Douglas S., Bridges, Cristian S., Calude, Jeremy, Gibbons, Steve, Reeves, and Ian H., Witten, editors), Springer, Singapore, 1997.
[90] Peter, Hertling, An effective Riemann Mapping Theorem, Theoretical Computer Science, vol. 219 (1999), pp. 225-265.Google Scholar
[91] Peter, Hertling, A real number structure that is effectively categorical, Mathematical Logic Quarterly, vol. 45 (1999), pp. 147-182.Google Scholar
[92] Peter, Hertling, A Banach–Mazur computable but not Markov computable function on the computable real numbers, Annals of Pure and Applied Logic, vol. 132 (2005), pp. 227-246.Google Scholar
[93] Peter, Hertling and Klaus, Weihrauch, Random elements in effective topological spaces with measure, Information and Computation, vol. 181 (2003), pp. 32-56.Google Scholar
[94] Arendt, Heyting, Die formalen Regeln der intuitionistischen Logik. I, II, III, Sitzungsberichte der königlich-preussischen Akademie der Wissenschaften. Berlin, (1930), pp. 42–56, 57–71, and 158-169.
[95] Arendt, Heyting, Intuitionism: An introduction, North-Holland, Amsterdam, 1956.
[96] David, Hilbert and Paul, Bernays, Grundlagen der Mathematik, vol. 1, Springer, Berlin, 1934, vol. 32, 1939.
[97] W. A., Howard, The formulae-as-types notion of construction, To H. B. Curry: Essays on combinatory logic, lambda calculus and formalism, Academic Press, London, 1980, pp. 480-490.
[98] Mathieu, Hoyrup and Cristóbal, Rojas, Computability of probability measures and Martin-Löfrandomness over metric spaces, Information and Computation, vol. 207 (2009), pp. 830-847.Google Scholar
[99] Mathieu, Hoyrup, Cristóbal, Rojas, and Klaus, Weihrauch, Computability of the Radon–Nikodym derivative, Models of computation in context (Benedikt, Löwe, Dag, Normann, Ivan, Soskov, and Alexandra, Soskova, editors), Springer, Berlin, 2011, pp. 132-141.
[100] Mathieu, Hoyrup, Computability of the Radon–Nikodym derivative, Computability, vol. 1 (2012), pp. 3-13.Google Scholar
[101] J. M. E., Hyland, The effective topos, The L.E.J. Brouwer Centenary Symposium (Noordwijkerhout, 1981), North-Holland, Amsterdam, 1982, pp. 165-216.
[102] Iraj, Kalantari and Larry, Welch, A blend of methods of recursion theory and topology, Annals of Pure and Applied Logic, vol. 124 (2003), pp. 141-178.Google Scholar
[103] Iraj, Kalantari and Lawrence, Welch, Point-free topological spaces, functions and recursive points; filter foundation for recursive analysis. I, Annals of Pure and Applied Logic, vol. 93 (1998), pp. 125-151.Google Scholar
[104] Iraj, Kalantari, Recursive and nonextendible functions over the reals; filter foundation for recursive analysis, II, Annals of Pure and Applied Logic, vol. 98 (1999), pp. 87-110.Google Scholar
[105] Akitoshi, Kawamura, Lipschitz continuous ordinary differential equations are polynomial-space complete, Computational Complexity, vol. 19 (2010), pp. 305-332.Google Scholar
[106] Akitoshi, Kawamura and Stephen, Cook, Complexity theory for operators in analysis, Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC '10), Association for Computing Machinery, New York, 2010, pp. 495-502.
[107] Dieter, Klaua, Berechenbare Analysis, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 2 (1956), pp. 265-303.Google Scholar
[108] Dieter, Klaua, Konstruktive Analysis, Deutscher Verlag der Wissenschaften, Berlin, 1961.
[109] Stephen Cole, Kleene, Recursive predicates and quantifiers, Transactions of the American Mathematical Society, vol. 53 (1943), pp. 41-73.Google Scholar
[110] Stephen Cole, Kleene, On the interpretation of intuitionistic number theory, The Journal of Symbolic Logic, vol. 10 (1945), pp. 109-124.Google Scholar
[111] Stephen Cole, Kleene, Introduction to metamathematics, D. Van Nostrand Company, New York, 1952.
[112] Stephen Cole, Kleene and Richard Eugene, Vesley, The foundations of intuitionistic mathematics, especially in relation to recursive functions, North-Holland, Amsterdam, 1965.
[113] Ker-I, Ko, The maximum value problem and NP real numbers, Journal of Computer and Systems Sciences, vol. 24 (1982), pp. 15-35.Google Scholar
[114] Ker-I, Ko, Some negative results on the computational complexity of total variation and differentiation, Information and Control, vol. 53 (1982), pp. 21-31.Google Scholar
[115] Ker-I, Ko, On the computational complexity of ordinary differential equations, Information and Control, vol. 58 (1983), pp. 157-194.Google Scholar
[116] Ker-I, Ko, On the computational complexity of integral equations, Annals of Pure and Applied Logic, vol. 58 (1992), pp. 201-228.Google Scholar
[117] Ker-I, Ko and H., Friedman, Computational complexity of real functions, Theoretical Computer Science, vol. 20 (1982), pp. 323-352.Google Scholar
[118] Ker-I, Ko, Computing power series in polynomial time, Advances in Applied Mathematics, vol. 9 (1988), pp. 40-50.Google Scholar
[119] Ulrich, Kohlenbach, Applied proof theory: Proof interpretations and their use in mathematics, Springer, Berlin, 2008.
[120] Georg, Kreisel, On the interpretation of non-finitist proofs II. Interpretation of number theory. Applications, The Journal of Symbolic Logic, vol. 17 (1952), pp. 43-58.Google Scholar
[121] Georg, Kreisel, Some elementary inequalities, Koninklijke Nederlandse Akademie van Wetenschappen, Proceedings, Series A, vol. 55 (1952), pp. 334-338, Indagationes Mathematicae, vol. 14.Google Scholar
[122] Georg, Kreisel and Daniel, Lacombe, Ensembles récursivement mesurables et ensembles recursivement ouverts et fermés, Comptes Rendus de l'Académie des Sciences. Paris, vol. 245 (1957), pp. 1106-1109.Google Scholar
[123] Georg, Kreisel, Daniel, Lacombe, and J. R., Shoenfield, Fonctionnelles récursivement définissables et fonctionnelles récursives, Comptes Rendus de l'Académie des Sciences. Paris, vol. 245 (1957), pp. 399-402.Google Scholar
[124] Georg, Kreisel, Partial recursive functionals and effective operations, Constructivity in mathematics (A., Heyting, editor), North-Holland, Amsterdam, 1959, pp. 290-297.
[125] Christoph, Kreitz and Klaus, Weihrauch, Theory of representations, Theoretical Computer Science, vol. 38 (1985), pp. 35-53.Google Scholar
[126] Christoph, Kreitz, Compactness in constructive analysis revisited, Annals of Pure and Applied Logic, vol. 36 (1987), pp. 29-38.Google Scholar
[127] Jean-Louis, Krivine, Typed lambda-calculus in classical Zermelo–Frænkel set theory, Archive for Mathematical Logic, vol. 40 (2001), pp. 189-205.Google Scholar
[128] Leopold, Kronecker, Grundzüge einer arithmetischen Theorie der algebraischen Grössen, Riemer, Berlin, 1882, also published in Journal für reine und angewandte Mathematik, vol. 92 (1882), pp. 1–122, and [132], vol. II, pp. 237–387.
[129] Leopold, Kronecker, Ein Fundamentalsatz der allgemeinen Arithmetik, Journal für die reine und angewandte Mathematik, vol. 100 (1887), pp. 490-510, reprinted in [132], vol. IIIa, pp. 209–240.Google Scholar
[130] Leopold, Kronecker, Über den Zahlbegriff, Philosophische Aufsätze, Eduard Zeller zu seinem fünfzigjährigen Doctorjubiläum gewidmet, Fues, Leipzig, 1887, pp. 261-274, reprinted in [132], vol. IIIa, pp. 249–274. Translated as On the concept of number by William Ewald in [58], vol. 2, pp. 947–955.
[131] Leopold, Kronecker, Vorlesungen über Zahlentheorie, (Kurt, Hensel, editor), Teubner, Leipzig, 1901, republished by Springer, Berlin, 1978.
[132] Leopold, Kronecker, Werke, (Kurt, Hensel, editor), vol. 1–5, Chelsea Publishing Company, New York, 1968.
[133] Antonín, Kučera and André, Nies, Demuth's path to randomness, Proceedings of the 2012 international Workshop on Theoretical Computer Science: Computation, physics and beyond (WTCS 2012), Springer, Berlin, 2012, pp. 159-173.
[134] Boris A., Kushner, Lectures on constructive mathematical analysis, American Mathematical Society, Providence, RI, 1984, translated from the Russian by E., Mendelson.
[135] Boris A., Kushner, The constructive mathematics of A. A. Markov, American Mathematical Monthly, vol. 113 (2006), pp. 559-566.Google Scholar
[136] Daniel, Lacombe, Classes récursivement fermés et fonctions majorantes, Comptes Rendus de l'Académie des Sciences. Paris, vol. 240 (1955), pp. 716-718.Google Scholar
[137] Daniel, Lacombe, Extension de la notion de fonction réicursive aux fonctions d'une ou plusieurs variables réelles I–III, Comptes Rendus de l'Académie des Sciences. Paris, vol. 240 and 241 (1955), pp. 2478-2480 and 13–14 and 151–153.Google Scholar
[138] Daniel, Lacombe, Remarques sur les opérateurs récursifs et sur les fonctions récursives d'une variable réelle, Comptes Rendus de l'Académie des Sciences. Paris, vol. 241 (1955), pp. 1250-1252.Google Scholar
[139] Daniel, Lacombe, Les ensembles récursivement ouverts ou fermés, et leurs applications à l'Analyse récursive, Comptes Rendus de l'Academie des Sciences. Paris, vol. 245 (1957), pp. 1040-1043.Google Scholar
[140] Daniel, Lacombe, Quelques propriétés d'analyse récursive, >Comptes Rendus de l'Académie des Sciences. Paris, vol. 244 (1957), pp. 838–840 and 996-997.Google Scholar
[141] Daniel, Lacombe, Les ensembles récursivement ouverts ou férmes, et leurs applications à l'Analyse récursive, Comptes Rendus de l'Académie des Sciences. Paris, vol. 246 (1958), pp. 28-31.Google Scholar
[142] Daniel, Lacombe, Sur les possibilites d'extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables réelles, Le raisonnement en mathematiques et en sciences, Editions du Centre National de la Recherche Scientifique, Paris, 1958, pp. 67-75.
[143] Daniel, Lacombe, Quelques procédés de definition en topologie recursive, Constructivity in mathematics (A., Heyting, editor), North-Holland, Amsterdam, 1959, pp. 129-158.
[144] Peter, Lietz, From constructive mathematics to computable analysis via the realizability interpretation, Ph.D. thesis, Fachbereich Mathematik, TU Darmstadt, Darmstadt, 2004.
[145] Saunders Mac, Lane and Ieke, Moerdijk, Sheaves in geometry and logic, Springer, New York, 1994.
[146] A. A., Markov, On the continuity of constructive functions, Uspekhi Matematicheskikh Nauk, vol. 9 (1954), pp. 226-230, (in Russian).Google Scholar
[147] A. A., Markov, On constructive functions, Trudy Matematicheskogo Instituta Imeni V. A. Steklova, vol. 52 (1958), pp. 315-348, (in Russian, English translation in American Mathematical Society Translations Series 2, vol. 29, 1963).Google Scholar
[148] Per, Martin-Löf, The definition of random sequences, Information and Control, vol. 9 (1966), pp. 602-619.Google Scholar
[149] Per, Martin-Löf, Notes on constructive mathematics, Almqvist and Wiksell, Stockholm, 1970.
[150] Per, Martin-Löf, An intuitionistic theory of types: predicative part, Logic Colloquium '73 (H. E., Rose and J. C., Shepherdson, editors), North-Holland, Amsterdam, 1973.
[151] Alec, Matheson and Timothy H., McNicholl, Computable analysis and Blaschke products, Proceedings of the American Mathematical Society, vol. 136 (2008), pp. 321-332.Google Scholar
[152] Stanisław, Mazur, Computable analysis, Razprawy Matematyczne, Warsaw, 1963.
[153] Timothy H., McNicholl, Uniformly computable aspects of inner functions: estimation and factorization, Mathematical Logic Quarterly, vol. 54 (2008), pp. 508-518.Google Scholar
[154] Timothy H., McNicholl, A uniformly computable implicit function theorem, Mathematical Logic Quarterly, vol. 54 (2008), pp. 272-279.Google Scholar
[155] George, Metakides and Anil, Nerode, The introduction of non-recursive methods into mathematics, The L. E. J. Brouwer Centenary Symposium (A. S., Troelstra and D., van Dalen, editors), North-Holland, Amsterdam, 1982, pp. 319-335.
[156] George, Metakides, Anil, Nerode, and R. A., Shore, Recursive limits on the Hahn–Banach theorem, Errett Bishop: Reflections on him and his research (Murray, Rosenblatt, editor), American Mathematical Society, 1985.
[157] Joseph Stephen, Miller, Pi-0-1 classes in computable analysis and topology, Ph.D. thesis, Cornell University, Ithaca, USA, 2002.
[158] Yiannis Nicholas, Moschovakis, Recursive metric spaces, Fundamenta Mathematicae, vol. 55 (1964), pp. 215-238.Google Scholar
[159] Andrzej, Mostowski, On computable sequences, Fundamenta Mathematicae, vol. 44 (1957), pp. 37-51.Google Scholar
[160] Chetan R., Murthy, An evaluation semantics for classical proofs, Proceedings, Sixth Annual IEEE Symposium on Logic in Computer Science, Amsterdam, 1991, pp. 96-107.
[161] John, Myhill, A recursive function defined on a compact interval and having a continuous derivative that is not recursive, Michigan Mathematical Journal, vol. 18 (1971), pp. 97-98.Google Scholar
[162] David, Nelson, Recursive functions and intuitionistic number theory, Transactions of the American Mathematical Society, vol. 61 (1947), pp. 307-368.Google Scholar
[163] André, Nies, Computability and randomness, Oxford University Press, New York, 2009.
[164] V. P., Orevkov, A constructive mapping of the square onto itself displacing every constructive point, Doklady Akademii Nauk, vol. 152 (1963), pp. 55-58, (in Russian) Translated in: Soviet Mathematics Doklady, vol. 4 (1963), pp. 1253–1256.Google Scholar
[165] Michel, Parigot, λμ-calculus: an algorithmic interpretation of classical natural deduction, Logic programming and automated reasoning (St. Petersburg, 1992), Springer, Berlin, 1992.
[166] Noopur, Pathak, A computational aspect of the lebesgue differentiation theorem, Journal of Logic and Analysis, vol. 1 (2009), pp. 1-15.Google Scholar
[167] Noopur, Pathak, Cristóbal, Rojas, and Stephen G., Simpson, Schnorr randomness and the Lebesgue differentiation theorem, Proceedings of the American Mathematical Society, (to appear).
[168] Arno, Pauly, How incomputable is finding Nash equilibria?, Journal of Universal Computer Science, vol. 16 (2010), pp. 2686-2710.Google Scholar
[169] Arno, Pauly, On the (semi)lattices induced by continuous reducibilities, Mathematical Logic Quarterly, vol. 56 (2010), pp. 488-502.Google Scholar
[170] Roger, Penrose, The emperor's new mind. concerning computers, minds and the laws of physics, Oxford University Press, New York, 1989.
[171] Rózsa, Péter, Rekursive Funktionen, Akademischer Verlag, Budapest, 1951.
[172] Marian, Pour-El and J., Caldwell, On a simple definition of computable functions of a real variable, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 21 (1975), pp. 1-19.Google Scholar
[173] Marian, Pour-El and Ning, Zhong, The wave equation with computable initial data whose unique solution is nowhere computable, Mathematical Logic Quarterly, vol. 43 (1997), pp. 499-509.Google Scholar
[174] Marian Boykan, Pour-El and J. Ian, Richards, A computable ordinary differential equation which possesses no computable solution, Annals of Mathematical Logic, vol. 17 (1979), pp. 61-90.Google Scholar
[175] Marian Boykan, Pour-El and J. Ian, Richards, The wave equation with computable initial data such that its unique solution is not computable, Advances in Mathematics, vol. 39 (1981), pp. 215-239.Google Scholar
[176] Marian Boykan, Pour-El and J. Ian, Richards, Noncomputability in analysis and physics: a complete determination of the class of noncomputable linear operators, Advances in Mathematics, vol. 48 (1983), pp. 44-74.Google Scholar
[177] Marian Boykan, Pour-El and J. Ian, Richards, Computability in analysis and physics, Springer, Berlin, 1989.
[178] Robert, Rettinger and Klaus, Weihrauch, The computational complexity ofsome Julia sets, Proceedings of the 35th Annual ACM Symposium on Theory of Computing (Michel X., Goemans, editor), Association for Computing Machinery, New York, 2003, pp. 177-185.
[179] Robert, Rettinger and Xizhong, Zheng, On the hierarchy and extension of monotonically computable real numbers, Journal of Complexity, vol. 19 (2003), pp. 672-691.Google Scholar
[180] Robert, Rettinger and Xizhong, Zheng, A hierarchy of Turing degrees of divergence bounded computable real numbers, Journal of Complexity, vol. 22 (2006), pp. 818-826.Google Scholar
[181] H. Gordon, Rice, Recursive real numbers, Proceedings of the American Mathematical Society, vol. 5 (1954), pp. 784-791.Google Scholar
[182] R. M., Robinson, Review of “Peter, R., Rekursive Funktionen”, The Journal of Symbolic Logic, vol. 16 (1951), pp. 280-282.Google Scholar
[183] Stéphane, le Roux and Martin, Ziegler, Singular coverings andnon-uniform notions of closed set computability, Mathematical Logic Quarterly, vol. 54 (2008), pp. 545-560.Google Scholar
[184] Bertrand, Russell and Alfred North, Whitehead, Principia mathematica, vol. 1, Cambridge University Press, 1910, vol. 2, 1912; vol. 3, 1913.
[185] Jason, Rute, Algorithmic randomness, martingales, and differentiability, in preparation.
[186] Claus Peter, Schnorr, Komplexität von Algorithmen mit Anwendung auf die Analysis, Archiv für Mathematische Logik und Grundlagenforschung, vol. 14 (1971), pp. 54-68.Google Scholar
[187] Claus Peter, Schnorr, Zufälligkeit und Wahrscheinlichkeit, Lecture Notes in Mathematics, vol. 218, Springer, Berlin, 1971.
[188] Arnold, Schönhage, Numerik analytischer Funktionen und Komplexität, Jahresbericht der Deutschen Mathematiker-Vereinigung, vol. 92 (1990), pp. 1-20.Google Scholar
[189] Matthias, Schröder, Topological spaces allowing type 2 complexity theory, Computability and complexity in analysis (Ker-I, Ko and Klaus, Weihrauch, editors), Fern Universität, Hagen, September 1995, pp. 41-53.
[190] Matthias, Schröder, Fast online multiplication of real numbers, STACS 97 (Rüdiger, Reischuk and Michel, Morvan, editors), Springer, Berlin, 1997, pp. 81-92.
[191] Matthias, Schröder, Online computations of differentiable functions, Theoretical Computer Science, vol. 219 (1999), pp. 331-345.Google Scholar
[192] Matthias, Schröder, Extended admissibility, Theoretical Computer Science, vol. 284 (2002), pp. 519-538.Google Scholar
[193] Matthias, Schröder, Spaces allowing type-2 complexity theory revisited, Mathematical Logic Quarterly, vol. 50 (2004), pp. 443-459.Google Scholar
[194] Matthias, Schröder, Admissible representations for probability measures, Mathematical Logic Quarterly, vol. 53 (2007), pp. 431-445.Google Scholar
[195] Dana, Scott, Outline of a mathematical theory of computation, Technical monograph prg-2, Oxford University, Oxford, November 1970.
[196] Ksenija, Simic, The pointwise ergodic theorem in subsystems of second-order arithmetic, The Journal of Symbolic Logic, vol. 72 (2007), pp. 45-66.Google Scholar
[197] Stephen G., Simpson, Subsystems of second order arithmetic, second ed., Cambridge University Press, Cambridge, 2009.
[198] Thoralf, Skolem, Begründung der elementaren Arithmetik durch die rekurrierende Denkweise ohne Anwendung scheinbarer Veränderlichen mit unendlichem Ausdehnungsbereich, Skrifter, Norske Videnskaps-Akademi i Oslo, Matematisk-Naturvidenskapelig Klasse, vol. 6, J. Dybwad, Oslo, 1923, pp. 1-38, translated in [217], pp. 302–333.
[199] Morten H., Słrensen and Pawel, Urzyczyn, Lectures on the Curry–Howard isomorphism, Elsevier, Amsterdam, 2006.
[200] Ernst, Specker, Nicht konstruktiv beweisbare Sätze der Analysis, The Journal of Symbolic Logic, vol. 14 (1949), pp. 145-158.Google Scholar
[201] Ernst, Specker, Der Satz vom Maximum in der rekursiven Analysis, Constructivity in mathematics (A., Heyting, editor), North-Holland, Amsterdam, 1959, pp. 254-265.
[202] Howard, Stein, Logos, Logic, and Logistiké, History and philosophy of moden mathematics (William, Aspray and Philip, Kitcher, editors), University of Minnesota, Minneapolis, 1988, pp. 238-259.
[203] William W., Tait, Intensional interpretations of functionals of finite type, I, The Journal of Symbolic Logic, vol. 32 (1967), pp. 198-212.Google Scholar
[204] A. S., Troelstra, Metamathematical investigation of intuitionistic arithmetic and analysis, Springer, Berlin, 1973.
[205] A. S., Troelstra, Realizability, Handbook of proof theory (Samuel R., Buss, editor), North-Holland, Amsterdam, 1998, pp. 407-473.
[206] A. S., Troelstra and Dirk Van, Dalen, Constructivism in mathematics: An introduction, North-Holland, Amsterdam, 1988.
[207] Alan M., Turing, On computable numbers, with an application to the “Entscheidungsproblem”, Proceedings of the London Mathematical Society, vol. 42 (1936), pp. 230-265.Google Scholar
[208] Alan M., Turing, On computable numbers, with an application to the “Entscheidungsproblem”. A correction, Proceedings of the London Mathematical Society, vol. 43 (1937), pp. 544-546.Google Scholar
[209] Alan M., Turing, Finite approximations to Lie groups, Annals of Mathematics, vol. 39 (1938), pp. 105-111.Google Scholar
[210] Alan M., Turing, Systems of logic based on ordinals, Proceedings of the London Mathematical Society. Series 2, vol. 45 (1939), pp. 161-228.Google Scholar
[211] Alan M., Turing, A method for the calculation of the zeta-function, Proceedings of the London Mathematical Society. Series 2, vol. 48 (1943), pp. 180-197.Google Scholar
[212] Alan M., Turing, Rounding-off errors in matrix processes, Quarterly Journal of Mechanics and Applied Mathematics, vol. 1 (1948), pp. 287-308.Google Scholar
[213] Alan M., Turing, Some calculations of the Riemann zeta-function, Proceedings of the London Mathematical Society. Series 3, vol. 3 (1953), pp. 99-117.Google Scholar
[214] V. A., Uspensky and A. L., Semenov, Basic developments connected with the concept of algorithm and with its applications in mathematics, Algorithms in modern mathematics and computer science (Andrei P., Ershov and Donald E., Knuth, editors), Springer, Berlin, 1981.
[215] Mark, van Atten, On Brouwer, Wadsworth/Thomson Learning, Belmont, CA, 2004.
[216] Mark, van Atten, Luitzen Egbertus Jan Brouwer, The Stanford encyclopedia of philosophy (Edward N., Zalta, editor), summer 2011 ed., 2011.
[217] Jean, van Heijenoort, From Frege to Gödel: A sourcebook in mathematical logic, 1879–1931, Harvard University Press, Cambridge, 1967.
[218] John, von Neumann, Die formalistische Grundlegung der Mathematik, Erkenntnis, vol. 2 (1931), 116-121, translated by E., Putnam and G. J., Massey as The formalist foundations of mathematics (P. Benacerraf and H. Putnam, editors), Philosophy of Mathematics: Selected Readings, 2nd edition, Cambridge University Press, Cambridge, 1983, pp. 61-65.Google Scholar
[219] V. V., V'yugin, Ergodic convergence in probability, and an ergodic theorem for individual random sequences, Teoriya Veroyatnostei i ee Primeneniya, vol. 42 (1997), pp. 35-50.Google Scholar
[220] V. V., V'yugin, Ergodic theorems for individual random sequences, Theoretical Computer Science, vol. 207 (1998), pp. 343-361.Google Scholar
[221] Klaus, Weihrauch, Computability, Springer, Berlin, 1987.
[222] Klaus, Weihrauch, Computability on the probability measures on the Borel sets of the unit interval, Theoretical Computer Science, vol. 219 (1999), pp. 421-437.Google Scholar
[223] Klaus, Weihrauch, Computable analysis, Springer, Berlin, 2000.
[224] Klaus, Weihrauch, Computational complexity on computable metric spaces, Mathematical Logic Quarterly, vol. 49 (2003), pp. 3-21.Google Scholar
[225] Klaus, Weihrauch and Christoph, Kreitz, Representations of the real numbers and of the open subsets of the set of real numbers, Annals of Pure and Applied Logic, vol. 35 (1987), pp. 247-260.Google Scholar
[226] Klaus, Weihrauch and Ning, Zhong, Is wave propagation computable or can wave computers beat the Turing machine?, Proceedings of the London Mathematical Society, vol. 85 (2002), pp. 312-332.Google Scholar
[227] Klaus, Weihrauch, Computing the solution of the Korteweg-de Vries equation with arbitrary precision on Turing machines, Theoretical Computer Science, vol. 332 (2005), pp. 337-366.Google Scholar
[228] Klaus, Weihrauch, An algorithm for computing fundamental solutions, SIAM Journal on Computing, vol. 35 (2006), pp. 1283-1294.Google Scholar
[229] Klaus, Weihrauch, Computing Schrödinger propagators on Type-2 Turing machines, Journal of Complexity, vol. 22 (2006), pp. 918-935.Google Scholar
[230] Klaus, Weihrauch, Computable analysis of the abstract Cauchy problem in a Banach space and its applications I, Mathematical Logic Quarterly, vol. 53 (2007), pp. 511-531.Google Scholar
[231] Norbert, Wiener, Time, communication, and the nervous system, Annals of the New York Academy of Sciences, vol. 50 (1948), pp. 197-220.Google Scholar
[232] Philip P., Wiener (editor), Leibniz: Selections, Charles Scribner's Sons, New York, 1951.
[233] Yongcheng, Wu and Klaus, Weihrauch, A computable version of the Daniell-Stone theorem on integration and linear functionals, Theoretical Computer Science, vol. 359 (2006), pp. 28-42.Google Scholar
[234] Mariko, Yasugi, Takakazu, Mori, and Yoshiki, Tsujii, Effective properties of sets and functions in metric spaces with computability structure, Theoretical Computer Science, vol. 219 (1999), pp. 467-486.Google Scholar
[235] Xiaokang, Yu, Riesz representation theorem, Borel measures and subsystems of second-order arithmetic, Annals of Pure and Applied Logic, vol. 59 (1993), pp. 65-78.Google Scholar
[236] Xiaokang, Yu, Lebesgue convergence theorems and reverse mathematics, Mathematical Logic Quarterly, vol. 40 (1994), pp. 1-13.Google Scholar
[237] Xiaokang, Yu and Stephen G., Simpson, Measure theory and weak König's lemma, Archive for Mathematical Logic, vol. 30 (1990), pp. 171-180.Google Scholar
[238] I. D., Zaslavski, Disproof of some theorems of classical analysis in constructive analysis, Uspekhi Matematicheskikh Nauk, vol. 10 (1955), pp. 209-210, (in Russian).Google Scholar
[239] Xizhong, Zheng and Klaus, Weihrauch, The arithmetical hierarchy of real numbers, Mathematical Logic Quarterly, vol. 47 (2001), pp. 51-65.Google Scholar
[240] Ning, Zhong and Klaus, Weihrauch, Computability theory of generalized functions, Journal of the Association for Computing Machinery, vol. 50 (2003), pp. 469-505.Google Scholar
[241] Qing, Zhou, Computable real-valued functions on recursive open and closed subsets of Euclidean space, Mathematical Logic Quarterly, vol. 42 (1996), pp. 379-409.Google Scholar
[242] Martin, Ziegler, Real hypercomputation and continuity, Theory of Computing Systems, vol. 41 (2007), pp. 177-206.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×