Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-22T04:58:10.907Z Has data issue: false hasContentIssue false
  • English
  • Français

The Mathematical Work of S.C.Kleene

Published online by Cambridge University Press:  15 January 2014

J.R. Shoenfield
J.R. Shoenfield*
Affiliation:
Department of Mathematics, Duke university, Durham, Nc 27706, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

§1. The origins of recursion theory. In dedicating a book to Steve Kleene, I referred to him as the person who made recursion theory into a theory. Recursion theory was begun by Kleene's teacher at Princeton, Alonzo Church, who first defined the class of recursive functions; first maintained that this class was the class of computable functions (a claim which has come to be known as Church's Thesis); and first used this fact to solve negatively some classical problems on the existence of algorithms. However, it was Kleene who, in his thesis and in his subsequent attempts to convince himself of Church's Thesis, developed a general theory of the behavior of the recursive functions. He continued to develop this theory and extend it to new situations throughout his mathematical career. Indeed, all of the research which he did had a close relationship to recursive functions.

Church's Thesis arose in an accidental way. In his investigations of a system of logic which he had invented, Church became interested in a class of functions which he called the λ-definable functions. Initially, Church knew that the successor function and the addition function were λ-definable, but not much else. During 1932, Kleene gradually showed1 that this class of functions was quite extensive; and these results became an important part of his thesis 1935a (completed in June of 1933).

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 1 , Issue 1 , March 1995 , pp. 9 - 43
Copyright
Copyright © Association for Symbolic Logic 1995

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

Kleene Bibliography

A bibliography of Kleene's work through 1980 is contained in the volume The Kleene Symposium [2], which also contains a complete list of his Ph.D. students and a brief biography. This bibliography lists only research articles and expository articles written for mathematicians.

