Abstract
Studies of issues related to computability and computational complexity
involve the use of a model of computation. Pivotal to such a model are the
computational processes considered. Processes of this kind can be described
using an imperative process algebra based on ACP (Algebra of Communicating
Processes). In this paper, it is investigated whether the imperative process
algebra concerned can play a role in the field of models of computation. It is
demonstrated that the process algebra is suitable to describe in a
mathematically precise way models of computation corresponding to existing
models based on sequential, asynchronous parallel, and synchronous parallel
random access machines as well as time and work complexity measures for those
models. A probabilistic variant of the model based on sequential random access
machines and complexity measures for it are also described.