Bounded action machines II: The basic structure of Tapeless computers

Abstract

This paper presents mathematical results concerning the basic structure of computers without tapes. We start by introducing a simple and very general axiomatic model of a computer without tapes (The "Tapeless" Bounded Action Machine). We then impose additional conditions (axioms) upon this basic structure and employ them to characterize such structural properties as: the existence of a processor; the modifiability of a processor; the relationship between the contents of the set of active locations at a given step (the memory locations whose contents are accessed or changed at that step) and the selection of the active locations at the given and following step; and the existence of control registers. The bulk of the paper consists of results concerning the relationships between these properties. In particular the paper shows that the basic structure of "conventional computers" is a consequence of the existence of control registers. Finally these results are generalized to computers with one-step indirect addressing. © 1972 Springer-Verlag.