Kleene's, [1934] Proof by cases in formal logic, Annals of Mathematics, vol. 35 (1934), pp. 529–544.Google Scholar
Kleene's, [1935a] A theory of positive integers in formal logic, American Journal of Mathematics, vol. 57 (1935), pp. 153–173, 219–244.Google Scholar
Kleene's, [1935b] The inconsistency of certain formal logics, with Rosser, J. B., Annals of Mathematics, vol. 36 (1935), pp. 630–636.Google Scholar
Kleene's, [1936a] General recursive functions of natural numbers, Mathmatische Annalen, vol. 112 (1936), pp. 727–742.CrossRefGoogle Scholar
Kleene's, [1936b] λ-definability and recursiveness, Duke Mathematical Journal, vol. 2 (1936), pp. 340–353.Google Scholar
Kleene's, [1936c] A note on recursive functions, Bulletin of the American Mathematical Society, vol. 42 (1936), pp. 544–546.Google Scholar
Kleene's, [1936d] Formal definitions in the theory of ordinal numbers, with Church, Alonzo, Fundamenta Mathematica, vol. 28 (1936), pp. 11–21.Google Scholar
Kleene's, [1938] On notation for ordinal numbers, Journal of Symbolic Logic, vol. 3 (1938), pp. 150–155.Google Scholar
Kleene's, [1939] A postulational basis for probability, with Evans, H. P., American Mathematical Monthly, vol. 46 (1939), pp. 141–148.Google Scholar
Kleene's, [1943] Recursive predicates and quantifiers, Transactions of the American Mathematical Society, vol. 53 (1943), pp. 41–73.Google Scholar
Kleene's, [1944] On the form of the predicates in the theory of constructive ordinals, American Journal of Mathematics, vol. 66 (1944), pp. 41–58.Google Scholar
Kleene's, [1945] On the interpretation of intuitionistic number theory, Journal of Symbolic Logic, vol. 10 (1945), pp. 109–124.Google Scholar
Kleene's, [1947] Analysis of lengthening of modulated repetitive pulses, Proceedings of the Institute of Radio Engineers, vol. 35 (1947), pp. 1049–1053.Google Scholar
Kleene's, [1950] A symmetric form of Godel's theorem, Indagationes Mathematicae, vol. 12 (1950), pp. 244–246.Google Scholar
Kleene's, [1952a] Two papers on the predicate calculus, Memoirs of the American Mathematical Society, no. 10, Americal Mathematical Society, 1952.Google Scholar
Kleene's, [1952b] Introduction to metamathematics, North-Holland Publishing Co., 1952.Google Scholar
Kleene's, [1954] The upper semi-lattice of degrees of unsolvability, with Post, Emil L., Annals of Mathematics, vol. 59 (1954), no. 2, pp. 379–407.Google Scholar
Kleene's, [1955a] Arithmetical predicates and function quantifiers, Transactions of the American Mathematical Society, vol. 79 (1955), pp. 312–340.Google Scholar
Kleene's, [1955b] On the form of the predicates in the theory of constructive ordinals (second paper), American Journal of Mathematics, vol. 77 (1955), pp. 405–428.Google Scholar
Kleene's, [1955c] Hierarchies of number-theoretic predicates, Bulletin of the American Mathematical Society, vol. 79 (1955), pp. 312–340.Google Scholar
Kleene's, [1956a] Representation of events in nervenets and finite automata, Automata studies, Annals of Mathematical Studies, no. 34, Princeton University Press, 1956, pp. 3–41.Google Scholar
Kleene's, [1956b] A note on computable functionals, Indagationes Mathematicae, vol. 18 (1956), pp. 275–280.CrossRefGoogle Scholar
Kleene's, [1957] A note on function quantification, with Addlson, John, Proceedings of the American Mathematical Society, vol. 8 (1957), pp. 1002–1006.Google Scholar
Kleene's, [1958] Extension of an effectively generated class of functions by enumeration, Colloquium Mathematicum, vol. 6 (1958), pp. 67–78.Google Scholar
Kleene's, [1959a] Recursive functionals and quantifiers of finite types I, Transactions of the American Mathematical Society, vol. 91 (1959), pp. 1–52.Google Scholar
Kleene's, [1959b] Countable functionals, Constructivity in mathematics, proceedings of the colloquium held in Amsterdam 1957, North-Holland Publishing Co., 1959, pp. 81–100.Google Scholar
Kleene's, [1959c] Quantifiers of number-theoretic functions, Compositio Mathematica, vol. 14 (1959), pp. 23–40.Google Scholar
Kleene's, [1960] Realizability and Shanins algorithm for the constructive deciphering of mathematical sentences, Logique et Analyse, vol. 3 (1960), pp. 154–165.Google Scholar
Kleene's, [1962a] Disjunction and existence under implication in elementary intuitionistic formalisms, Journal of Symbolic Logic, vol. 27 (1962), pp. 11–18, Addendum, [1962a] Disjunction and existence under implication in elementary intuitionistic formalisms, Journal of Symbolic Logic, vol. 28 (1963), pp. 154-156.Google Scholar
Kleene's, [1962b] Turing-machine computable functionals of finite types I, Logic, methodology, and philosophy of science: Proceedings of the 1960 international congress, Stanford University Press, 1962, pp. 38–45.Google Scholar
Kleene's, [1962c] Turing-machine computable functionals of finite types II, Proceedings of the London Mathematical Society, vol. 12 (1962), no. 3, pp. 245–258.Google Scholar
Kleene's, [1962d] Lambda-definable functionals of finite type, Fundamenta Mathematicae, vol. 50 (1962), pp. 281–303.Google Scholar
Kleene's, [1962e] Herbrand-Gödel-style recursivefunctionals of finite types, Recursive function theory, Proceedings of the Symposia in Pure Mathematics, vol. 5, American Mathematical Society, 1962, pp. 49–75.Google Scholar
Kleene's, [1963] Recursive functionals and quantifiers of finite type II, Transactions of the American Mathematical Society, vol. 108 (1963), pp. 106–142.Google Scholar
Kleene's, [1965] The foundations of intuitionistic matehmatics, especially in relation to recursive functions, with Vesley, Richard, North Holland Publidhing Company, 1965.Google Scholar
Kleene's, [1967] Mathematical logic, Wiley, 1967, 398pp.Google Scholar
Kleene's, [1969] Formalized recursive functionals and formalized realizability, Memoirs of the American Mathematical Society, no. 89, Americal Mathematical Society, 1969.Google Scholar
Kleene's, [1973] Realizability: a retrospective survey, Cambridge summer school in mathematical logic, Lecture Notes in Mathematics, no. 337, Springer-Verlag, 1973, pp. 95–112.Google Scholar
Kleene's, [1976] The work of Kurt Gödel, Journal of Symbolic Logic, vol. 41 (1976), pp. 761–778, Addendum, [1976] The work of Kurt Godel, Journal of Symbolic Logic, vol. 43 (1978), p. 613.Google Scholar
Kleene's, [1978] Recursive functionals and quantifiers of finite type revisited I, Generalized recursion theory II: Proceedings of the 1977 Oslo symposium, North-Holland Publishing Co., 1978, pp. 185–222.Google Scholar
Kleene's, [1980] Recursive functionals and quantifiers of finite type revisisted II, The Kleene symposium, Studies in logic and the foundations of mathematics, no. 101, North-Holland Publishing Co., 1980, pp. 1–29.Google Scholar
Kleene's, [1981a] Origins of recursive function theory, Annals of the History of Computing, vol. 3 (1981), pp. 52–65.Google Scholar
Kleene's, [1981b] The theory of recursive functions, approaching its centennial, Bulletin of the American Mathematical Society, vol. 5 (1981), pp. 43–61.Google Scholar
Kleene's, [1982] Recursive functionals and quantifiers of finite type revisited III, Patras logic symposium, Studies in logic and foundations of mathematics, no. 109, North-Holland Publishing Co., 1982, pp. 1–40.Google Scholar
Kleene's, [1984] Unimonotone functions of finite type (recursive functionals and quantifiers of finite type revisited IV), Recursion theory, Proceedings of Symposia in Pure MathematicsN, vol. 42, American Mathematical Society, 1984, pp. 119–138.Google Scholar
Kleene's, [1987] Reflections on Church's Thesis, Notre Dame Journal of Formal Logic, vol. 28 (1987), pp. 490–498.Google Scholar
[1] Addison, J. W., Separation principles in the hierarchies of classical and effective descriptive set theory, Fundamenta Mathematicae, vol. 46 (1959), pp. 123–135.Google Scholar
[2] Jon Barwise, H. Jerome Keisler, and Kunen, Kenneth (editors), The Kleene symposium, Studies in Logic, vol. 101, North Holland Publishing Company, Amsterdam, New York, Oxford, 1980.Google Scholar
[3] Hindley, Roger and Seldin, Jonathan, Introduction to combinators and λ-calculus, Cambridge University Press, 1986.Google Scholar
[4] Kierstead, David, Syntax and semantics in higher-type recursion theory, Transactions of the American Mathematical Society, vol. 276 (1983), pp. 67–105.Google Scholar
[5] Moschovakis, Joan Rand, Disjunction and existence in formalized intuitionistic analysis, Proceedings of the summer school in mathematical logic, Leicester, North-Holland Publishing Co., 1967, pp. 309–331.Google Scholar
[6] Nelson, David, Recursive functions and intuitionistic number theory, Transactions of the American Mathematical Society, vol. 61 (1967), pp. 307–368.Google Scholar
[7] Normann, David, Recursion on countable functionals, Lecture Notes in Mathematics, no. 811, Springer-Verlag, 1980.Google Scholar
[8] Platek, Richard, Foundations of recursion theory, Ph.D. thesis , Stanford University, 1966.Google Scholar
[9] Post, Emil, Recursively enumerable sets of positive integers and their decision problem, Bulletin of the American Mathematical Society, vol. 50 (1944), pp. 284–316.CrossRefGoogle Scholar
[10] Soare, Robert, Recursively enumerable sets and degrees, Springer-Verlag, 1987.Google Scholar
[11] Spector, Clifford, Recursive well-orderings, Journal of Symbolic Logic, vol. 20 (1955), pp. 151–163.Google Scholar
[12] Spector, Clifford, On degrees of recursive unsolvability, Annals of Mathematics, vol. 64 (1956), no. 2, pp. 581–592.Google Scholar
[13] Turing, Alan, Computability and λ-definability, Journal of Symbolic Logic, vol. 2 (1937), pp. 153–163.Google Scholar