Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-21T23:14:17.790Z Has data issue: false hasContentIssue false
  • English
  • Français

Computability and Recursion

Published online by Cambridge University Press:  15 January 2014

Robert I. Soare
Robert I. Soare*
Affiliation:
Department of Mathematics, University of Chicago, Chicago, Illinois 60637-1546, USA E-mail: [email protected], http://www.cs.uchicago.edu/~soare, Papers posted at, ftp:cs.uchicago.edu/ftp/pub/users/soare
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the informal concept of “computability” or “effective calculability” and two of the formalisms commonly used to define it, “(Turing) computability” and “(general) recursiveness”. We consider their origin, exact technical definition, concepts, history, general English meanings, how they became fixed in their present roles, how they were first and are now used, their impact on nonspecialists, how their use will affect the future content of the subject of computability theory, and its connection to other related areas.

After a careful historical and conceptual analysis of computability and recursion we make several recommendations in section §7 about preserving the intensional differences between the concepts of “computability” and “recursion.” Specifically we recommend that: the term “recursive” should no longer carry the additional meaning of “computable” or “decidable;” functions defined using Turing machines, register machines, or their variants should be called “computable” rather than “recursive;” we should distinguish the intensional difference between Church's Thesis and Turing's Thesis, and use the latter particularly in dealing with mechanistic questions; the name of the subject should be “Computability Theory” or simply Computability rather than “Recursive Function Theory.”

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 2 , Issue 3 , September 1996 , pp. 284 - 321
Copyright
Copyright © Association for Symbolic Logic 1996

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

