OUTLINE OF A MATHEMATICAL THEORY OF COMPUTATION

Abstract

This paper introduces a theory of computation which is mathematical rather than operational in its approach. The theory is based on the idea that data types can be partially ordered by a relation similar to that of approximation, and as a result can be considered as complete lattices. The properties of these lattices and the functions on them are discussed in an informal manner and shown to be very suitable for developing a mathematical theory of the semantics of programming languages. A preliminary result of this approach is the construction of the first "mathematical" model for the λ-calculus.