Bounded action machines: Toward an abstract theory of computer structure

Abstract

The axiomatically defined Bounded Action Machine is presented as an approach to an abstract theory of computer structure-organization-architecture. The basic property of a Bounded, Action Machine is that there is a finite upper bound on the number of storage locations which can be active (contents "accessed or changed") at any step in the machine's operation. The paper starts with a precise formulation of this property within a very general framework. The study proceeds by investigating the consequences of imposing additional axioms on this basic structure; the new axioms being chosen so as to promote simpler and more uniform structure (i.e., so as to rule out "pathological structures"). This leads first to a characterization of "addressable memory". It is shown to be finite under very general conditions. The latter part, of the paper is addressed to the structure of the "remainder" of the memory. This culminates in a general characterization of the concept of "tapes". Together these results constitute a general characterization of the existing computer specie (including Turing machines). This paper includes comparison of this model with those of other authors and a discussion of possible directions of future research. © 1996 Academic Press, Inc.