An algebraic theory of recursive definitions and recursive languages

Abstract

This is the introductory paper in a series devoted to a general algebraic theory of recursive definitions" and "recursive languages". In this paper we present the fundamental concepts and theorems concerning the basic structure (basic syntax), the semantics and the combination and manipulation of "recursive definitions" and the closure properties of "recursive languages". The development is carried out within the framework of category theory and lattice theory. To illustrate the generality of the approach and our results we show how they apply directly to the specific examples of "recursive languages" of (generalized) context- free grammars, Turing machines, and flowcharts. Informally speaking, what I have in mind when I speak of a "recursive definition" are ,l such things as a Post canonical system, a Turing machine, a set of Herbrand-Godel equations, a context-free grammar, an iterative definition, a flowchart, an ALGOL program, a Markov algorithm, etc. Each of these things is some kind of syntactic object which has a "meaning" (e. g. a unique corresponding set, function, or relation) associated with it. In addition any specific such object has associated with it the whole family of objects which are "written" and "interpreted" in the same way. For example, associated with a given Turing machine defined in the manner of Davis (i. e. , with quadruples) we have the family of all Turing machines defined in this manner on the same alphabet. It seems natural to think of such a family as a "language" and indeed programming languages are "languages" in just this sense. It is intuitively clear that all these different notions of "recursive definitions are in some sense but specific examples of some fundamental type of mathematical entity, and the situation is almost as clear for "recursive languages. It seems only reasonable that we ought to be able to study these entities ("recursive definitions" and "recursive languages") as such rather than by means of a plethora of examples and that by doing so we ought to be able to establish many results once-and-for-all rather than case-by-case. Furthermore, such a general theory ought to provide a common framework in which to view, investigate and relate everything from finite automata to the highest level programming languages.