Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-22T14:56:49.443Z Has data issue: false hasContentIssue false
  • English
  • Français

Alan Turing and the Foundations of Computable Analysis

Published online by Cambridge University Press:  15 January 2014

Guido Gherardi
Guido Gherardi*
Affiliation:
Dipartimento Di Filosofia, Universitá Du Bologna, Via Zamboni 38, 40126 Bologna, ItalyE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We investigate Turing's contributions to computability theory for real numbers and real functions presented in [22, 24, 26]. In particular, it is shown how two fundamental approaches to computable analysis, the so-called ‘Type-2 Theory of Effectivity’ (TTE) and the ‘realRAM machine’ model, have their foundations in Turing's work, in spite of the two incompatible notions of computability they involve. It is also shown, by contrast, how the modern conceptual tools provided by these two paradigms allow a systematic interpretation of Turing's pioneering work in the subject.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 17 , Issue 3 , September 2011 , pp. 394 - 430
Copyright
Copyright © Association for Symbolic Logic 2011

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

REFERENCES

[1] Blum, Leonore, Computing over the reals: where Turing meets Newton, Notices of the American Mathematical Society, vol. 51 (2004), no. 9, pp. 1024–1034.Google Scholar
[2] Blum, Leonore, Cucker, Felipe, Schub, Michael, and Smale, Stephen, Complexity and real computation, Springer, New York, 1998.Google Scholar
[3] Brouwer, Luitzen E. J., Begründung der Mengenlehre unabhängig vom logischen Satz vom ausgeschlossenen Dritten. Erster Teil: allgemeine Mengenlehre, Verhandelingen der Koninklijke Nederlandse Akademie van Wetenschappen, vol. 1 sectie 12 (1918), no. 5, pp. 3–43.Google Scholar
[4] Brouwer, Luitzen E. J., Begründung der Mengenlehre unabhängig vom logischen Satz vom ausgeschlossenen Dritten. Zweiter Teil: Theorie der Punktmengen, Verhandelingen der Koninklijke Nederlandse Akademie van Wetenschappen, vol. 1 sectie 12 (1919), no. 7, pp. 3–33.Google Scholar
[5] Brouwer, Luitzen E. J., Über die Bedeutung des Satzes vom ausgeschlossenen Dritten in der Mathematik, insbesondere in der Funktiontheorie, Journal fur die reine und angewandte Mathematik, vol. 154 (1924), pp. 1–7.Google Scholar
[6] Chaitin, Gregory, Meta math! The quest for Omega, Vintage Books, 2006.Google Scholar
[7] Cucker, Felipe, Real computations with fake numbers, Journal of Complexity, vol. 18 (2002), pp. 104–134.Google Scholar
[8] Davis, Martin, Computability and unsolvability, McGraw-Hill, 1958.Google Scholar
[9] Grzegorczick, Andrzej, Computable functionals, Fundamenta Mathematicae, vol. 42 (1955), pp. 168–202.CrossRefGoogle Scholar
[10] Grzegorczick, Andrzej, On the definitions of computable real continuous functions, Fundamenta Mathematicae, vol. 44 (1957), pp. 61–71.Google Scholar
[11] Kleene, Stephen C., Introduction to metamathematics, North-Holland Publishing Company, Amsterdam, 1952.Google Scholar
[12] Kleene, Stephen C. and Vesley, Richard E., Intuitionistic mathematics especially in relation to recursive functions, North-Holland Publishing Company, Amsterdam, 1965.Google Scholar
[13] Kreitz, Christoph and Weihrauch, K., Theory of representations, Theoretical Computer Science, vol. 38 (1985), pp. 35–53.Google Scholar
[14] Lacombe, Daniel, Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables réelles III, Comptes Rendus Académie des Sciences Paris, vol. 241 (1955), pp. 151–153.Google Scholar
[15] Mazur, Stanislav, Computational analysis, Razprawy Matematyczne, Warsaw, 1963.Google Scholar
[16] Miller, Joseph S., Degrees of unsolvability of continuous functions, The Journal of Symbolic Logic, vol. 69 (2004), no. 2, pp. 555–584.Google Scholar
[17] Odifreddi, Piergiorgio, Classical recursion theory, North-Holland Publishing Company, Amsterdam, 1989.Google Scholar
[18] Petzold, Charles, The annotated Turing, Wiley Publishing, Indianapolis, 2008.Google Scholar
[19] Post, Emil L., Recursive unsolvability of a problem of Thue, The Journal of Symbolic Logic, vol. 12 (1947), pp. 503–513.Google Scholar
[20] Rogers, Hartley, Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[21] Soare, Robert I., Recursively enumerable sets and degrees, Springer, Berlin, 1987.Google Scholar
[22] Turing, Alan M., On computable numbers, with an application to the ‘Entscheidungsproblem’, Proceedings of the London Mathematical Society, vol. 42 (1936), no. 2, pp. 230–265.Google Scholar
[23] Turing, Alan M., Computability and λ-definability, The Journal of Symbolic Logic, vol. 2 (1937), no. 4, pp. 153–163.Google Scholar
[24] Turing, Alan M., On computable numbers, with an application to the ‘Entscheidungsproblem’. A correction, Proceedings of the London Mathematical Society, vol. 43 (1937), no. 2, pp. 544–546.Google Scholar
[25] Turing, Alan M., A method for the calculation of the Zeta-function, Proceedings of the London Mathematical Society, vol. 48 (1943), no. 2, pp. 180–197.Google Scholar
[26] Turing, Alan M., Rounding-off errors in matrix processes, The Quarterly Journal of Mechanics and Applied Mathematics, vol. 1 (1948), no. 1, pp. 287–308.Google Scholar
[27] Turing, Alan M., Some calculations of the Riemann Zeta-function, Proceedings of the London Mathematical Society, vol. 3 (1953), no. 3, pp. 99–117.Google Scholar
[28] Weihrauch, Klaus, Computable analysis, Springer, Berlin, 2000.Google Scholar
[29] Ziegler, Martin, Revising type–2 computation and degrees of discontinuity, Electronic Notes in Theoretical Computer Science, vol. 167 (2007), pp. 255–274.Google Scholar