A theory of computer instructions

AbstractJust as there is a theory of groups, or rings, or fields, or topological spaces, so there is presented here a theory of computer instructions. These are functions from S to S, where S is the set of states of a computer. Here S is a set of functions from M to B, where M is the memory (the set of variables) and B is a set of values; or alternatively, S is a cartesian product, over M as an index set, of the sets of values of all variables in M. For each instruction I there are defined the input region IR(I) and the output region OR(I); these are subsets of M. An instruction takes data from its input region and places data in its output region. Here OR(I) may be decomposed further into regions affected by subsets of M, which may be defined in either of two alternative ways. The theory presented here includes theorems concerning composition of instructions, decomposition of instructions, and the existence of instructions with specified regions. Many examples are given