Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)

 
 

 

The theory of recursive functions, approaching its centennial


Author: Stephen C. Kleene
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
Corrigendum: Bull. Amer. Math. Soc. (N.S.), Volume 5, Number 3 (1981), 364--364
MathSciNet review: 614313
Full-text PDF

References | Similar Articles | Additional Information

References [Enhancements On Off] (What's this?)

  • Wilhelm Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen, Math. Ann. 99 (1928), no. 1, 118–133 (German). MR 1512441, https://doi.org/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, https://doi.org/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, https://doi.org/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, https://doi.org/10.2307/1968702
  • Alonzo Church, An Unsolvable Problem of Elementary Number Theory, Amer. J. Math. 58 (1936), no. 2, 345–363. MR 1507159, https://doi.org/10.2307/2371045
  • Church, Alonzo, [1936a] A note on the Entscheidungsproblem, J. Symbolic Logic 1, 40-41; Correction, 101-102. MR 441682
  • 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, https://doi.org/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, https://doi.org/10.1007/BF01457115
  • David Hilbert, Über das Unendliche, Math. Ann. 95 (1926), no. 1, 161–190 (German). MR 1512272, https://doi.org/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, https://doi.org/10.1007/BF01565439
  • S. C. Kleene, 𝜆-definability and recursiveness, Duke Math. J. 2 (1936), no. 2, 340–353. MR 1545927, https://doi.org/10.1215/S0012-7094-36-00227-2
  • Kleene, Stephen, C., [ 1938] On notation for ordinal numbers, J. Symbolic Logic 3, 150-155.
  • Kleene, Stephen, C., [1943] Recursive predicates and quantifiers, Trans. Amer. Math. Soc. 53, 41-73. MR 7371
  • Kleene, Stephen, C., [1950] Recursive functions and intuitionistic mathematics, Proc. Internat. Congr. Math. (Cambridge, Mass., U.S.A., 1950), Amer Math. Soc., Providence, R. I., 1952, I, pp. 679-685. MR 44468
  • Kleene, Stephen, C., [1952] Introduction to metamathematics, North-Holland, Amsterdam, P. Noordhoff, Groningen and D. Van Nostrand, Toronto and New York. MR 51790
  • Kleene, Stephen, C., [1955] Arithmetical predicates and function quantifiers, Trans. Amer. Math. Soc. 79, 312-340. MR 70594
  • Kleene, Stephen, C., [1955a] On the forms of the predicates in the theory of constructive ordinals (second paper), Amer. J. Math. 77, 405-428. MR 70595
  • Kleene, Stephen, C., [1955b] Hierarchies of number-theoretic predicates, Bull. Amer. Math. Soc. 61, 193-213. MR 70593
  • 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.
  • Kleene, Stephen, C., [1958] Mathematical logic: constructive and non-constructive operations, Proc. Internat. Congr. Math. (Edinburgh, 1958) (J. A. Todd, ed.), Cambridge at the University Press, 1960, pp. 137-153. MR 114750
  • Kleene, Stephen, C., [1959] Recursive functionals and quantifiers of finite types. I, Trans. Amer. Math. Soc. 91, 1-52. MR 102480
  • Kleene, Stephen, C., [1963] Recursive functionals and quantifiers of finite types. II, Trans. Amer. Math. Soc. 108, 106-142. MR 153557
  • 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.
  • Kleene, Stephen, C., [1967] Mathematical logic, Wiley, New York, London and Sidney. MR 216930
  • 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) Stud. Logic Foundations Math., 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), Stud. Logic Foundations Math., 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, https://doi.org/10.1007/BF01458217
  • Marcov, A. A., [1951] Theory of algorithms, Amer. Math. Soc. Transl. (2) 15 (1960), 1-14. MR 114753
  • Marcov, A. A., [1954] Theory of algorithms, The National Science Foundation, Washington, D.C., the Department of Commerce, U.S.A., and the Israel Program for Scientific Translation, Jerusalem, 1961. MR 132690
  • 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, https://doi.org/10.1007/BF01448046
  • Rózsa Péter, Konstruktion nichtrekursiver Funktionen, Math. Ann. 111 (1935), no. 1, 42–60 (German). MR 1512975, https://doi.org/10.1007/BF01472200
  • Rózsa Péter, Über die mehrfache Rekursion, Math. Ann. 113 (1937), no. 1, 489–527 (German). MR 1513105, https://doi.org/10.1007/BF01571648
  • Post, Emil L., [1936] Finite combinatory processes-formulation 1, J. Symbolic Logic 1, 103-105. MR 20527
  • Post, Emil L., [1943] Formal reductions of the general combinatorial decision problem, Amer. J. Math. 65, 197-215. MR 7893
  • Post, Emil L., [1944] Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50, 284-316. MR 10514
  • 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.
  • Smullyan, Raymond M., [1961] Theory of formal systems, Annals of Math. Studies, no. 47, Princeton Univ. Press, Princeton, N. J. MR 152429
  • 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.

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (1980): 03D20, 03D10, 03A05

Retrieve articles in all journals with MSC (1980): 03D20, 03D10, 03A05


Additional Information

DOI: https://doi.org/10.1090/S0273-0979-1981-14920-X

American Mathematical Society