Information Flow in Spatial Models of Computation

UoM administered thesis: Phd


Some models of computation have a notion of underlying space. In this thesis, we study the way in which information flows over this space in the course of computation, with the aim of discovering some geometric structure in the set of possible computations. We select cellular automata as a particular example to study. We define an abstract notion of information flow and characterize those which come from cellular automata. A slight generalization of the properties involved in the characterization includes what can be interpreted as a continuity condition on the flow of information. This condition can be thought of as giving an Alexandroff neighbourhood space (a mild generalization of a topological space) whose points are distributions of information. Motivated by this we study aspects of the structure of Alexandroff neighbourhood spaces. We show that any map from a simplicial complex into an Alexandroff space is homotopic to one of a simple combinatorial form.


Original languageEnglish
Awarding Institution
Award date1 Aug 2017