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.