Book contents
- Frontmatter
- Contents
- Preface
- List of Participants
- CLASSICAL RECURSION THEORY
- GENERALISATIONS
- APPLICATIONS
- Computing in Algebraic Systems
- Applications of Classical Recursion Theory to Computer Science
- “Natural” Programming Languages and Complexity Measures for Subrecursive Programming Languages: An Abstract Approach
Applications of Classical Recursion Theory to Computer Science
Published online by Cambridge University Press: 09 February 2010
- Frontmatter
- Contents
- Preface
- List of Participants
- CLASSICAL RECURSION THEORY
- GENERALISATIONS
- APPLICATIONS
- Computing in Algebraic Systems
- Applications of Classical Recursion Theory to Computer Science
- “Natural” Programming Languages and Complexity Measures for Subrecursive Programming Languages: An Abstract Approach
Summary
Introduction
In introducing his definitive work on recursion theory, Rogers (1967) remarks
“… our emphasis will be extensional, in that we shall be more concerned with objects named (functions) than with objects serving as names (algorithms).”
Computer scientists are interested in algorithms; their existence, expression, relative efficiency, comprehensibility, accuracy, and structure. Many computer scientists are more interested in algorithms themselves, rather than what is computed by them. In the sequel will emphasize and exploit the intensional aspects of recursion theory. Our intention is to substantiate the claim that the formalisms and techniques of recursive function theory can be applied to obtain results of interest in computer science. In what follows we will survey results which yield insights into the nature of programming techniques, complexity of programs, and the inductive inference of programs given examples of their intended input-output behavior. The results presented below are from the field of intensional recursion theory in that they make assertions concerning algorithms and their proofs use the recursion theoretic techniques of diagonalization and recursion. Furthermore, in many instances, these techniques are applied intensionally in that they are used to specify an algorithm which manipulates other algorithms syntactically without necessarily any knowledge of the function specified by the manipulated algorithms. We include proofs only to illustrate the intensionality of their techniques.
First we introduce the necessary concepts and notation of recursive function theory from the perspective of a computer scientist. We start with an enumeration of the closure under concatenation of some arbitrary, but fixed, finite alphabet. An element of the enumeration is called a file. Files contain text which will be interpreted as either a program or as data.
- Type
- Chapter
- Information
- Recursion Theory, its Generalisations and Applications , pp. 236 - 247Publisher: Cambridge University PressPrint publication year: 1980