Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

The Development of Theoretical Computer Science - Origins of Recursive Function Theory

IP.com Disclosure Number: IPCOM000129363D
Original Publication Date: 1981-Jan-01
Included in the Prior Art Database: 2005-Oct-05
Document File: 18 page(s) / 69K

Publishing Venue

Software Patent Institute

Related People

STEPHEN C. KLEENE: AUTHOR [+2]

Abstract

[Figure containing following caption omitted: ©; 1981 by the American Federation of Information Processing Societies, Inc. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the AFIPS copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the American Federation of Information Processing Societies, Inc. To copy otherwise, or to republish, requires specific permission. Author's Address: Department of Mathematics, Van Vleck Hall, University of Wisconsin, Madison, WI 53706. Note: This is a revised version of a paper presented at the twentieth annual IEEE Symposium on Foundations of Computer Science, October 1979, San Juan, Puer. to Rico. ©; 1981 AFIPS 0164-1239/81/01052-67$01.00/0]

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 5% of the total text.

Page 1 of 18

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Copyright ©; 1981 by the American Federation of Information Processing Societies, Inc. Used with permission.

The Development of Theoretical Computer Science - Origins of Recursive Function Theory

STEPHEN C. KLEENE

(Image Omitted: Stephen C. Kleene was born in Hartford, Connecticut, in 1909. He graduated from Amherst College in 1930 and received a Ph.D. from Princeton University in 1934. He has taught mathematics at the University of Wisconsin since 1935. He was president of the Association for Symbolic Logic from 1956 to 1958 and was editor of the Journal of Symbolic Logic from 1950 to 1962. He was elected to the National Academy of Sciences in 1969.)

(Image Omitted: © 1981 by the American Federation of Information Processing Societies, Inc. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the AFIPS copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the American Federation of Information Processing Societies, Inc. To copy otherwise, or to republish, requires specific permission. Author's Address: Department of Mathematics, Van Vleck Hall, University of Wisconsin, Madison, WI 53706. Note: This is a revised version of a paper presented at the twentieth annual IEEE Symposium on Foundations of Computer Science, October 1979, San Juan, Puer. to Rico. © 1981 AFIPS 0164-1239/81/01052-67

The Development of Theoretical Computer Science - Origins of Recursive Function Theory

STEPHEN C. KLEENE

(Image Omitted: Stephen C. Kleene was born in Hartford, Connecticut, in 1909. He graduated from Amherst College in 1930 and received a Ph.D. from Princeton University in 1934. He has taught mathematics at the University of Wisconsin since 1935. He was president of the Association for Symbolic Logic from 1956 to 1958 and was editor of the Journal of Symbolic Logic from 1950 to 1962. He was elected to the National Academy of Sciences in 1969.)

.00/0)

For over two millenia mathematicians have used particular examples of algorithms for determining the values of functions. The notion of "A definability" was the first of what are now accepted as equivalent exact mathematics/descriptions of the class of the functions for which algorithms exist This article explains the notion and traces the investigation in 1931-1933 by which the notion was quite unexpectedly so accepted. The Herbrand-Godel notion of "general recursiveness" in 1934 and the Turing notion of "computability" in 1936 were the second and third equivalent notions. Techniques developed in the study of A-definability were applied in the analysis of general recursiveness and Turing compatability. Keywords: A-definability, undecidable sentences, general recursiveness, partial recursiveness, Turing computability, finite automata, recursion theorem, primitive rec...