[Boolos and Jeffrey, 1974] Boolos, G. and Jeffrey, R., Computability and logic, Cambridge University Press, Cambridge, England.Google Scholar
[Church, 1935] Church, A., An unsolvable problem of elementary number theory, Bulletin of the American Mathematical Society, vol. 41, pp. 332–333, Preliminary report (abstract).Google Scholar
[Church, 1936] Church, A., An unsolvable problem of elementary number theory, American Journal of Mathematics, vol. 58, pp. 345–363.Google Scholar
[Church, 1936 b] Church, A., A note on the Entscheidungsproblem, Journal of Symbolic Logic, vol. 1, pp. 40–41, correction 101–102.CrossRefGoogle Scholar
[Church, 1937] Church, A., Review of Turing 1936, Journal of Symbolic Logic, vol. 2, no. 1, pp. 42–43.Google Scholar
[Church, 1937 b] Church, A., Review of Post 1936, Journal of Symbolic Logic, vol. 2, no. 1, p. 43.Google Scholar
[Church, 1938] Church, A., The constructive second number class, Bulletin of the American Mathematical Society, vol. 44, pp. 224–232.Google Scholar
[Church and Kleene, 1936] Church, A. and Kleene, S. C., Formal definitions in the theory ofordinal numbers, Fundamenta Mathematicae, vol. 28, pp. 11–21.Google Scholar
[Cutland, 1980] Cutiand, Nigel, Computability: An introduction to recursive function theory, Cambridge University Press, Cambridge, England.Google Scholar
[Davis, 1958] Davis, M., Computability and unsolvability, Mc-Graw-Hill, New York, reprinted in 1982 by Dover Publications.Google Scholar
[Davis, 1965] Davis, M. (editor), The undecidable. Basicpaperson undecidablepropositions, unsolvable problems, andcomputable functions, Raven Press, Hewlett, New York.Google Scholar
[Davis, 1982] Davis, M., Why Gödel did not have Church's thesis, Information and Control, vol. 54, pp. 3–24. Google Scholar
[Davis, 1988] Davis, M., Mathematical logic and the origin of modern computers, in Herken, 1988, pp. 149–174.Google Scholar
[Dedekind, 1872] Dedekind, R., Stetigkeit und irrational Zahlen, Braunschweig, 5th ed., 1927; also in Dedekind Gesammelte mathematische Werke (Viewegand Sohn, editors), vol. III, Braunschweig, 1932, pp. 315–334; English translation by Wooster Woodruff Beman entitled Continuity and irrational numbers, Essays on the theory ofnumbers , Open Court, Chicago, 1901, pp. 1–24.Google Scholar
[Dedekind, 1888] Dedekind, R., Was sind und was sollen die Zahlen?, Braunschweig, 6th ed., 1930; also in Dedekind Gesammelte Mathematische Werke , vol. III, pp. 335-391; English translation by Beman, The nature and meaning of numbers. loc. cit. , pp. 31–105; English translation in Dedekind, Essays on the theory ofnumbers , Open Court, Chicago, 1901, pp. 29–115.Google Scholar
[Epstein and Carnielli, 1989] Epstein, R. L. and Carnielli, W. A., Computability: computable functions, logic, and the foundations of mathematics, Brooks/Cole Advanced Books and Software, Pacific Grove, Calif. Google Scholar
[Feferman, 1988] Feferman, S., Turing in the land of O(z), in Herken, 1988, pp. 113–147.Google Scholar
[Feferman, 1992] Feferman, S., Turing's “oracle”: From absolute to relative computability—and back, The space of mathematics (Echeverria, J. et al., editors), Walter de Gruyter, Berlin, pp. 314–348.Google Scholar
[Fitting, 1987] Fitting, M., Computability theory, semantics, and logicprogramming, Oxford University Press.Google Scholar
[Gandy, 1980] Gandy, R., Church's thesis and principles for mechanisms, The Kleene symposium, North-Holland, pp. 123–148.Google Scholar
[Gandy, 1988] Gandy, R., The confluence of ideas in 1936, in Herken, 1988, pp. 55–111.Google Scholar
[Gödel, 193?] Gödel, K., Undecidable diophantine propositions, in Gödel 1995, pp. 156–175.Google Scholar
[Gödel, 1931] Gödel, K., Über formal unent scheidbare sätze der Principia Mathematica und verwandter systeme. I, Monatsch. Math. Phys., vol. 38, pp. 173–178, English translation in Davis 1965, pp. 4–38, and in van Heijenoort, 1967, pp. 592–616.Google Scholar
[Gödel, 1934] Gödel, K., On undecidable propositions of formal mathematical systems, notes by S. C. Kleene and J. B. Rosser on lectures at the Institute for Advanced Study, Princeton, New Jersey, 1934, reprinted in Davis 1965, pp. 39–74].Google Scholar
[Gödel, 1936] Gödel, K., On the length of proofs, Gödel 1986, pp. 397–399; reprinted in Davis 1965, pp. 82–83, with a Remark added in proof [of the original German publication].Google Scholar
[Gödel, 1946] Gödel, K., Remarks before the Princeton bicentennial conference of problems in mathematics, reprinted in Davis 1965, pp. 84–88.Google Scholar
[Gödel, 1951] Gödel, K., Some basic theorems on the foundations of mathematics and their implications, in Gödel 1995, pp. 304–323. (This was the Gibbs Lecture delivered by Godel on December 26, 1951 to the American Mathematical Society).Google Scholar
[Gödel, 1958] Gödel, K., Über eine bisher noch nicht benütze Erweiterung des finiten Standpunktes, Dialectica, vol. 12, pp. 280–287, German and English translation in Godel 1986, pp. 240–251, with introductory note by A. S. Troelstra, pp. 217–241.Google Scholar
[Gödel, 1964] Gödel, K., Postscriptum to Gödel 1931, written in 1946, printed in Davis 1965, pp. 71–73.Google Scholar
[Gödel, 1972] Gödel, K., Some remarks on the undecidability results, in Gödel 1990, pp. 305–306, written in 1972.Google Scholar
[Gödel, 1986] Gödel, K., Collected works volume I: Publications 1929–36 (Feferman, S. et al., editors), Oxford University Press, Oxford.Google Scholar
[Gödel, 1990] Gödel, K., Collected works volume II: Publications 1938–1974 (Feferman, S. et al., editors), Oxford University Press, Oxford.Google Scholar
[Gödel, 1995] Gödel, K., Collected works volume III: Unpublished essays and lectures (Feferman, S. et al., editors), Oxford University Press, Oxford.Google Scholar
[Harrington and Soare, 1996] Harrington, L. and Soare, R. I., Definability, automorphisms, and dynamic properties of computably enumerable sets, this Bulletin, vol. 2, 1996, pp. 199–213.Google Scholar
[Herken, 1988] Herken, R. (editor), The universal Turing machine: A half-century survey, Oxford University Press.Google Scholar
[Hilbert, 1899] Hilbert, D., Grundlagen der Geometrie, 7th ed., Tuebner-Verlag, Leipzig, Berlin, 1930.Google Scholar
[Hilbert, 1904] Hilbert, D., Über die Grundlagen der Logik und der Arithmetik, in Verhandlungen des Dritten Internationalen Mathematiker-Kongresses in Heidelberg vom 8. bis 13. August 1904, Teubner, Leipzig, 1905, pp. 174–185. Reprinted in van Heijenoort 1967, pp. 129–138.Google Scholar
[Hilbert, 1918] Hilbert, D., Axiomatisches Denken, Mathematische Annalen, vol. 78, pp. 405–415.Google Scholar
[Hilbert, 1926] Hilbert, D., Über das Unendliche, Mathematische Annalen, vol. 95, pp. 161–190, English translation in van Heijenoort 1967, 367–392.Google Scholar
[Hilbert, 1928] Hilbert, D., Abhandlungen aus dem mathematischen Seminar derHamburgischen Universität, Die Grundlagen der Mathematik, vol. 6, pp. 65–85, reprinted in van Heijenoort 1967, pp. 464–479.Google Scholar
[Hilbert and Ackermann, 1928] Hilbert, D. and Ackermann, W., Grundzüge der theoretischen Logik, Springer-Verlag, Berlin, English translation of 1938 edition, Chelsea, New York, 1950.Google Scholar
[Hilbert and Bernays, 1934] Hilbert, D. and Bernays, P., Grundlagen der Mathematik I (1934), II (1939), second ed., Springer-Verlag, Berlin, I (1968), II (1970).Google Scholar
[Hodges, 1983] Hodges, A., Alan Turing: The enigma, Burnett Books and Hutchinson, London, and Simon and Schuster, New York.Google Scholar
[Kleene, 1936] Kleene, S. C., General recursive functions of natural numbers, Mathematische Annalen, vol. 112, pp. 727–742.Google Scholar
[Kleene, 1936 b] Kleene, S. C., λ-definability and recursiveness, Duke Mathematics Journal, vol. 2, pp. 340–353.Google Scholar
[Kleene, 1936 c] Kleene, S. C., A note on recursive functions, Bulletin of the American Mathematical Society, vol. 42, pp. 544–546.Google Scholar
[Kleene, 1938] Kleene, S. C., On notation for ordinal numbers, Journal of Symbolic Logic, vol. 3, pp. 150–155.CrossRefGoogle Scholar
[Kleene, 1943] Kleene, S. C., Recursive predicates and quantifiers, Transactions of the American Mathematical Society, vol. 53, pp. 41–73.Google Scholar
[Kleene, 1944] Kleene, S. C., On the forms of the predicates in the theory of constructive ordinals, American Journal of Mathematics, vol. 66, pp. 41–58.Google Scholar
[Kleene, 1952] Kleene, S. C., Introduction to metamathematics, Van Nostrand, New York, ninth reprint 1988, Walters-Noordhoff Publishing Co., Groningen and North-Holland, Amsterdam.Google Scholar
[Kleene, 1952 b] Kleene, S. C., Recursive functions and intuitionistic mathematics, Proceedings of the international congress of mathematicians, Cambridge, Massachusetts, U.S.A., August 30-September 6, 1950, vol. 1, American Mathematical Society (Providence, R.I.), pp. 679–685.Google Scholar
[Kleene, 1955] Kleene, S. C., Arithmetical predicates and function quantifiers, Transactions of the American Mathematical Society, vol. 79, pp. 312–340.CrossRefGoogle Scholar
[Kleene, 1955 b] Kleene, S. C., On the forms of the predicates in the theory of constructive ordinals (second paper), American Journal of Mathematics, vol. 77, pp. 405–428.CrossRefGoogle Scholar
[Kleene, 1955 c] Kleene, S. C., Hierarchies of number-theoretical predicates, Bulletin of the American Mathematical Society, vol. 61, pp. 193–213.Google Scholar
[Kleene, 1959] Kleene, S. C., Recursive functionals and quantifiers of finite type I, Transactions of the American Mathematical Society, vol. 91, pp. 1–52.Google Scholar
[Kleene, 1962] Kleene, S. C., Turing-machine computable functionals of finite types I, Logic, methodology, and philosophy of science: Proceedings of the 1960 international congress, Stanford University Press, pp. 38–45.Google Scholar
[Kleene, 1962 b] Kleene, S. C., Turing-machine computable functionals offinite types II, Proceedings of the London Mathematical Society, vol. 12, no. 3, pp. 245–258.Google Scholar
[Kleene, 1963] Kleene, S. C., Recursive functionals and quantifiers offinite type II, Transactions of the American Mathematical Society, vol. 108, pp. 106–142.Google Scholar
[Kleene, 1981] Kleene, S. C., Origins of recursive function theory, Annals of the History of Computing, vol. 3, pp. 52–67.Google Scholar
[Kleene, 1981 b] Kleene, S. C., The theory of recursive functions, approaching its centennial, Bulletin of the American Mathematical Society (n.s.), vol. 5, pp. 43–61.Google Scholar
[Kleene, 1981 c] Kleene, S. C., Algorithms in various contexts, Proc. sympos. algorithms in modern mathematics and computer science (dedicated to Al-Khowarizimi), Urgench, Khorezm Region, Uzbek, SSSR, 1979, Springer-Verlag, Berlin, Heidelberg and New York.Google Scholar
[Kleene, 1987] Kleene, S. C., Reflections on Church's Thesis, Notre Dame Journal of Formal Logic, vol. 28, pp. 490–498.Google Scholar
[Kleene, 1987 b] Kleene, S. C., Gödel's impression on students of logic in the 1930's, Gödel remembered (Weingartner, P. and Schmetterer, L., editors), Bibliopolis, Naples, pp. 49–64.Google Scholar
[Kleene, 1988] Kleene, S. C., Turing's analysis of computability, and major applications of it, in Herken 1988, pp. 17–54.Google Scholar
[Kleene-Post, 1954] Kleene, S. C. and Post, E. L., The upper semi-lattice of degrees of recursive unsolvability, Annals ofMathematics, vol. 59, pp. 379–407.Google Scholar
[Kline, 1972] Kline, M., Mathematical thought from ancient to modern times, Oxford University Press, Oxford.Google Scholar
[Lerman, 1983] Lerman, M., Degrees of unsolvability: Local and global theory, Springer-Verlag, Heidelberg, New York, Tokyo.Google Scholar
[Normann, 1980] Normann, D., Recursion on countable functionals, Lecture notes in mathematics, no. 811, Springer-Verlag, Heidelberg, New York.Google Scholar
[Odifreddi, 1989] Odœreddi, P., Classical recursion theory, North-Holland, Amsterdam.Google Scholar
[O.E.D., 1989] Simpson, J. A. and Weiner, E. S. C. (editors), Oxford english dictionary, second ed., Clarendon Press, Oxford.Google Scholar
[Peano, 1889] Peano, G., Arithmetices principia, nova methodo exposita, Turin Bocca, English translation in van Heijenoort, 1967, pp. 83–97.Google Scholar
[Peano, 1891] Peano, G., Sul concetto di numéro, Rivista di Matematica, vol. 1, pp. 87–102, 256–267.Google Scholar
[Peirce, 1960] Peirce, Charles S., Book II. Speculative grammar, Volume II: Elements of logic (Hartshorne, C. and Weiss, P., editors), Collected Papers of Charles Sanders Peirce , The Belknap Press of Harvard University Press, Cambridge, Massachusetts and London, England.Google Scholar
[Penrose, 1994] Penrose, R., Shadows of the mind, Oxford University Press, Oxford.Google Scholar
[Peter, 1934] Péter, R., Über den Zussammenhang der verschiedenen Begriffe der rekursiven Funktion, Mathematische Annalen, vol. 110, pp. 612–632.Google Scholar
[Peter, 1951] Péter, R., Rekursive funktionen, Akadémaiai Kiadó (Akademische Verlag), Budapest, Recursive functions , third revised ed., Academic Press, New York, 1967.Google Scholar
[Platek, 1966] Platek, R., Foundations of recursion theory, Ph.D. thesis , Stanford University, Stanford, CA.Google Scholar
[Post, 1936] Post, E. L., Finite combinatory processes-formulation I, Journal of Symbolic Logic, vol. 1, pp. 103–105, reprinted in Davis 1965, pp. 288–291.CrossRefGoogle Scholar
[Post, 1941] Post, E. L., Absolutely unsolvable problems and relatively undecidable propositions: Account of an anticipation, submitted for publication in 1941; printed in Davis 1965, pp. 340–433.Google Scholar
[Post, 1943] Post, E. L., Formal reductions of the general combinatorial decision problem, American Journal of Mathematics, vol. 65, pp. 197–215.Google Scholar
[Post, 1944] Post, E. L., Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society, vol. 50, pp. 284–316, reprinted in Davis 1965, pp. 304–337.Google Scholar
[Post, 1947] Post, E. L., Recursive unsolvability of a problem of Thue, Journal of Symbolic Logic, vol. 12, pp. 1–11, reprinted in Davis 1965, pp. 292–303.Google Scholar
[Post, 1948] Post, E. L., Degrees of recursive unsolvability: preliminary report (abstract), Bulletin of the American Mathematical Society, vol. 54, pp. 641–642.Google Scholar
[Putnam, 1995] Putnam, H., Review of Penrose 1994, Bulletin of the American Mathematical Society, vol. 32, pp. 370–373.Google Scholar
[Sacks, 1990] Sacks, G. E., Higher recursion theory, Springer-Verlag, Heidelberg, New York.Google Scholar
[Shoenfield, 1967] Shoenfield, J. R., Mathematical logic, Addison-Wesley, Reading, Massachusetts.Google Scholar
[Shoenfield, 1991] Shoenfield, J. R., Recursion theory, Lecture notes in logic, Springer-Verlag, Heidelberg, New York.Google Scholar
[Shoenfield, 1995] Shoenfield, J. R., The mathematical work of S. C. Kleene, this Bulletin, vol. 1, pp. 8–43.Google Scholar
[Sieg, 1994] Sieg, W., Mechanical procedures and mathematical experience, Mathematics and mind (George, A., editor), Oxford University Press.Google Scholar
[Sieg and Byrnes, 1995] Sieg, W. and Byrnes, J., K-graph machines: generalizing Turing's machines and arguments, preprint.Google Scholar
[Skolem, 1923] Skolem, T., Begründung der elementaren Arithmetik durch die rekurrierende Denkweise ohne Anwendung scheinbare Veränderlichen mit unendlichen Ausdehnungsbereich, Skrifter utgit av Videnskapsselskapet i Kristiania, I. Mathematisk-Naturvidenskabelig Klasse, vol. 6, English translation in van Heijenoort, 1967, pp. 302–333.Google Scholar
[Soare, ta 1] Soare, R. I., An overview of the computably enumerable sets, Handbook of computability theory, North-Holland, Amsterdam, in preparation.Google Scholar
[Soare, ta 2] Soare, R. I., Computability and enumerability, Proceedings of the 10th international congress of logic, methodology, and philosophy of science, August 19–25, 1995, Florence, Italy, to appear.Google Scholar
[Soare, 1981] Soare, R. I., Constructions in the recursively enumerable degrees, Recursion theory and computational complexity (Lolli, G., editor), Proceedings of Centro Internazionale Matematico Estivo (C.I.M.E.), 06 14–23, 1979, in Bressanone, Italy, Liguori Editore, Naples, Italy.Google Scholar
[Soare, 1987] Soare, R. I., Recursively enumerable sets and degrees: A study of computable functions and computably generated sets, Springer-Verlag, Heidelberg.Google Scholar
[Tamburrini, 1995] Tamburrini, G., Mechanistic theories in cognitive science: The import of Turing's Thesis, Proceedings of the 10th international congress of logic, methodology, and philosophy ofscience, August 19–25, 1995, Florence, Italy, to appear.Google Scholar
[Turing, 1936] Turing, A. M., On computable numbers, with an application to the Entscheidungsproblem, parts 3 and 4, Proceedings of the London Mathematical Society, vol. 42, pp. 230–265; [Turing, 1937] A correction, Proceedings of the London Mathematical Society , vol. 43, pp. 544–546.Google Scholar
[Turing, 1937 b] Turing, A. M., Computability and λ-definability, Journal of Symbolic Logic, vol. 2, pp. 153–163.Google Scholar
[Turing, 1939] Turing, A. M., Systems of logic basedon ordinals, part 3, Proceedings of the London Mathematical Society, vol. 45, pp. 161–228, reprinted in Davis 1965, pp. 154–222.CrossRefGoogle Scholar
[Turing, 1948] Turing, A. M., Intelligent machinery, Machine Intelligence, vol. 5, pp. 3–23, written in September, 1947 and submitted to the National Physical Laboratory in 1948.Google Scholar
[Turing, 1949] Turing, A. M., Text of a lecture by Turing on June 24, 1949, in Morris, F. L. and Jones, C. B., An early program proof by Alan Turing, Annals of the History of Computing, vol. 6 (1984), pp. 139–143.Google Scholar
[Turing, 1950] Turing, A. M., Computing machinery and intelligence, Mind, vol. 59, pp. 433–460.Google Scholar
[Turing, 1950 b] Turing, A. M., The word problem in semi-groups with cancellation, Annals of Mathematics, vol. 52, pp. 491–505.Google Scholar
[Turing, 1954] Turing, A. M., Solvable and unsolvable problems, Science News, vol. 31, pp. 7–23.Google Scholar
[Turing, 1986] Turing, A. M., Lecture to the London Mathematical Society on 20 February 1947, A. M. Turing's ACE report of 1946 and other papers (Carpenter, B. E. and Doran, R.W., editors), Cambridge University Press, pp. 106–124.Google Scholar
[van Heijenoort, 1967] Heijenoort, J. van (editor), From Frege to Godel, a sourcebook in mathematical logic, 1879–1931, Harvard University Press, Cambridge, Massachusetts.Google Scholar
[Webster, 1993] Gove, Ph. B. (editor), Webster's third new international dictionary of the English language (unabridged), Merriam-Webster Inc., Publishers, Springfield, Massachusetts, U.S.A. Google Scholar
[Zabell, 1995] Zabell, S. L., Alan Turing and the central limit theorem, American Mathematical Monthly, vol. 102, no. 6, pp. 483–494.Google Scholar