Computable processes

Abstract

In this paper we study concurrent, asynchronous processes and functions on them which can be programmed using the (full) unfair or the fair merge operations. The main result is a normal form theorem for these (relatively) “computable process functions” which implies that although they can be very complex when viewed as classical set-functions, they are all “loosely implementable” in the sense of Park [7]. We also announce a variation and a substantial strengthening of the main “transfer principle” of [4] which have applications to the semantics and logic of programming languages with interactive (deterministic) or concurrent (non-deterministic) constructs.