A Concept of Equivalence Between Formally Defined Complexes of Interacting Digital Systems

Abstract

The environment of a formally defined complex of interacting digital systems is specified as a set of ideal, independent observers who can provide input as well as monitor any observable computation. Precise definitions are given for the behavior of an observer toward a system complex, the behavior of a system complex toward an observer, and the relative rates at which the systems of a complex can finish steps and transmit messages. These ideas are used in a very general definition of functional equivalence between system complexes; a sample equivalence proof and suggestions for more specialized forms of equivalence are added. It is argued that this definition compares favorably with other notions of equivalence because it is based on effective observations and allows equivalence classes to be as rich as possible.