Abstract
This paper presents an algebraic theory of instruction sequences with
instructions for a random access machine (RAM) as basic instructions,
the behaviours produced by the instruction sequences concerned under
execution, and the interaction between such behaviours and RAM memories.
This theory provides a setting for the development of theory in areas
such as computational complexity and analysis of algorithm that
distinguishes itself by offering the possibility of equational reasoning
to establish whether an instruction sequence computes a given function
and being more general than the setting provided by any known version of
the RAM model of computation.
In this setting, a semi-realistic version of the RAM model of
computation and a bit-oriented time complexity measure for this version
are introduced.
Preprint available:
arXiv:2007.09946v3 [cs.PL]