Report Number: CS-TR-80-768
Institution: Stanford University, Department of Computer Science
Title: Causal nets or what is a deterministic computation
Author: Gacs, Peter
Author: Levin, Leonid A.
Date: October 1980
Abstract: We introduce the concept of causal nets - it can be considered as the most general and elementary concept of the history of a deterministic computation (sequential or parallel). Causality and locality are distinguished as the only important properties of nets representing such records. Different types of complexities of computations correspond to different geometrical characteristics of the corresponding causal nets - which have the advantage of being finite objects. Synchrony becomes a relative notion. Nets can have symmetries; therefore it will make sense to ask what can be computed from arbitrary symmetric inputs. Here, we obtain a complete group-theoretical characterization of the kind of symmetries that can be allowed in parallel computations.