The theory of recursive functions, approaching its centennial
HTML articles powered by AMS MathViewer
- by Stephen C. Kleene PDF
- Bull. Amer. Math. Soc. 5 (1981), 43-61
References
- Wilhelm Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen, Math. Ann. 99 (1928), no. 1, 118–133 (German). MR 1512441, DOI 10.1007/BF01459088 Cantor, Georg, [1874] Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen, J. Reine Angew. Math. 77, 258-262.
- Georg Cantor, Beiträge zur Begründung der transfiniten Mengenlehre, Math. Ann. 49 (1897), no. 2, 207–246 (German). MR 1510964, DOI 10.1007/BF01444205
- Alonzo Church, A set of postulates for the foundation of logic, Ann. of Math. (2) 33 (1932), no. 2, 346–366. MR 1503059, DOI 10.2307/1968337
- Alonzo Church, A set of postulates for the foundation of logic, Ann. of Math. (2) 34 (1933), no. 4, 839–864. MR 1503136, DOI 10.2307/1968702
- Alonzo Church, An Unsolvable Problem of Elementary Number Theory, Amer. J. Math. 58 (1936), no. 2, 345–363. MR 1507159, DOI 10.2307/2371045
- Alonzo Church, Comparison of Russell’s resolution of the semantical antinomies with that of Tarski, J. Symbolic Logic 41 (1976), no. 4, 747–760. MR 441682, DOI 10.2307/2272393 Dedekind, Richard, [1888] Was sind und was sollen die Zahlen? Braunschweig.
- Kurt Gödel, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, Monatsh. Math. Phys. 38 (1931), no. 1, 173–198 (German). MR 1549910, DOI 10.1007/BF01700692
- Martin Davis (ed.), The undecidable, Dover Publications, Inc., Mineola, NY, 2004. Basic papers on undecidable propositions, unsolvable problems and computable functions; Corrected reprint of the 1965 original [Raven Press, Hewlett, NY; MR0189996]. MR 2070909
- David Hilbert, Axiomatisches Denken, Math. Ann. 78 (1917), no. 1, 405–415 (German). MR 1511909, DOI 10.1007/BF01457115
- David Hilbert, Über das Unendliche, Math. Ann. 95 (1926), no. 1, 161–190 (German). MR 1512272, DOI 10.1007/BF01206605 Kleene, Stephen, C., [1935] A theory of positive integers in formal logic, Amer. J. Math. 57, 153-173; 219-244.
- S. C. Kleene, General recursive functions of natural numbers, Math. Ann. 112 (1936), no. 1, 727–742. MR 1513071, DOI 10.1007/BF01565439
- S. C. Kleene, $\lambda$-definability and recursiveness, Duke Math. J. 2 (1936), no. 2, 340–353. MR 1545927, DOI 10.1215/S0012-7094-36-00227-2 Kleene, Stephen, C., [ 1938] On notation for ordinal numbers, J. Symbolic Logic 3, 150-155.
- S. C. Kleene, Recursive predicates and quantifiers, Trans. Amer. Math. Soc. 53 (1943), 41–73. MR 7371, DOI 10.1090/S0002-9947-1943-0007371-8
- S. C. Kleene, Recursive functions and intuitionistic mathematics, Proceedings of the International Congress of Mathematicians, Cambridge, Mass., 1950, vol. 1, Amer. Math. Soc., Providence, R.I., 1952, pp. 679–685. MR 0044468
- Stephen Cole Kleene, Introduction to metamathematics, D. Van Nostrand Co., Inc., New York, N. Y., 1952. MR 0051790
- S. C. Kleene, Arithmetical predicates and function quantifiers, Trans. Amer. Math. Soc. 79 (1955), 312–340. MR 70594, DOI 10.1090/S0002-9947-1955-0070594-4
- S. C. Kleene, On the forms of the predicates in the theory of constructive ordinals. II, Amer. J. Math. 77 (1955), 405–428. MR 70595, DOI 10.2307/2372632
- S. C. Kleene, Hierarchies of number-theoretic predicates, Bull. Amer. Math. Soc. 61 (1955), 193–213. MR 70593, DOI 10.1090/S0002-9904-1955-09896-3 Kleene, Stephen, C., [1957] Mathematics, foundations of, Encyclopaedia Britannica, 1957 and subsequent printings. Beginning with 1974, the article was reworked to replace Kleene’s section on intuitionism by a fuller treatment by Solomon Fefermann.
- S. C. Kleene, Mathematical logic: constructive and non-constructive operations, Proc. Internat. Congress Math. 1958., Cambridge Univ. Press, New York, 1960, pp. 137–153. MR 0114750
- S. C. Kleene, Recursive functionals and quantifiers of finite types. I, Trans. Amer. Math. Soc. 91 (1959), 1–52. MR 102480, DOI 10.1090/S0002-9947-1959-0102480-9
- S. C. Kleene, Recursive functionals and quantifiers of finite types. II, Trans. Amer. Math. Soc. 108 (1963), 106–142. MR 153557, DOI 10.1090/S0002-9947-1963-0153557-4 Kleene, Stephen, C., [1964] Computability, The Voice of America Forum Lectures, Phil. of Science Series, no. 6; reprinted, Philosophy of Science Today (Sidney Morgenbesser, ed.), Basic Books, New York and London, 1967, pp. 36-45.
- Stephen Cole Kleene, Mathematical logic, John Wiley & Sons, Inc., New York-London-Sydney, 1967. MR 0216930 Kleene, Stephen, C., [1969] The new logic, Sigma-Xi-RESA National Lecture, Southeast Tour (Spring 1969), Amer. Sci. 57, 333-347.
- S. C. Kleene, Recursive functionals and quantifiers of finite types revisited. I, Generalized recursion theory, II (Proc. Second Sympos., Univ. Oslo, Oslo, 1977) Studies in Logic and the Foundations of Mathematics, vol. 94, North-Holland, Amsterdam-New York, 1978, pp. 185–222. MR 516936
- S. C. Kleene, Recursive functionals and quantifiers of finite types revisited. II, The Kleene Symposium (Proc. Sympos., Univ. Wisconsin, Madison, Wis., 1978), Studies in Logic and the Foundations of Mathematics, vol. 101, North-Holland, Amsterdam-New York, 1980, pp. 1–29. MR 591873
- Stephen C. Kleene, Origins of recursive function theory, 20th Annual Symposium on Foundations of Computer Science (San Juan, Puerto Rico, 1979) IEEE, New York, 1979, pp. 371–382. MR 598119
- Stephen C. Kleene, Algorithms in various contexts, Algorithms in modern mathematics and computer science (Urgench, 1979), Lecture Notes in Comput. Sci., vol. 122, Springer, Berlin-New York, 1981, pp. 355–360. MR 657625 Klein, Felix, [1908-9] Elementarmathematik vom höheren Standpunkte aus, Lithographed, Leipzig; English transl. from 3rd German ed. (E. R. Hedrick and C. A. Noble, eds.), Macmillan, New York, 1932. Kronecker, Leopold, [1886] The saying quoted in the third paragraph of the text was spoken in his lecture on 21 September 1886 before der Deutschen Naturforscherversammlung zu Berlin, according to H. Weber, Leopold Kronecker, Math. Ann. 43 (1893), 1-25 (cf. p. 15). Also cf. Leopold Kronecker’s Werke, hrg. K. Henzel, vol. 3, pt. 2, p. 203.
- Leopold Löwenheim, Über Möglichkeiten im Relativkalkül, Math. Ann. 76 (1915), no. 4, 447–470 (German). MR 1511835, DOI 10.1007/BF01458217
- A. A. Markov, The theory of algorithms, Amer. Math. Soc. Transl. (2) 15 (1960), 1–14. MR 0114753, DOI 10.1090/trans2/015/01
- A. A. Markov, Theory of algorithms, Published for The National Science Foundation, Washington, D.C. and The Department of Commerce by The Israel Program for Scientific Translations, Jerusalem, 1961. Translated by Jacques J. Schorr-Kon and PST Staff. MR 0132690 Peano, Guiseppe, [1889] Arithmetices principia, nova methodo exposita, Turin, Bocca. Peano, Guiseppe, [1891] Sul concetto di numero, Rivista di Matematica 1, 87-102; 256-267.
- Rózsa Péter, Über den Zusammenhang der verschiedenen Begriffe der rekursiven Funktion, Math. Ann. 110 (1935), no. 1, 612–632 (German). MR 1512957, DOI 10.1007/BF01448046
- Rózsa Péter, Konstruktion nichtrekursiver Funktionen, Math. Ann. 111 (1935), no. 1, 42–60 (German). MR 1512975, DOI 10.1007/BF01472200
- Rózsa Péter, Über die mehrfache Rekursion, Math. Ann. 113 (1937), no. 1, 489–527 (German). MR 1513105, DOI 10.1007/BF01571648
- Emil L. Post, Recursive unsolvability of a problem of Thue, J. Symbolic Logic 12 (1947), 1–11. MR 20527, DOI 10.2307/2267170
- Emil L. Post, Formal reductions of the general combinatorial decision problem, Amer. J. Math. 65 (1943), 197–215. MR 7893, DOI 10.2307/2371809
- Emil L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284–316. MR 10514, DOI 10.1090/S0002-9904-1944-08111-1 Post, Emil L., [1948] Degrees of recursive unsolvability, abstract (preliminary report) in Bull. Amer. Math. Soc. 54, 641-642. Schröder, Ernst, [1895] Vorlesungen über die Algebra der Logik (exakte Logik), 3 Algebra und Logik der Relative, part 1, Leipzig. Skolem, Thoralf, [1923] Begründung der elementaren Arithmetik durch die rekurrierende Denkweise ohne Anwendung scheinbare Veränderlichen mit unendlichem Ausdehnungsbereich, Skrifter utgit av Videnskapsselskapet i Kristiania, I. Matematisk-Naturvidenskabelig Klasse 1923, no. 6; English transl., Jean van Heijenoort, From Frege to Gödel, a source book in mathematical logic, 1879-1931, Harvard Univ. Press, Cambridge, Mass., 1967, pp. 302-333.
- Raymond M. Smullyan, Theory of formal systems, Revised edition, Princeton University Press, Princeton, N. J., 1961. MR 0152429, DOI 10.1515/9781400882007 Turing, Allan Mathison, [1936-7] On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math. Soc. (2) 42, 230-265; A Correction, 43 (1937), 544-546. Turing, Allan Mathison, [1939] Systems of logic based on ordinals, Proc. London Math. Soc. (2) 45, 161-228.
Additional Information
- Journal: Bull. Amer. Math. Soc. 5 (1981), 43-61
- MSC (1980): Primary 03D20; Secondary 03D10, 03A05
- DOI: https://doi.org/10.1090/S0273-0979-1981-14920-X
- MathSciNet review: 614313