A remarkable eprint just appeared: T. Bolognesi, Causal sets from simple models of computation, arXiv:1004.3128.

In the theory of relativity, the relation “event A happened before event B” is not a total ordering relation. When events have space-like separation, the relation “before” is observer-dependent. By restricting attention to a partial ordering relation, that only applies to pairs of events with time-like separation, an observer-independent relation is obtained.

The theory of relativity is concerned with continuous, smooth manifolds. Computation is usually conceived of in terms of a discretized state space. To connect some aspects of the two, the new eprints defines a partial ordering relation on computational events (e.g. state transitions in a Turing machine) that represents a “before” relation. The resulting visualizations of the partial ordering relations as graphs are intriguing. Whether or not one believes this sort of mathematical structure will have useful applications in physics, the eprint is worth a read just for its visualizations.