Navigation within Allocentric Cognitive Maps is Computationally Universal

This article presents three proofs showing that idealized architectures capable of navigation guided by allocentric maps with landmark structure can be computationally universal. The navigation may occur either online (in the environment) or offline (in the animal’s head). The first proof proceeds from two-counter machines by encoding counters as the positions of two movable markers on orthogonal coordinate axes. The second proof directly simulates an ordinary one-tape Turing machine by using a writable tape-path embedded in the map. The third proof strengthens locality by replacing the globally designated path with a two-dimensional field of landmarks that carries only local predecessor/successor information. These constructions are mathematically close to classical graph-based models in computability theory, including Kolmogorov-Uspensky machines, storage-modification machines, graph Turing machines, and related navigation-on-graphs models. Accordingly, the bare universality results are mathematically unsurprising. Nevertheless, as far as I know, the present treatment is the first self-contained reconstruction of such universality demonstrations in the framework of navigation within allocentric cognitive maps, that is, within an architecture whose core representational and computational primitives are drawn from a body of empirical and theoretical work on spatial navigation. The article therefore reframes known computability-theoretic ideas to show that an allocentric navigation-based architecture can be computationally universal. This opens the possibility of reconstructing aspects of biological cognition, including symbolic processing, in terms of map-based computation.