Navigation within Allocentric Cognitive Maps is Computationally Universal

Navigation within Allocentric Cognitive Maps is Computationally Universal | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Navigation within Allocentric Cognitive Maps is Computationally Universal Gualtiero Piccinini This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-9307584/v1 This work is licensed under a CC BY 4.0 License Status: Under Review Version 1 posted 8 You are reading this latest preprint version Abstract 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. Turing universality Turing machines cognitive maps allocentric representation navigation-based computation 1. Introduction This article proves three sufficiency theorems showing that idealized navigation-based architectures with allocentric maps and landmark structure can be computationally universal. The underlying mathematical ideas are close to classical results from computability theory, especially work on counter machines, graph-based machines, and locally navigable memory structures. The present contribution is to reconstruct those ideas explicitly in the framework of navigation within allocentric cognitive maps, that is, within a type of computational architecture that is independently motivated by empirical and theoretical work in neuroscience. This shows how established universality constructions can be reformulated inside an allocentric navigation-based architecture. In contemporary neuroscience, allocentric cognitive maps are widely discussed representational and computational structures that organize knowledge relative to stable environmental features rather than momentary egocentric position (Behrens et al., 2018 ; Epstein et al., 2017 ; O’Keefe & Nadel, 1978). Many animals use allocentric, landmark-anchored spatial representations in navigation (Basu & Nagel, 2024 ). In mammals, hippocampal activity can replay previously experienced trajectories and, in some cases, preplay trajectories later expressed during navigation (Carr et al., 2011 ; Dragoi & Tonegawa, 2011 ). There is increasing evidence that hippocampal-entorhinal cognitive maps support functions beyond navigation, including memory, inference, and abstract relational knowledge, and that related map-like representations are present in other brain regions (Courellis et al., 2024 ; Whittington et al., 2022 ; Wikenheiser & Schoenbaum, 2016 ). This evidence raises the question of what representational and computational power cognitive maps possess. This article makes precise and proves a family of claims of the following form: an architecture that represents space in an allocentric coordinate system, represents landmarks at locations within that system, stores information at landmarks, can internally simulate navigation among those landmarks, and can internally simulate performing operations at those landmarks can compute any Turing-computable function under idealizations that are standard in computability theory. While the primary target of this article is the representational and computational power of architectures capable of internally simulating navigation and action within cognitive maps, offline simulation is not necessary for the universality results to obtain. The sort of allocentric navigation investigated in this article may be entirely simulated in an animal’s head or it may occur partly or wholly within the animal’s environment. The extent to which navigation occurs online or offline makes a difference to how cognitively demanding the task is, because keeping track of all the needed information in one’s head requires more cognitive resources than storing some of that information in the environment. For the purposes of the universality results, however, that difference is immaterial so long as the same operations are available. The benchmark is Turing universality in the standard sense established by Turing's analysis of effective calculability (Turing, 1937 ). A convenient auxiliary benchmark is universality via counter or register machines, especially the simple two-counter models associated with Minsky and related register-machine formalisms (Dudenhefner, 2022 ; Minsky, 1967 ; Shepherdson & Sturgis, 1963 ). The first proof simulates two-counter machines by using two movable markers on the coordinate axes to encode unbounded counters. The second proof simulates standard one-tape Turing machines by embedding a writable tape-path in the allocentric map. The third proof is the most local: it still simulates ordinary Turing machines directly, but it dispenses with any globally indexed path available to the machine itself and uses only local directional information at neighboring landmarks. The constructions are mathematically close to several classical graph-based machine models. Accordingly, the bare universality results are mathematically unsurprising. What is new here, as far as I know, is the explicit reconstruction of those results inside a navigation-based allocentric-map architecture of a kind that is independently motivated by cognitive neuroscience. The significance of this contribution is architectural and interdisciplinary: it shows that an architecture often associated primarily with spatial navigation can, under standard idealizations, realize universal computation. This conclusion bears on a line of criticism according to which nonclassical architectures uncovered by mainstream neuroscience, including cognitive maps, lack sufficient representational or computational power to explain cognition, and so additional classical “symbolic” Turing- or von Neumann-style architectures must be posited and invoked instead (e.g., Fodor & Pylyhyn, 1988; Gallistel & King, 2009 ). It also bears on arguments that neural states count as representations only if they play a computational role (Krakauer & Ramsey, 2026 ). The present results show that navigation-based architectures have sufficient representational and computational power in principle. Under idealizations routinely adopted in computability theory, such architectures suffice for Turing universality. This entails that such architectures can, in principle, realize arbitrarily complex computable transformations, including transformations with the kinds of productivity, systematicity, and compositionality often taken to require a classical symbolic architecture. This, in turn, opens the possibility of explaining higher cognition, including symbolic processing, in terms of cognitive map-based computation. Cognitive maps do not normally store and process symbols in any linguistic or language-like sense. What they store is information about the allocentric relations among locations, landmarks, and other items located within the map, together with operations that may be performed on such items. The present results show that those resources are sufficient for universal computation. Symbolic processing therefore need not be treated as architecturally basic but may instead be reconstrued in terms of map-like resources already known to exist in the brain. At the same time, I do not argue that any biological system literally implements a Turing machine or any other classical computing device, whether universal or otherwise. Nor do I imply that implementing classical Turing-style computation within cognitive maps is required to explain cognition. The point is, rather, that a computational architecture often seen as capable at best of allegedly “low-level” cognitive tasks such as navigation, or perhaps too weak even for navigation without the support of allegedly more powerful symbolic architectures (e.g., Gallistel & King, 2009 ) can, under standard idealizations, support universal computation. To that extent, cognitive map-based architectures are rich enough in principle to realize any computable cognitive function. Whether they in fact explain cognition, and if so whether they do it by classical or nonclassical means, is a separate empirical question. The remainder of this article proceeds as follows: Section 2 outlines historical antecedents, Section 3 provides formal preliminaries, Sections 4 through 6 present the three proofs of universality, Section 7 discusses the significance of the proofs, Section 8 discusses the proofs’ scope, and Section 9 concludes. 2. Historical background While the motivation for the present results stems from reflections on the relation between allocentric cognitive maps and computational universality, the proofs have historical antecedents within computability theory (Table 1 ). The most relevant computability-theoretic predecessors are graph-based machines in which memory is not a linear tape but a mutable or navigable graph with a distinguished active location. The oldest example is Kolmogorov and Uspensky’s graph-based conception of algorithmic computation. In this model, machines operate locally on graph-structured memory, and the resulting class of machines computes all partial recursive functions (Kolmogorov & Uspensky, 1958/1963). A second close predecessor is Schönhage's storage-modification machine. Here memory is represented by a mutable directed graph and computation proceeds by local pointer manipulations around an active node. This is mathematically very close to a navigation-based architecture in which an agent accesses and updates memory through local moves among landmarks (Schönhage, 1980 ). A third close family is provided by graph Turing machines. Ackerman and Freer formulate computation on vertex-labeled, edge-colored graphs and explicitly prove that ordinary Turing computation can be recovered inside that framework. Their model differs from the present one in being designed first and foremost as a graph-computation formalism rather than as a cognitive-map architecture, but it is plainly relevant for any claim that graph-like spatial organization plus local rules can support universality (Ackerman & Freer, 2017 ). There is also a neighboring literature on graph-walking automata and graph exploration. This work is relevant because it treats movement through a graph as a computational primitive and analyzes how much can be achieved when an automaton navigates an environment using only local information. At the same time, this literature is useful as a cautionary contrast: finite-state navigation by itself is generally not universal unless one adds unbounded memory resources (Fraigniaud et al., 2005 ; Okhotin, 2019 ). On the neurocognitive side, the allocentric-map framework used in this article is motivated by a large literature on hippocampal and entorhinal representations. The original cognitive-map program of O'Keefe and Nadel was linked to place-cell evidence, and subsequent work on place cells, grid cells, boundary cells, head-direction cells, and related systems has made allocentric spatial coding a central part of contemporary theories of navigation and memory (Behrens et al., 2018 ; Moser et al., 2008 ; O'Keefe & Dostrovsky, 1971 ; O'Keefe & Nadel, 1978 ). As far as I have been able to determine, no prior source makes universality arguments explicit in the distinctive vocabulary of allocentric coordinates, landmarks, and navigation while simultaneously situating the architecture within the empirical cognitive-map literature. In this respect the results are mathematically unsurprising but conceptually novel and theoretically significant for the mind sciences. Table 1 Overview of the three constructions and their closest prior analogues. Construction Primary memory encoding Simulation target Closest prior family Main significance Counter-map proof Two movable marker positions on orthogonal axes Two-counter machine Register/counter machines Shows that genuinely spatial position alone can encode unbounded memory Tape-path proof Writable labels on landmarks along a designated bi-infinite path Ordinary one-tape Turing machine Graph Turing machines / tape-on-graph models Directly identifies landmarks with memory cells Local-layout proof Writable labels plus only local predecessor/successor cues in a 2D field Ordinary one-tape Turing machine Kolmogorov-Uspensky / SMM / local graph machines Most faithful to navigation among landmarks using only local structure 3. Preliminaries Definition 3.1 (Deterministic one-tape Turing machine). A deterministic one-tape Turing machine is a tuple $$\:M=(Q,{\Gamma\:},\square\:,{q}_{0},{q}_{h},\delta\:),$$ where \(\:Q\) is a finite set of states, \(\:{\Gamma\:}\:\) is a finite tape alphabet, \(\:\square\:\) is the distinguished blank symbol, \(\:{q}_{0}\) is the start state, \(\:{q}_{h}\:\) is the halting state, and $$\:\delta\::(Q\setminus\:\{{q}_{h}\left\}\right)\times\:{\Gamma\:}\to\:Q\times\:{\Gamma\:}\times\:\{L,R\}$$ is the transition function. A configuration is a triple $$\:(q,h,t),$$ where \(\:q\in\:Q\:\) is the current state, \(\:h\in\:\mathbb{Z}\) is the head position, and $$\:t:\mathbb{Z}\to\:{\Gamma\:}$$ is the tape-content function, with \(\:t\left(i\right)=\square\:\) for all but finitely many \(\:i\in\:\mathbb{Z}\) . Definition 3.2 (Deterministic two-counter machine). A deterministic two-counter machine consists of a finite set of instruction labels $$\:L=\{{\mathcal{l}}_{0},{\mathcal{l}}_{1},\dots\:,{\mathcal{l}}_{m-1},{\mathcal{l}}_{h}\},$$ two counters \(\:{c}_{1},{c}_{2}\in\:\mathbb{N}\) , and one instruction attached to each non-halting label. The permitted instruction forms are $$\:{\text{I}\text{n}\text{c}}_{1}\left({\mathcal{l}}_{j}\right),{\:\text{I}\text{n}\text{c}}_{2}\left({\mathcal{l}}_{j}\right),{\:\text{J}\text{Z}\text{D}\text{e}\text{c}}_{1}({\mathcal{l}}_{j},{\mathcal{l}}_{k}),{\:\text{J}\text{Z}\text{D}\text{e}\text{c}}_{2}({\mathcal{l}}_{j},{\mathcal{l}}_{k}).$$ Their operational semantics are as follows. \(\:{\text{I}\text{n}\text{c}}_{1}\left({\mathcal{l}}_{j}\right)\) : replace \(\:{c}_{1}\:\) by \(\:{c}_{1}+1\) and jump to \(\:{\mathcal{l}}_{j}\) . \(\:{\text{I}\text{n}\text{c}}_{2}\left({\mathcal{l}}_{j}\right)\) : replace \(\:{c}_{2}\) by \(\:{c}_{2}+1\) and jump to \(\:{\mathcal{l}}_{j}\) . \(\:{\text{J}\text{Z}\text{D}\text{e}\text{c}}_{1}({\mathcal{l}}_{j},{\mathcal{l}}_{k})\) : if \(\:{c}_{1}=0\) , jump to \(\:{\mathcal{l}}_{j}\) ; otherwise replace \(\:{c}_{1}\:\) by \(\:{c}_{1}-1\) and jump to \(\:{\mathcal{l}}_{k}\) . \(\:{\text{J}\text{Z}\text{D}\text{e}\text{c}}_{2}({\mathcal{l}}_{j},{\mathcal{l}}_{k})\) : if \(\:{c}_{2}=0\) , jump to \(\:{\mathcal{l}}_{j}\) ; otherwise replace \(\:{c}_{2}\) by \(\:{c}_{2}-1\) and jump to \(\:{\mathcal{l}}_{k}\) . A configuration is a triple ( \(\:{\mathcal{l}}_{i},\:m,\:\:n)\) , where \(\:{\mathcal{l}}_{i}\in\:L\:\) is the current instruction label and \(\:m,n\) are the values of \(\:{c}_{1},{c}_{2}\) . Deterministic two-counter machines are a standard universal model of computation (Dudenhefner, 2022 ; Minsky, 1967 ). Definition 3.3 (Criterion of universality). For each navigation architecture \(\:A\) considered below, universality is established by an effective simulation theorem: for every machine \(\:M\:\) in a known universal model, there is a machine \(\:{A}_{M}\:\) realized in the navigation architecture and a computable encoding \(\:E\) of configurations such that each machine step of \(\:M\:\) is mirrored exactly by one macro-step of \(\:{A}_{M}\) . A macro-step may consist of finitely many primitive navigation actions, but it corresponds to one instruction of the simulated machine. 4. Universality by navigation on two coordinate axes The first architecture treats the allocentric map as a genuinely two-dimensional storage medium, but in a highly compressed way. One movable marker \(\:X\) is constrained to move on the \(\:x\) -axis and one movable marker \(\:Y\:\) is constrained to move on the \(\:y\) -axis. Their distances from the origin encode the values of two unbounded counters. The internal control state of the machine plays the role of the finite control of a counter machine. Definition 4.1 (Counter-based allocentric navigation machine). A counter-based allocentric navigation machine has an internal map \(\:{\mathbb{N}}^{2}\:\) with origin \(\:O=\left(\text{0,0}\right)\) , two movable markers \(\:X\) and \(\:Y\:\) constrained to the \(\:x\) -axis and \(\:y\) -axis respectively, a finite control set \(\:Q\) , and a navigator cursor. A configuration is a quadruple $$\:(q,p,x,y),$$ where \(\:q\in\:Q\) is the control state, \(\:p\in\:{\mathbb{N}}^{2}\:\) is the cursor position, \(\:X\:\) is at \(\:(x,0)\) , and \(\:Y\:\) is at \(\:(0,\:y)\) . Primitive operations allow the cursor: to move one step east, west, north, or south whenever the resulting position remains in \(\:{\mathbb{N}}^{2}\) ; to test whether the current position is the origin; to test whether the current position coincides with \(\:X\) or \(\:Y\) ; to move \(\:X\:\) one step east or west along the \(\:x\) -axis when the cursor is at \(\:X\) ; to move \(\:Y\:\) one step north or south along the \(\:y\) -axis when the cursor is at \(\:Y\) ; and to change the control state. Theorem 4.2 For every deterministic two-counter machine \(\:M\) , there exists a counter-based allocentric navigation machine \(\:{A}_{M\:}\) that simulates \(\:M\:\) exactly, one machine instruction at a time. Consequently, the class of counter-based allocentric navigation machines is Turing universal. Proof Fix a deterministic two-counter machine \(\:M\:\) with instruction labels $$\:L=\{{\mathcal{l}}_{0},\dots\:,{\mathcal{l}}_{m-1},{\mathcal{l}}_{h}\}.$$ Construct \(\:{A}_{M}\:\) so that its control states $$\:{q}_{0},\dots\:,{q}_{m-1},{q}_{h}$$ correspond exactly to the instruction labels of \(\:M\) . Encode a machine configuration \(\:\left({\mathcal{l}}_{i},m,n\right)\:\) by $$\:E({\mathcal{l}}_{i},m,n)=({q}_{i},O,m,n),$$ where \(\:O\) denotes the cursor at the origin, the position of \(\:X\) at \(\:(m,\:0)\:\) represents counter \(\:1\) , and the position of \(\:Y\) at \(\:(0,\:n)\:\) represents counter \(\:2\) . Encode the four instruction forms as finite navigation macros. An instruction \(\:{\text{I}\text{n}\text{c}}_{1}\left({\mathcal{l}}_{j}\right)\:\) is implemented by moving the cursor east step by step from the origin along the \(\:x\) -axis until the cursor reaches \(\:X\) , shifting \(\:X\) one step east, returning west step by step to the origin, and entering control state \(\:{q}_{j}\) . An instruction \(\:{\text{I}\text{n}\text{c}}_{2}\left({\mathcal{l}}_{j}\right)\:\) is implemented analogously on the \(\:y\) -axis. An instruction \(\:{\text{J}\text{Z}\text{D}\text{e}\text{c}}_{1}\left({\mathcal{l}}_{j},{\mathcal{l}}_{k}\right)\:\) first checks at the origin whether the current position coincides with \(\:X\) . If so, the machine leaves \(\:X\:\) unchanged and enters \(\:{q}_{j}\) . If not, it moves east step by step until the cursor reaches \(\:X\) , shifts \(\:X\:\) one step west, returns west step by step to the origin, and enters \(\:{q}_{k}\) . The instruction \(\:{\text{J}\text{Z}\text{D}\text{e}\text{c}}_{2}\left({\mathcal{l}}_{j},{\mathcal{l}}_{k}\right)\:\) is symmetric. Every macro terminates because the cursor traverses only a finite distance equal to the current counter value. One-step correctness follows by inspection of the four instruction forms. If \(\:M\:\) performs an increment instruction, then the corresponding marker in \(\:{A}_{M}\:\) is shifted exactly one unit in the appropriate axis direction and the control state changes exactly as prescribed. If \(\:M\:\) performs \(\:\text{J}\text{Z}\text{D}\text{e}\text{c}\:\) on a zero counter, then the cursor at the origin detects the corresponding marker there and \(\:{A}_{M}\) follows the zero branch without moving the marker. If the counter is positive, \(\:{A}_{M}\:\) moves the marker one unit toward the origin and takes the nonzero branch. In every case, the resulting navigation configuration is exactly the encoding of the successor configuration of \(\:M\) . Induction on the number of machine steps now yields: whenever $$\:{C}_{0}\to\:{C}_{1}\to\:\cdots\:\to\:{C}_{k}$$ is a run of \(\:M\) , the encoded sequence $$\:E\left({C}_{0}\right)\Rightarrow\:E\left({C}_{1}\right)\Rightarrow\:\cdots\:\Rightarrow\:E\left({C}_{k}\right)$$ is a run of \(\:{A}_{M}\) , where each double arrow denotes one encoded macro-step. Halting is preserved because \(\:{q}_{h}\:\) is reached if and only if \(\:{\mathcal{l}}_{h}\:\) is reached. Therefore, \(\:{A}_{M}\:\) computes the same partial function as \(\:M\) . Since deterministic two-counter machines are universal, the architecture is Turing universal. This first proof is mathematically straightforward and historically unsurprising, but it makes vivid the idea that a two-dimensional map can already function as unbounded memory by purely spatial means. ∎ 5. Direct universality via a writable tape-path in the map The second construction makes the simulation more direct. Instead of encoding memory arithmetically as distances of markers from the origin, it places writable labels on landmarks along a distinguished bi-infinite path through the allocentric map. The current simulated location plays the role of the Turing head, and movement along the path plays the role of left and right head motion. In effect, this construction is an isomorphic recoding of an ordinary one-tape Turing machine into allocentric-map terms: the path realizes the tape, the current simulated location realizes the head position, and the stored labels on path landmarks realize the tape contents. Definition 5.1 (Tape-path allocentric navigation machine). A tape-path allocentric navigation machine has an internal map \(\:{\mathbb{Z}}^{2}\) , a writable landmark-labeling function $$\:\lambda\::{\mathbb{Z}}^{2}\to\:{\Gamma\:},$$ a distinguished bi-infinite path $$\:\pi\::\mathbb{Z}\to\:{\mathbb{Z}}^{2},$$ a finite control set \(\:Q\) , and a current simulated location constrained to lie on the path. In one computational step the machine checks the stored label at the current path location, updates that label, changes control state, and moves to the predecessor or successor location on the path. Theorem 5.2 For every deterministic one-tape Turing machine \(\:M\) , there exists a tape-path allocentric navigation machine \(\:{A}_{M}\:\) that simulates \(\:M\:\) exactly, step for step. Consequently, the class of tape-path allocentric navigation machines is Turing universal. Proof Let $$\:M=(Q,{\Gamma\:},\square\:,{q}_{0},{q}_{h},\delta\:)$$ be a deterministic one-tape Turing machine. Build \(\:{A}_{M}\:\) with the same finite control states, the same tape alphabet, and the same transition table. This is essentially an isomorphic recoding of \(\:M\) : no new computational resources are introduced beyond a spatial redescription of the tape and head. Represent tape cell \(\:i\:\) by the path location \(\:\pi\:\left(i\right)\) . Represent the Turing head position \(\:h\:\) by the current simulated location \(\:\pi\:\left(h\right)\) . Represent the tape content function \(\:t\) by storing the label \(\:t\left(i\right)\:\) at landmark \(\:\pi\:\left(i\right)\) . Thus encode a Turing configuration \(\:(q,\:h,\:t)\:\) by $$\:E(q,h,t)=(q,\pi\:(h),{\lambda\:}_{t}),$$ where \(\:{\lambda\:}_{t}\left(\pi\:\left(i\right)\right)=t\left(i\right)\:\) for every integer \(\:i\) and all non-path locations are blank. Now take one Turing step from \(\:C=(q,h,t)\) . Let \(\:a=t\left(h\right)\) , and suppose $$\:\delta\:(q,a)=({q}^{{\prime\:}},b,D).$$ The Turing successor configuration is \(\:{C}^{{\prime\:}}=({q}^{{\prime\:}},{h}^{{\prime\:}},{t}^{{\prime\:}})\) , where \(\:{t}^{{\prime\:}}\) differs from \(\:t\:\) only in writing \(\:b\:\) at cell \(\:h\) , and \(\:{h}^{{\prime\:}}=h-1\:\) if \(\:D=L\:\) or \(\:{h}^{{\prime\:}}=h+1\:\) if \(\:D=R\) . In the encoded navigation configuration, the current location is \(\:\pi\:\left(h\right)\:\) and the current label is \(\:a\) . The encoded transition rule writes \(\:b\:\) at \(\:\pi\:\left(h\right)\) , changes state to \(\:{q}^{{\prime\:}}\) , and moves to \(\:\pi\:\left(h-1\right)\:\) or \(\:\pi\:\left(h+1\right)\:\) according to \(\:D\) . Therefore, the resulting navigation configuration is exactly \(\:E\left({C}^{{\prime\:}}\right)\) . Induction on run length yields a full step-for-step simulation. Every run of \(\:M\:\) is mirrored by a run of \(\:{A}_{M}\:\) that preserves the control state, the complete tape contents, the head location, and halting behavior at every stage. Hence \(\:{A}_{M}\:\) computes the same partial function as \(\:M\) . Because ordinary one-tape Turing machines are universal, the tape-path architecture is Turing universal. Relative to the first proof, this construction is more direct and conceptually closer to standard Turing-machine organization. Relative to older graph-based formalisms, however, it remains a familiar kind of tape-on-graph encoding. ∎ 6. Direct universality via a fully local two-dimensional landmark layout The third construction removes the globally designated path from the machine’s operative resources. Memory is realized as a two-dimensional field of landmarks, and the machine moves only by following local predecessor/successor information available at the landmark currently occupied by the simulated head. Equivalently, the construction gives a local two-dimensional embedding of a linear Turing tape into a zigzag track in the allocentric map: the machine itself accesses only local predecessor/successor cues, while the linear order appears only in the metatheory. Definition 6.1 (Local-layout allocentric navigation machine). Let the internal map be \(\:{\mathbb{Z}}^{2}\) , and let the memory landmarks occupy the two-row track $$\:T\:=\:\left\{\right(x,y)\mathbb{\:}\in\:\mathbb{\:}\mathbb{Z}²\mathbb{\:}|\mathbb{\:}y\:\in\:\:\left\{\text{0,1}\right\}\}.$$ The landmarks are arranged in a zigzag chain through the plane: $$\:\cdots\:\to\:(-\text{2,0})\to\:(-\text{2,1})\to\:(-\text{1,1})\to\:(-\text{1,0})\to\:\left(\text{0,0}\right)\to\:\left(\text{0,1}\right)\to\:\left(\text{1,1}\right)\to\:\left(\text{1,0}\right)\to\:\left(\text{2,0}\right)\to\:\cdots\:\text{\hspace{0.17em}}.$$ Each landmark stores a writable label from \(\:{\Gamma\:}\) , a head marker indicating whether the simulated head is currently there, and a fixed local landmark type determining only two local directions: predecessor and successor. The machine has no access to any global index over the chain. Definition 6.2 (The four local landmark types). Type A landmarks occur at \(\:(2k,\:0)\) and point west as predecessor and north as successor. Type B landmarks occur at (2 k , 1) \(\:\:\) and point south as predecessor and east as successor. Type C landmarks occur at \(\:\left(2k+1,\:1\right)\:\) and point west as predecessor and south as successor. Type D landmarks occur at \(\:\left(2k+1,\:0\right)\:\) and point north as predecessor and east as successor. These local arrows are the only navigation data available to the machine. Lemma 6.3 There exists a bijection $$\:\eta\::\mathbb{Z}\to\:T$$ such that following the local successor pointer from \(\:\eta\:\left(i\right)\:\) reaches \(\:\eta\:(i+1)\) , while following the local predecessor pointer from \(\:\eta\:\left(i\right)\:\) reaches \(\:\eta\:(i-1)\) . Proof Define \(\:\eta\:\:\) by listing the zigzag in order: \(\:\eta\:\left(4k\right)=\left(2k,0\right),\:\:\eta\:(4k+1)=(2k,1),\) \(\:\eta\:\left(4k+2\right)=\left(2k+1,\:1\right),\:\:\eta\:(4k+3)=(2k+1,\:0).\) The successor and predecessor claims are then verified case by case from the four landmark types. From a type A landmark, successor is north; from B, east; from C, south; from D, east. The predecessor directions are the corresponding reverses. Hence predecessor and successor along the local arrows coincide exactly with decrement and increment of the hidden index \(\:i\) . The bijection \(\:\eta\:\:\) is used only in the metatheory to prove correctness; it is not available to the machine itself. ∎ Theorem 6.4 For every deterministic one-tape Turing machine \(\:M\) , there exists a local-layout allocentric navigation machine \(\:{A}_{M}\) that simulates \(\:M\:\) exactly, step for step. Consequently, the class of local-layout allocentric navigation machines is Turing universal. Proof Let $$\:M=(Q,{\Gamma\:},\square\:,{q}_{0},{q}_{h},\delta\:)$$ be a deterministic one-tape Turing machine. Build \(\:{A}_{M}\) with the same finite control set and the same transition table. Thus, the linear tape of \(\:M\:\) is embedded into the two-dimensional track \(\:T\:\) in such a way that the machine follows only local predecessor/successor structure; the indexing \(\:\eta\:\) is used only to prove that this local structure recovers the usual left/right tape dynamics. If $$\:\delta\:(q,a)=({q}^{{\prime\:}},b,L),$$ then \(\:{A}_{M}\) , when in state \(\:q\:\) at a landmark storing \(\:a\) , writes \(\:b\) , changes state to \(\:{q}^{{\prime\:}}\) , and moves the head marker to the locally designated predecessor landmark. If $$\:\delta\:(q,a)=({q}^{{\prime\:}},b,R),$$ it writes \(\:b\) , changes state to \(\:{q}^{{\prime\:}}\) , and moves to the locally designated successor landmark instead. Encode a Turing configuration \(\:(q,\:h,\:t)\:\) by $$\:E(q,h,t)=(q,{\lambda\:}_{t},\eta\:(h\left)\right),$$ where \(\:{\lambda\:}_{t}\left(\eta\:\right(i\left)\right)=t\left(i\right)\) for each integer \(\:i\) . Thus, tape cell \(\:i\) is represented by landmark \(\:\eta\:\left(i\right)\) , and the Turing head position \(\:h\) is represented by the unique head-marked landmark \(\:\eta\:\left(h\right)\) . Now take one Turing step from \(\:C=(q,h,t)\) . Let \(\:a=t\left(h\right)\) , and suppose $$\:\delta\:(q,a)=({q}^{{\prime\:}},b,D).$$ The Turing successor configuration is \(\:{C}^{{\prime\:}}=({q}^{{\prime\:}},{h}^{{\prime\:}},{t}^{{\prime\:}})\) , where \(\:{t}^{{\prime\:}}\) differs from \(\:t\) only in writing \(\:b\:\) at cell \(\:h\:\) and \(\:{h}^{{\prime\:}}=h-1\:\) if \(\:D=L\:\) or \(\:{h}^{{\prime\:}}=h+1\:\) if \(\:D=R\) . In the encoded navigation configuration, the current landmark is \(\:\eta\:\left(h\right)\) and the label stored there is \(\:a\) . The encoded local rule writes \(\:b\) , changes state to \(\:{q}^{{\prime\:}}\) , and moves the head marker by following the current landmark’s predecessor or successor pointer according to \(\:D\) . By Lemma 6.3 , this local move reaches \(\:\eta\:\left(h-1\right)\:\) in the left case and \(\:\eta\:\left(h+1\right)\:\) in the right case. Therefore, the resulting navigation configuration is exactly \(\:E\left({C}^{{\prime\:}}\right)\) . Induction on run length yields a full step-for-step simulation. Every run of \(\:M\:\) is mirrored by a run of \(\:{A}_{M}\:\) that preserves the control state, tape contents, head location, and halting behavior at every stage. Hence \(\:{A}_{M}\:\) computes the same partial function as \(\:M\) . Because ordinary one-tape Turing machines are universal, the local-layout architecture is Turing universal. This third proof is the most faithful to the idea of computation by internal navigation among landmarks because the operative resources of the machine are entirely local. In that respect it lies especially close, in mathematical spirit, to local graph-based machine models studied in computability theory, even though it is recast here in allocentric cognitive-map terms. ∎ While the proofs of Theorems 5.2 and 6.4 assign locations within a cognitive map formal roles corresponding to entries in the tape alphabet \(\:{\Gamma\:}\) , this should not be taken to imply that allocentric navigation requires “symbols” in any language-like sense. Letters of a finite alphabet are just uninterpreted labels. Nothing in the universality proofs depends on the stored items in the map being symbolic in any richer sense. To make this explicit, let \(\:O\:\) be a finite set of reliably distinguishable stored item-types, and let $$\:\rho\::O\to\:{\Gamma\:}$$ be a fixed bijection onto the tape alphabet \(\:{\Gamma\:}\) . Each relevant location in the allocentric map stores an item of type \(\:o\in\:O\) , and this item realizes the tape letter \(\:\rho\:\left(o\right)\) . Thus, rather than assuming that the map literally stores elements of \(\:{\Gamma\:}\) , we may assume that it stores one of finitely many reliably distinguishable item-types. The universality proofs go through unchanged. 7. Comparative significance The three theorems establish the same computability-theoretic conclusion while differing in how they apply navigation-based processing. The counter proof is the most austere. It uses a two-dimensional map essentially, because the x - and y -axes encode different unbounded stores, yet its memory is encoded purely by spatial location. This makes the proof conceptually economical. The tape-path proof is more direct. In fact, it is essentially an isomorphic recoding of an ordinary one-tape Turing machine into an allocentric cognitive map. If a navigation architecture can maintain a track of landmarks with replaceable stored items and move a simulated location along that track, then the standard Turing model is already present almost verbatim. The advantage is interpretive clarity: landmarks are memory cells, their stored items are tape entries, and navigation is head movement. Within cognitive maps, those items may be interpreted as information associated with objects or features at landmarks. The disadvantage is that the architecture still presupposes a globally distinguished path whose adjacency relations are simply handed to the machine. The local-layout proof is more local and spatially natural. It may be viewed as a local two-dimensional embedding of a linear Turing tape into a field of landmarks. The memory is realized as a genuinely two-dimensional field of landmarks, and the machine moves only by inspecting local directional cues at its present position. The hidden indexing used in the proof exists only at the meta-level to establish correctness. Thus, the operative resources of the machine are fully local even though the proof uses a global enumeration for convenience. The mathematical content of these constructions is similar to earlier work on graph-based computation and locally rewritable memory. Kolmogorov-Uspensky machines and storage-modification machines already show that graph-structured memory plus local operations can realize universal computation. Graph Turing machines show that Turing computation can be reproduced inside labeled graphs. Graph-walking automata and exploration models show how navigation itself becomes a computational lens, while also revealing that navigation without sufficient writable memory is too weak. Against that background, the present proofs are a reconstruction of those results within a framework motivated by empirical work on neurocognitive architecture. This reconstruction makes clear that computational universality is not tied to any particular representational format, but can arise within a variety of structured systems, including those based on spatial organization and local interaction. The present contribution is therefore about the representational and computational power of allocentric navigation, particularly the kind of offline navigation that might underlie many cognitive functions. These universality results make explicit how standard computability-theoretic constructions can be reinterpreted inside a navigation-based allocentric-map architecture that relies on representational and computational resources independently studied in neuroscience. The full universal machines proved here remain heavily idealized, but the allocentric-map vocabulary is anchored in the mainstream empirical literature on spatial coding and cognitive maps. From this perspective, the results may be seen not merely as demonstrations of sufficiency, but as clarification of the structural resources already present in allocentric navigation architectures. Such systems involve storage at landmarks, locally defined transitions between states, and structured spatial organization. Once these elements are in place, the capacity for universal computation follows. The present constructions therefore make explicit what is already implicit in these architectures: that structured spatial organization, together with local update rules, is sufficient to support arbitrarily complex computable transformations. This has direct implications for the claim that navigation-based or otherwise nonclassical architectures lack sufficient representational or computational power to support cognition. This sort of objection appears to depend on an additional assumption, namely that adequate representation must take a symbolic, language-like form. The results developed here undermine that assumption and flip the script. They show that systems grounded in structured spatial relations and local transition rules can realize the same class of computable transformations typically associated with symbolic architectures. Accordingly, symbolic processing could be understood as a special case of spatial navigation, where symbols are items represented at locations within a cognitive map and symbolic operations are actions taken on such items. Developing this suggestion in detail is a research program to be pursued in future work. 8. Limitations and scope These universality theorems require standard idealizations. They assume an unbounded allocentric map, perfectly reliable landmark identity, exact storage, exact local movement, and arbitrarily long navigation. None of those assumptions should be attributed to biological systems. These results therefore do not establish that animals, humans, or hippocampal-entorhinal systems literally implement Turing-universal navigation machines. They establish only that allocentric navigation-based architectures, if idealized in the usual way familiar from computability theory, are computationally universal. The evidence from neuroscience supports allocentric spatial representation, place and grid coding, and map-like navigation capacities, including offline navigation. It does not by itself support the stronger assumptions required for universal computation, such as exact unbounded writable memory at landmarks. The contribution is thus a formal reconstruction that begins from an empirically motivated representational vocabulary and then idealizes it into a universal machine model. The theorems also do not show that every navigation architecture is universal. Universality depends on specific structural enrichments: unbounded storage, reliable update operations, and sufficiently precise control. A purely finite navigation system, or a system lacking sufficiently stable memory, could not be strictly universal. That said, the navigation and action processes discussed here may also occur partly within the external environment, which under suitable idealization may be treated as an unbounded memory store. In that case, the same type of universality construction can be realized by an allocentric navigation architecture that uses environmental as well as internal storage. This suggests how cognitive maps may help explain calculations performed by humans on paper or other external media. 9. Conclusion This article has presented three formal routes from allocentric cognitive-map architectures to computational universality. The first uses two-dimensional spatial position to encode counter values. The second turns a distinguished path of writable landmarks into a direct analogue of a Turing tape. The third replaces that global path with a fully local two-dimensional layout whose predecessor and successor relations are available only through local landmark structure. These results are mathematically continuous with earlier work on graph-based computation, but they make explicit how universal computational capacity can be reconstructed within the framework of navigation within allocentric cognitive maps. In that way, they clarify the representational and computational significance of a class of architectures that are independently motivated by empirical work in neuroscience. None of this is to say that biological navigation literally implements classical Turing-style computation. On the contrary, the point is that, if allocentric navigation—which is normally nonclassical in most respects—is expressive enough to implement classical Turing computation, it may be expressive enough to explain cognition nonclassically (cf. Piccinini, 2025 ). That is enough to motivate a research program in which higher cognition, including symbolic processing, is reconstructed in map-based terms. Declarations Competing Interests . No funding was received for conducting this study. The authors has no relevant financial or non-financial interests to disclose. Author Contribution I used generative AI (ChatGPT 5.4 Thinking and Pro and Google Gemini 3.1 Pro) to help with research assistance, proof writing and checking, and draft feedback. All substantive ideas, arguments, interpretations, source selection, and final wording are my own and were reviewed and approved by me. I take full responsibility for the work. Acknowledgement This work was partially done on the land of the Osage Nation, Otae-Missouri, Chikasaw, Illni, Ioway, Quapaw, Shawnee, Delaware, Kickapoo, Sac & Fox, Omaha, and Santee Sioux. I thank Carl Sachs for recently reminding me of Wells’s (2006) work, which may have helped inspire this project. Martínez (2025) may also have been a source of inspiration. Thanks to Jeff Dauer, Pawel Pachniewski, Waldemar Rohloff, and Stephen Selesnick for helpful feedback on the manuscript. References Ackerman, N.L., Freer, C.E.: Graph Turing machines. In J. Kennedy and R. J. G. B. de Queiroz (Eds.), Logic, Language, Information, and Computation (Lecture Notes in Computer Science, Vol. 10388, pp. 1–13). Springer. (2017). https://doi.org/10.1007/978-3-662-55386-2_1 Basu, J., Nagel, K.I.: Neural circuits for goal-directed navigation across species. Trends Neurosci. 47 (11), 904–917 (2024). https://doi.org/10.1016/j.tins.2024.09.005 Behrens, T.E.J., Muller, T.H., Whittington, J.C.R., Mark, S., Baram, A.B., Stachenfeld, K.L., Kurth-Nelson, Z.: What is a cognitive map? Organizing knowledge for flexible behavior. Neuron. 100 (2), 490–509 (2018). https://doi.org/10.1016/j.neuron.2018.10.002 Carr, M.F., Jadhav, S.P., Frank, L.M.: Hippocampal replay in the awake state: A potential substrate for memory consolidation and retrieval. Nat. Neurosci. 14 (2), 147–153 (2011). https://doi.org/10.1038/nn.2732 Courellis, H.S., Minxha, J., Cardenas, A.R., Kimmel, D.L., Reed, C.M., Valiante, T.A., Salzman, C.D., Mamelak, A.N., Fusi, S., Rutishauser, U.: Abstract representations emerge in human hippocampal neurons during inference. Nature. 632 (8026), 841–849 (2024). https://doi.org/10.1038/s41586-024-07799-x Dragoi, G., Tonegawa, S.: Preplay of future place cell sequences by hippocampal cellular assemblies. Nature. 469 (7330), 397–401 (2011). https://doi.org/10.1038/nature09633 Dudenhefner, A.: Certified decision procedures for two-counter machines. In A. P. Felty (Ed.), 7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022) (Leibniz International Proceedings in Informatics [LIPIcs], Vol. 228, Article 16, p. 16:1–16:18). Schloss Dagstuhl—Leibniz-Zentrum fuer Informatik. (2022). https://doi.org/10.4230/LIPIcs.FSCD.2022.16 Epstein, R.A., Patai, E.Z., Julian, J.B., Spiers, H.J.: The cognitive map in humans: Spatial navigation and beyond. Nat. Neurosci. 20 (11), 1504–1513 (2017). https://doi.org/10.1038/nn.4656 Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph exploration by a finite automaton. Theor. Comput. Sci. 345 (2–3), 331–344 (2005). https://doi.org/10.1016/j.tcs.2005.07.014 Fodor, J.A., Pylyshyn, Z.W.: Connectionism and cognitive architecture: A critical analysis. Cognition. 28 (1–2), 3–71 (1988). https://doi.org/10.1016/0010-0277(88)90031-5 Gallistel, C.R., King, A.P.: Memory and the computational brain: Why cognitive science will transform neuroscience. Wiley (2009) Kolmogorov, A.N., Uspensky, V.A.: On the definition of an algorithm. Am. Math. Soc. Translations: Ser. 2 , 217–245 (1963). (Original work published 1958) Krakauer, J.W., Ramsey, W.: Mental representation without neural representation: Understanding the evidence. Philos. Mind Sci., 7 (1). (2026) Martínez, M.: Structural representation as complexity management. In: Neurocognitive foundations of mind, pp. 120–143. Routledge (2025) Minsky, M.L.: Computation: Finite and infinite machines. Prentice-Hall (1967) Moser, E.I., Kropff, E., Moser, M.-B.: Place cells, grid cells, and the brain's spatial representation system. Annu. Rev. Neurosci. 31 , 69–89 (2008). https://doi.org/10.1146/annurev.neuro.31.061307.090723 O'Keefe, J., Dostrovsky, J.: The hippocampus as a spatial map: Preliminary evidence from unit activity in the freely-moving rat. Brain Res. 34 (1), 171–175 (1971). https://doi.org/10.1016/0006-8993(71)90358-1 O'Keefe, J., Nadel, L.: The hippocampus as a cognitive map. Oxford University Press (1978) Okhotin, A.: Graph-walking automata: From whence they come, and whither they are bound. In M. Hospodar & G. Jiraskova (Eds.), Implementation and Application of Automata (Lecture Notes in Computer Science, Vol. 11601, pp. 10–29). Springer. (2019). https://doi.org/10.1007/978-3-030-23679-3_2 Piccinini, G.: Neural hardware for the language of thought: New rules for an old game. arXiv:2510.10251 (2025) Schönhage, A.: Storage modification machines. SIAM J. Comput. 9 (3), 490–508 (1980). https://doi.org/10.1137/0209036 Shepherdson, J.C., Sturgis, H.E.: Computability of recursive functions. J. ACM. 10 (2), 217–255 (1963). https://doi.org/10.1145/321160.321170 Turing, A.M.: On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, s2-42 (1), 230–265. (1937). https://doi.org/10.1112/plms/s2-42.1.230 Wells, A.: Rethinking cognitive computation: Turing and the science of the mind. Macmillan (2006) Whittington, J.C.R., McCaffary, D., Bakermans, J.J.W., Behrens, T.E.J.: How to build a cognitive map. Nat. Neurosci. 25 (10), 1257–1272 (2022). https://doi.org/10.1038/s41593-022-01153-y Wikenheiser, A.M., Schoenbaum, G.: Over the river, through the woods: Cognitive maps in the hippocampus and orbitofrontal cortex. Nat. Rev. Neurosci. 17 (8), 513–523 (2016). https://doi.org/10.1038/nrn.2016.56 Additional Declarations No competing interests reported. Cite Share Download PDF Status: Under Review Version 1 posted Reviews received at journal 13 May, 2026 Reviews received at journal 30 Apr, 2026 Reviewers agreed at journal 22 Apr, 2026 Reviewers agreed at journal 06 Apr, 2026 Reviewers invited by journal 06 Apr, 2026 Editor assigned by journal 06 Apr, 2026 Submission checks completed at journal 06 Apr, 2026 First submitted to journal 02 Apr, 2026 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-9307584","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":619837477,"identity":"19254372-2b10-4b87-b21f-4753992542e1","order_by":0,"name":"Gualtiero Piccinini","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA8ElEQVRIiWNgGAWjYDACZiBOYJBgYGNgPoAkzEaUFrYEsAAPQS0IwGNAnBZzduaHHx7usMjj41/zTerGn8P29uzdCQwfyg7j1GLZzGYskXhGophN4u026dy2w4k9PGc3MM44h1uLwWEeNobENgkgOgvU0nA4gUcidwMzbxtRWs48k84BOoxH/u0G5r9EaeHvYZPOYTvM2CPBu4GZEY8WiF/AtrAZW+e2pSf2nMndcLDnXDpOLeb8hx9+/NlWlzi///DD2zl/rO3Z289ufPCjzBq3w+AsiQQQ2QxmH8CpHkULP1hdHT7Fo2AUjIJRMEIBACBnUvqu75z+AAAAAElFTkSuQmCC","orcid":"","institution":"University of Missouri","correspondingAuthor":true,"prefix":"","firstName":"Gualtiero","middleName":"","lastName":"Piccinini","suffix":""}],"badges":[],"createdAt":"2026-04-03 01:23:12","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-9307584/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-9307584/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":106727250,"identity":"abcd903d-a7eb-4ec8-970f-1489385ec91c","added_by":"auto","created_at":"2026-04-12 18:38:27","extension":"pdf","order_by":0,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":753732,"visible":true,"origin":"","legend":"","description":"","filename":"manuscript.pdf","url":"https://assets-eu.researchsquare.com/files/rs-9307584/v1/aa341c97-32b3-4419-ba2b-46f2d84e096b.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Navigation within Allocentric Cognitive Maps is Computationally Universal","fulltext":[{"header":"1. Introduction","content":"\u003cp\u003eThis article proves three sufficiency theorems showing that idealized navigation-based architectures with allocentric maps and landmark structure can be computationally universal. The underlying mathematical ideas are close to classical results from computability theory, especially work on counter machines, graph-based machines, and locally navigable memory structures. The present contribution is to reconstruct those ideas explicitly in the framework of navigation within allocentric cognitive maps, that is, within a type of computational architecture that is independently motivated by empirical and theoretical work in neuroscience. This shows how established universality constructions can be reformulated inside an allocentric navigation-based architecture.\u003c/p\u003e \u003cp\u003eIn contemporary neuroscience, allocentric cognitive maps are widely discussed representational and computational structures that organize knowledge relative to stable environmental features rather than momentary egocentric position (Behrens et al., \u003cspan citationid=\"CR3\" class=\"CitationRef\"\u003e2018\u003c/span\u003e; Epstein et al., \u003cspan citationid=\"CR8\" class=\"CitationRef\"\u003e2017\u003c/span\u003e; O\u0026rsquo;Keefe \u0026amp; Nadel, 1978). Many animals use allocentric, landmark-anchored spatial representations in navigation (Basu \u0026amp; Nagel, \u003cspan citationid=\"CR2\" class=\"CitationRef\"\u003e2024\u003c/span\u003e). In mammals, hippocampal activity can replay previously experienced trajectories and, in some cases, preplay trajectories later expressed during navigation (Carr et al., \u003cspan citationid=\"CR4\" class=\"CitationRef\"\u003e2011\u003c/span\u003e; Dragoi \u0026amp; Tonegawa, \u003cspan citationid=\"CR6\" class=\"CitationRef\"\u003e2011\u003c/span\u003e). There is increasing evidence that hippocampal-entorhinal cognitive maps support functions beyond navigation, including memory, inference, and abstract relational knowledge, and that related map-like representations are present in other brain regions (Courellis et al., \u003cspan citationid=\"CR5\" class=\"CitationRef\"\u003e2024\u003c/span\u003e; Whittington et al., \u003cspan citationid=\"CR25\" class=\"CitationRef\"\u003e2022\u003c/span\u003e; Wikenheiser \u0026amp; Schoenbaum, \u003cspan citationid=\"CR26\" class=\"CitationRef\"\u003e2016\u003c/span\u003e). This evidence raises the question of what representational and computational power cognitive maps possess.\u003c/p\u003e \u003cp\u003eThis article makes precise and proves a family of claims of the following form: an architecture that represents space in an allocentric coordinate system, represents landmarks at locations within that system, stores information at landmarks, can internally simulate navigation among those landmarks, and can internally simulate performing operations at those landmarks can compute any Turing-computable function under idealizations that are standard in computability theory.\u003c/p\u003e \u003cp\u003eWhile the primary target of this article is the representational and computational power of architectures capable of internally simulating navigation and action within cognitive maps, \u003cem\u003eoffline\u003c/em\u003e simulation is not necessary for the universality results to obtain. The sort of allocentric navigation investigated in this article may be entirely simulated in an animal\u0026rsquo;s head or it may occur partly or wholly within the animal\u0026rsquo;s environment. The extent to which navigation occurs online or offline makes a difference to how cognitively demanding the task is, because keeping track of all the needed information in one\u0026rsquo;s head requires more cognitive resources than storing some of that information in the environment. For the purposes of the universality results, however, that difference is immaterial so long as the same operations are available.\u003c/p\u003e \u003cp\u003eThe benchmark is Turing universality in the standard sense established by Turing's analysis of effective calculability (Turing, \u003cspan citationid=\"CR23\" class=\"CitationRef\"\u003e1937\u003c/span\u003e). A convenient auxiliary benchmark is universality via counter or register machines, especially the simple two-counter models associated with Minsky and related register-machine formalisms (Dudenhefner, \u003cspan citationid=\"CR7\" class=\"CitationRef\"\u003e2022\u003c/span\u003e; Minsky, \u003cspan citationid=\"CR15\" class=\"CitationRef\"\u003e1967\u003c/span\u003e; Shepherdson \u0026amp; Sturgis, \u003cspan citationid=\"CR22\" class=\"CitationRef\"\u003e1963\u003c/span\u003e). The first proof simulates two-counter machines by using two movable markers on the coordinate axes to encode unbounded counters. The second proof simulates standard one-tape Turing machines by embedding a writable tape-path in the allocentric map. The third proof is the most local: it still simulates ordinary Turing machines directly, but it dispenses with any globally indexed path available to the machine itself and uses only local directional information at neighboring landmarks.\u003c/p\u003e \u003cp\u003eThe constructions are mathematically close to several classical graph-based machine models. Accordingly, the bare universality results are mathematically unsurprising. What is new here, as far as I know, is the explicit reconstruction of those results inside a navigation-based allocentric-map architecture of a kind that is independently motivated by cognitive neuroscience. The significance of this contribution is architectural and interdisciplinary: it shows that an architecture often associated primarily with spatial navigation can, under standard idealizations, realize universal computation.\u003c/p\u003e \u003cp\u003eThis conclusion bears on a line of criticism according to which nonclassical architectures uncovered by mainstream neuroscience, including cognitive maps, lack sufficient representational or computational power to explain cognition, and so additional classical \u0026ldquo;symbolic\u0026rdquo; Turing- or von Neumann-style architectures must be posited and invoked instead (e.g., Fodor \u0026amp; Pylyhyn, 1988; Gallistel \u0026amp; King, \u003cspan citationid=\"CR11\" class=\"CitationRef\"\u003e2009\u003c/span\u003e). It also bears on arguments that neural states count as representations only if they play a computational role (Krakauer \u0026amp; Ramsey, \u003cspan citationid=\"CR13\" class=\"CitationRef\"\u003e2026\u003c/span\u003e). The present results show that navigation-based architectures have sufficient representational and computational power in principle. Under idealizations routinely adopted in computability theory, such architectures suffice for Turing universality. This entails that such architectures can, in principle, realize arbitrarily complex computable transformations, including transformations with the kinds of productivity, systematicity, and compositionality often taken to require a classical symbolic architecture.\u003c/p\u003e \u003cp\u003eThis, in turn, opens the possibility of explaining higher cognition, including symbolic processing, in terms of cognitive map-based computation. Cognitive maps do not normally store and process symbols in any linguistic or language-like sense. What they store is information about the allocentric relations among locations, landmarks, and other items located within the map, together with operations that may be performed on such items. The present results show that those resources are sufficient for universal computation. Symbolic processing therefore need not be treated as architecturally basic but may instead be reconstrued in terms of map-like resources already known to exist in the brain.\u003c/p\u003e \u003cp\u003eAt the same time, I do not argue that any biological system literally implements a Turing machine or any other classical computing device, whether universal or otherwise. Nor do I imply that implementing classical Turing-style computation within cognitive maps is required to explain cognition. The point is, rather, that a computational architecture often seen as capable at best of allegedly \u0026ldquo;low-level\u0026rdquo; cognitive tasks such as navigation, or perhaps too weak even for navigation without the support of allegedly more powerful symbolic architectures (e.g., Gallistel \u0026amp; King, \u003cspan citationid=\"CR11\" class=\"CitationRef\"\u003e2009\u003c/span\u003e) can, under standard idealizations, support universal computation. To that extent, cognitive map-based architectures are rich enough in principle to realize any computable cognitive function. Whether they in fact explain cognition, and if so whether they do it by classical or nonclassical means, is a separate empirical question.\u003c/p\u003e \u003cp\u003eThe remainder of this article proceeds as follows: Section \u003cspan refid=\"Sec2\" class=\"InternalRef\"\u003e2\u003c/span\u003e outlines historical antecedents, Section \u003cspan refid=\"Sec3\" class=\"InternalRef\"\u003e3\u003c/span\u003e provides formal preliminaries, Sections \u003cspan refid=\"Sec4\" class=\"InternalRef\"\u003e4\u003c/span\u003e through \u003cspan refid=\"Sec6\" class=\"InternalRef\"\u003e6\u003c/span\u003e present the three proofs of universality, Section \u003cspan refid=\"Sec7\" class=\"InternalRef\"\u003e7\u003c/span\u003e discusses the significance of the proofs, Section \u003cspan refid=\"Sec8\" class=\"InternalRef\"\u003e8\u003c/span\u003e discusses the proofs\u0026rsquo; scope, and Section \u003cspan refid=\"Sec9\" class=\"InternalRef\"\u003e9\u003c/span\u003e concludes.\u003c/p\u003e"},{"header":"2. Historical background","content":"\u003cp\u003eWhile the motivation for the present results stems from reflections on the relation between allocentric cognitive maps and computational universality, the proofs have historical antecedents within computability theory (Table\u0026nbsp;\u003cspan refid=\"Tab1\" class=\"InternalRef\"\u003e1\u003c/span\u003e). The most relevant computability-theoretic predecessors are graph-based machines in which memory is not a linear tape but a mutable or navigable graph with a distinguished active location. The oldest example is Kolmogorov and Uspensky\u0026rsquo;s graph-based conception of algorithmic computation. In this model, machines operate locally on graph-structured memory, and the resulting class of machines computes all partial recursive functions (Kolmogorov \u0026amp; Uspensky, 1958/1963).\u003c/p\u003e \u003cp\u003eA second close predecessor is Sch\u0026ouml;nhage's storage-modification machine. Here memory is represented by a mutable directed graph and computation proceeds by local pointer manipulations around an active node. This is mathematically very close to a navigation-based architecture in which an agent accesses and updates memory through local moves among landmarks (Sch\u0026ouml;nhage, \u003cspan citationid=\"CR21\" class=\"CitationRef\"\u003e1980\u003c/span\u003e).\u003c/p\u003e \u003cp\u003eA third close family is provided by graph Turing machines. Ackerman and Freer formulate computation on vertex-labeled, edge-colored graphs and explicitly prove that ordinary Turing computation can be recovered inside that framework. Their model differs from the present one in being designed first and foremost as a graph-computation formalism rather than as a cognitive-map architecture, but it is plainly relevant for any claim that graph-like spatial organization plus local rules can support universality (Ackerman \u0026amp; Freer, \u003cspan citationid=\"CR1\" class=\"CitationRef\"\u003e2017\u003c/span\u003e).\u003c/p\u003e \u003cp\u003eThere is also a neighboring literature on graph-walking automata and graph exploration. This work is relevant because it treats movement through a graph as a computational primitive and analyzes how much can be achieved when an automaton navigates an environment using only local information. At the same time, this literature is useful as a cautionary contrast: finite-state navigation by itself is generally not universal unless one adds unbounded memory resources (Fraigniaud et al., \u003cspan citationid=\"CR9\" class=\"CitationRef\"\u003e2005\u003c/span\u003e; Okhotin, \u003cspan citationid=\"CR19\" class=\"CitationRef\"\u003e2019\u003c/span\u003e).\u003c/p\u003e \u003cp\u003eOn the neurocognitive side, the allocentric-map framework used in this article is motivated by a large literature on hippocampal and entorhinal representations. The original cognitive-map program of O'Keefe and Nadel was linked to place-cell evidence, and subsequent work on place cells, grid cells, boundary cells, head-direction cells, and related systems has made allocentric spatial coding a central part of contemporary theories of navigation and memory (Behrens et al., \u003cspan citationid=\"CR3\" class=\"CitationRef\"\u003e2018\u003c/span\u003e; Moser et al., \u003cspan citationid=\"CR16\" class=\"CitationRef\"\u003e2008\u003c/span\u003e; O'Keefe \u0026amp; Dostrovsky, \u003cspan citationid=\"CR17\" class=\"CitationRef\"\u003e1971\u003c/span\u003e; O'Keefe \u0026amp; Nadel, \u003cspan citationid=\"CR18\" class=\"CitationRef\"\u003e1978\u003c/span\u003e).\u003c/p\u003e \u003cp\u003eAs far as I have been able to determine, no prior source makes universality arguments explicit in the distinctive vocabulary of allocentric coordinates, landmarks, and navigation while simultaneously situating the architecture within the empirical cognitive-map literature. In this respect the results are mathematically unsurprising but conceptually novel and theoretically significant for the mind sciences.\u003c/p\u003e \u003cp\u003e \u003cdiv class=\"gridtable\"\u003e\u003ctable float=\"Yes\" id=\"Tab1\" border=\"1\"\u003e \u003ccaption language=\"En\"\u003e \u003cdiv class=\"CaptionNumber\"\u003eTable 1\u003c/div\u003e \u003cdiv class=\"CaptionContent\"\u003e \u003cp\u003eOverview of the three constructions and their closest prior analogues.\u003c/p\u003e \u003c/div\u003e \u003c/caption\u003e \u003ccolgroup cols=\"5\"\u003e \u003cdiv align=\"left\" class=\"colspec\" colname=\"c1\" colnum=\"1\"\u003e\u003c/div\u003e \u003cdiv align=\"left\" class=\"colspec\" colname=\"c2\" colnum=\"2\"\u003e\u003c/div\u003e \u003cdiv align=\"left\" class=\"colspec\" colname=\"c3\" colnum=\"3\"\u003e\u003c/div\u003e \u003cdiv align=\"left\" class=\"colspec\" colname=\"c4\" colnum=\"4\"\u003e\u003c/div\u003e \u003cdiv align=\"left\" class=\"colspec\" colname=\"c5\" colnum=\"5\"\u003e\u003c/div\u003e \u003cthead\u003e \u003ctr\u003e \u003cth align=\"left\" colname=\"c1\"\u003e \u003cp\u003eConstruction\u003c/p\u003e \u003c/th\u003e \u003cth align=\"left\" colname=\"c2\"\u003e \u003cp\u003ePrimary memory encoding\u003c/p\u003e \u003c/th\u003e \u003cth align=\"left\" colname=\"c3\"\u003e \u003cp\u003eSimulation target\u003c/p\u003e \u003c/th\u003e \u003cth align=\"left\" colname=\"c4\"\u003e \u003cp\u003eClosest prior family\u003c/p\u003e \u003c/th\u003e \u003cth align=\"left\" colname=\"c5\"\u003e \u003cp\u003eMain significance\u003c/p\u003e \u003c/th\u003e \u003c/tr\u003e \u003c/thead\u003e \u003ctbody\u003e \u003ctr\u003e \u003ctd align=\"left\" colname=\"c1\"\u003e \u003cp\u003eCounter-map proof\u003c/p\u003e \u003c/td\u003e \u003ctd align=\"left\" colname=\"c2\"\u003e \u003cp\u003eTwo movable marker positions on orthogonal axes\u003c/p\u003e \u003c/td\u003e \u003ctd align=\"left\" colname=\"c3\"\u003e \u003cp\u003eTwo-counter machine\u003c/p\u003e \u003c/td\u003e \u003ctd align=\"left\" colname=\"c4\"\u003e \u003cp\u003eRegister/counter machines\u003c/p\u003e \u003c/td\u003e \u003ctd align=\"left\" colname=\"c5\"\u003e \u003cp\u003eShows that genuinely spatial position alone can encode unbounded memory\u003c/p\u003e \u003c/td\u003e \u003c/tr\u003e \u003ctr\u003e \u003ctd align=\"left\" colname=\"c1\"\u003e \u003cp\u003eTape-path proof\u003c/p\u003e \u003c/td\u003e \u003ctd align=\"left\" colname=\"c2\"\u003e \u003cp\u003eWritable labels on landmarks along a designated bi-infinite path\u003c/p\u003e \u003c/td\u003e \u003ctd align=\"left\" colname=\"c3\"\u003e \u003cp\u003eOrdinary one-tape Turing machine\u003c/p\u003e \u003c/td\u003e \u003ctd align=\"left\" colname=\"c4\"\u003e \u003cp\u003eGraph Turing machines / tape-on-graph models\u003c/p\u003e \u003c/td\u003e \u003ctd align=\"left\" colname=\"c5\"\u003e \u003cp\u003eDirectly identifies landmarks with memory cells\u003c/p\u003e \u003c/td\u003e \u003c/tr\u003e \u003ctr\u003e \u003ctd align=\"left\" colname=\"c1\"\u003e \u003cp\u003eLocal-layout proof\u003c/p\u003e \u003c/td\u003e \u003ctd align=\"left\" colname=\"c2\"\u003e \u003cp\u003eWritable labels plus only local predecessor/successor cues in a 2D field\u003c/p\u003e \u003c/td\u003e \u003ctd align=\"left\" colname=\"c3\"\u003e \u003cp\u003eOrdinary one-tape Turing machine\u003c/p\u003e \u003c/td\u003e \u003ctd align=\"left\" colname=\"c4\"\u003e \u003cp\u003eKolmogorov-Uspensky / SMM / local graph machines\u003c/p\u003e \u003c/td\u003e \u003ctd align=\"left\" colname=\"c5\"\u003e \u003cp\u003eMost faithful to navigation among landmarks using only local structure\u003c/p\u003e \u003c/td\u003e \u003c/tr\u003e \u003c/tbody\u003e \u003c/colgroup\u003e \u003c/table\u003e\u003c/div\u003e \u003c/p\u003e"},{"header":"3. Preliminaries","content":"\u003cp\u003e \u003cstrong\u003eDefinition 3.1\u003c/strong\u003e \u003cp\u003e \u003cb\u003e(Deterministic one-tape Turing machine).\u003c/b\u003e A deterministic one-tape Turing machine is a tuple\u003cdiv id=\"Equa\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equa\" name=\"EquationSource\"\u003e\n$$\\:M=(Q,{\\Gamma\\:},\\square\\:,{q}_{0},{q}_{h},\\delta\\:),$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003c/p\u003e \u003cp\u003ewhere \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:Q\\)\u003c/span\u003e\u003c/span\u003eis a finite set of states, \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\Gamma\\:}\\:\\)\u003c/span\u003e\u003c/span\u003eis a finite tape alphabet, \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\square\\:\\)\u003c/span\u003e\u003c/span\u003e is the distinguished blank symbol, \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{q}_{0}\\)\u003c/span\u003e\u003c/span\u003e is the start state, \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{q}_{h}\\:\\)\u003c/span\u003e\u003c/span\u003eis the halting state, and\u003cdiv id=\"Equb\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equb\" name=\"EquationSource\"\u003e\n$$\\:\\delta\\::(Q\\setminus\\:\\{{q}_{h}\\left\\}\\right)\\times\\:{\\Gamma\\:}\\to\\:Q\\times\\:{\\Gamma\\:}\\times\\:\\{L,R\\}$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003cp\u003eis the transition function. A configuration is a triple\u003cdiv id=\"Equc\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equc\" name=\"EquationSource\"\u003e\n$$\\:(q,h,t),$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003cp\u003ewhere \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:q\\in\\:Q\\:\\)\u003c/span\u003e\u003c/span\u003eis the current state, \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:h\\in\\:\\mathbb{Z}\\)\u003c/span\u003e\u003c/span\u003e is the head position, and\u003cdiv id=\"Equd\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equd\" name=\"EquationSource\"\u003e\n$$\\:t:\\mathbb{Z}\\to\\:{\\Gamma\\:}$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003cp\u003eis the tape-content function, with \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:t\\left(i\\right)=\\square\\:\\)\u003c/span\u003e\u003c/span\u003e for all but finitely many \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:i\\in\\:\\mathbb{Z}\\)\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e \u003cp\u003e \u003cstrong\u003eDefinition 3.2\u003c/strong\u003e \u003cp\u003e \u003cb\u003e(Deterministic two-counter machine).\u003c/b\u003e A deterministic two-counter machine consists of a finite set of instruction labels\u003cdiv id=\"Eque\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Eque\" name=\"EquationSource\"\u003e\n$$\\:L=\\{{\\mathcal{l}}_{0},{\\mathcal{l}}_{1},\\dots\\:,{\\mathcal{l}}_{m-1},{\\mathcal{l}}_{h}\\},$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003c/p\u003e \u003cp\u003etwo counters \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{c}_{1},{c}_{2}\\in\\:\\mathbb{N}\\)\u003c/span\u003e\u003c/span\u003e, and one instruction attached to each non-halting label. The permitted instruction forms are\u003cdiv id=\"Equf\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equf\" name=\"EquationSource\"\u003e\n$$\\:{\\text{I}\\text{n}\\text{c}}_{1}\\left({\\mathcal{l}}_{j}\\right),{\\:\\text{I}\\text{n}\\text{c}}_{2}\\left({\\mathcal{l}}_{j}\\right),{\\:\\text{J}\\text{Z}\\text{D}\\text{e}\\text{c}}_{1}({\\mathcal{l}}_{j},{\\mathcal{l}}_{k}),{\\:\\text{J}\\text{Z}\\text{D}\\text{e}\\text{c}}_{2}({\\mathcal{l}}_{j},{\\mathcal{l}}_{k}).$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003cp\u003eTheir operational semantics are as follows.\u003c/p\u003e \u003cp\u003e \u003cul\u003e \u003cli\u003e \u003cp\u003e \u003cspan class=\"InlineEquation\"\u003e \u003cspan class=\"mathinline\"\u003e\\(\\:{\\text{I}\\text{n}\\text{c}}_{1}\\left({\\mathcal{l}}_{j}\\right)\\)\u003c/span\u003e \u003c/span\u003e: replace \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{c}_{1}\\:\\)\u003c/span\u003e\u003c/span\u003eby \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{c}_{1}+1\\)\u003c/span\u003e\u003c/span\u003e and jump to \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\mathcal{l}}_{j}\\)\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e \u003c/li\u003e \u003cli\u003e \u003cp\u003e \u003cspan class=\"InlineEquation\"\u003e \u003cspan class=\"mathinline\"\u003e\\(\\:{\\text{I}\\text{n}\\text{c}}_{2}\\left({\\mathcal{l}}_{j}\\right)\\)\u003c/span\u003e \u003c/span\u003e: replace \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{c}_{2}\\)\u003c/span\u003e\u003c/span\u003e by \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{c}_{2}+1\\)\u003c/span\u003e\u003c/span\u003e and jump to \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\mathcal{l}}_{j}\\)\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e \u003c/li\u003e \u003cli\u003e \u003cp\u003e \u003cspan class=\"InlineEquation\"\u003e \u003cspan class=\"mathinline\"\u003e\\(\\:{\\text{J}\\text{Z}\\text{D}\\text{e}\\text{c}}_{1}({\\mathcal{l}}_{j},{\\mathcal{l}}_{k})\\)\u003c/span\u003e \u003c/span\u003e: if \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{c}_{1}=0\\)\u003c/span\u003e\u003c/span\u003e, jump to \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\mathcal{l}}_{j}\\)\u003c/span\u003e\u003c/span\u003e; otherwise replace \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{c}_{1}\\:\\)\u003c/span\u003e\u003c/span\u003eby \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{c}_{1}-1\\)\u003c/span\u003e\u003c/span\u003eand jump to \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\mathcal{l}}_{k}\\)\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e \u003c/li\u003e \u003cli\u003e \u003cp\u003e \u003cspan class=\"InlineEquation\"\u003e \u003cspan class=\"mathinline\"\u003e\\(\\:{\\text{J}\\text{Z}\\text{D}\\text{e}\\text{c}}_{2}({\\mathcal{l}}_{j},{\\mathcal{l}}_{k})\\)\u003c/span\u003e \u003c/span\u003e: if \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{c}_{2}=0\\)\u003c/span\u003e\u003c/span\u003e, jump to \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\mathcal{l}}_{j}\\)\u003c/span\u003e\u003c/span\u003e; otherwise replace \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{c}_{2}\\)\u003c/span\u003e\u003c/span\u003e by \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{c}_{2}-1\\)\u003c/span\u003e\u003c/span\u003eand jump to \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\mathcal{l}}_{k}\\)\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e \u003c/li\u003e \u003c/ul\u003e \u003c/p\u003e \u003cp\u003eA configuration is a triple (\u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\mathcal{l}}_{i},\\:m,\\:\\:n)\\)\u003c/span\u003e\u003c/span\u003e, where \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\mathcal{l}}_{i}\\in\\:L\\:\\)\u003c/span\u003e\u003c/span\u003eis the current instruction label and \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:m,n\\)\u003c/span\u003e\u003c/span\u003e are the values of \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{c}_{1},{c}_{2}\\)\u003c/span\u003e\u003c/span\u003e. Deterministic two-counter machines are a standard universal model of computation (Dudenhefner, \u003cspan citationid=\"CR7\" class=\"CitationRef\"\u003e2022\u003c/span\u003e; Minsky, \u003cspan citationid=\"CR15\" class=\"CitationRef\"\u003e1967\u003c/span\u003e).\u003c/p\u003e \u003cp\u003e \u003cstrong\u003eDefinition 3.3\u003c/strong\u003e \u003cp\u003e \u003cb\u003e(Criterion of universality).\u003c/b\u003e For each navigation architecture \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:A\\)\u003c/span\u003e\u003c/span\u003e considered below, universality is established by an effective simulation theorem: for every machine \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:M\\:\\)\u003c/span\u003e\u003c/span\u003ein a known universal model, there is a machine \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{A}_{M}\\:\\)\u003c/span\u003e\u003c/span\u003erealized in the navigation architecture and a computable encoding \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:E\\)\u003c/span\u003e\u003c/span\u003e of configurations such that each machine step of \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:M\\:\\)\u003c/span\u003e\u003c/span\u003eis mirrored exactly by one macro-step of \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{A}_{M}\\)\u003c/span\u003e\u003c/span\u003e. A macro-step may consist of finitely many primitive navigation actions, but it corresponds to one instruction of the simulated machine.\u003c/p\u003e \u003c/p\u003e"},{"header":"4. Universality by navigation on two coordinate axes","content":"\u003cp\u003eThe first architecture treats the allocentric map as a genuinely two-dimensional storage medium, but in a highly compressed way. One movable marker \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:X\\)\u003c/span\u003e\u003c/span\u003e is constrained to move on the \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:x\\)\u003c/span\u003e\u003c/span\u003e-axis and one movable marker \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:Y\\:\\)\u003c/span\u003e\u003c/span\u003eis constrained to move on the \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:y\\)\u003c/span\u003e\u003c/span\u003e-axis. Their distances from the origin encode the values of two unbounded counters. The internal control state of the machine plays the role of the finite control of a counter machine.\u003c/p\u003e \u003cp\u003e \u003cstrong\u003eDefinition 4.1\u003c/strong\u003e \u003cp\u003e \u003cb\u003e(Counter-based allocentric navigation machine).\u003c/b\u003e A counter-based allocentric navigation machine has an internal map \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\mathbb{N}}^{2}\\:\\)\u003c/span\u003e\u003c/span\u003ewith origin \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:O=\\left(\\text{0,0}\\right)\\)\u003c/span\u003e\u003c/span\u003e, two movable markers \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:X\\)\u003c/span\u003e\u003c/span\u003e and \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:Y\\:\\)\u003c/span\u003e\u003c/span\u003econstrained to the \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:x\\)\u003c/span\u003e\u003c/span\u003e-axis and \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:y\\)\u003c/span\u003e\u003c/span\u003e-axis respectively, a finite control set \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:Q\\)\u003c/span\u003e\u003c/span\u003e, and a navigator cursor. A configuration is a quadruple\u003cdiv id=\"Equg\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equg\" name=\"EquationSource\"\u003e\n$$\\:(q,p,x,y),$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003c/p\u003e \u003cp\u003ewhere \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:q\\in\\:Q\\)\u003c/span\u003e\u003c/span\u003eis the control state, \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:p\\in\\:{\\mathbb{N}}^{2}\\:\\)\u003c/span\u003e\u003c/span\u003eis the cursor position, \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:X\\:\\)\u003c/span\u003e\u003c/span\u003eis at \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:(x,0)\\)\u003c/span\u003e\u003c/span\u003e, and \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:Y\\:\\)\u003c/span\u003e\u003c/span\u003eis at \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:(0,\\:y)\\)\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e \u003cp\u003ePrimitive operations allow the cursor:\u003c/p\u003e \u003cp\u003e \u003cul\u003e \u003cli\u003e \u003cp\u003eto move one step east, west, north, or south whenever the resulting position remains in \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\mathbb{N}}^{2}\\)\u003c/span\u003e\u003c/span\u003e;\u003c/p\u003e \u003c/li\u003e \u003cli\u003e \u003cp\u003eto test whether the current position is the origin;\u003c/p\u003e \u003c/li\u003e \u003cli\u003e \u003cp\u003eto test whether the current position coincides with \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:X\\)\u003c/span\u003e\u003c/span\u003e or \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:Y\\)\u003c/span\u003e\u003c/span\u003e;\u003c/p\u003e \u003c/li\u003e \u003cli\u003e \u003cp\u003eto move \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:X\\:\\)\u003c/span\u003e\u003c/span\u003eone step east or west along the \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:x\\)\u003c/span\u003e\u003c/span\u003e-axis when the cursor is at \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:X\\)\u003c/span\u003e\u003c/span\u003e;\u003c/p\u003e \u003c/li\u003e \u003cli\u003e \u003cp\u003eto move \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:Y\\:\\)\u003c/span\u003e\u003c/span\u003eone step north or south along the \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:y\\)\u003c/span\u003e\u003c/span\u003e-axis when the cursor is at \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:Y\\)\u003c/span\u003e\u003c/span\u003e;\u003c/p\u003e \u003c/li\u003e \u003cli\u003e \u003cp\u003eand to change the control state.\u003c/p\u003e \u003c/li\u003e \u003c/ul\u003e \u003c/p\u003e \u003cp\u003e \u003cstrong\u003eTheorem 4.2\u003c/strong\u003e \u003cp\u003eFor every deterministic two-counter machine \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:M\\)\u003c/span\u003e\u003c/span\u003e, there exists a counter-based allocentric navigation machine \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{A}_{M\\:}\\)\u003c/span\u003e\u003c/span\u003ethat simulates \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:M\\:\\)\u003c/span\u003e\u003c/span\u003eexactly, one machine instruction at a time. Consequently, the class of counter-based allocentric navigation machines is Turing universal.\u003c/p\u003e \u003c/p\u003e \u003cp\u003e \u003cstrong\u003eProof\u003c/strong\u003e \u003cp\u003eFix a deterministic two-counter machine \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:M\\:\\)\u003c/span\u003e\u003c/span\u003ewith instruction labels\u003cdiv id=\"Equh\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equh\" name=\"EquationSource\"\u003e\n$$\\:L=\\{{\\mathcal{l}}_{0},\\dots\\:,{\\mathcal{l}}_{m-1},{\\mathcal{l}}_{h}\\}.$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003c/p\u003e \u003cp\u003eConstruct \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{A}_{M}\\:\\)\u003c/span\u003e\u003c/span\u003eso that its control states\u003cdiv id=\"Equi\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equi\" name=\"EquationSource\"\u003e\n$$\\:{q}_{0},\\dots\\:,{q}_{m-1},{q}_{h}$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003cp\u003ecorrespond exactly to the instruction labels of \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:M\\)\u003c/span\u003e\u003c/span\u003e. Encode a machine configuration \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\left({\\mathcal{l}}_{i},m,n\\right)\\:\\)\u003c/span\u003e\u003c/span\u003eby\u003cdiv id=\"Equj\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equj\" name=\"EquationSource\"\u003e\n$$\\:E({\\mathcal{l}}_{i},m,n)=({q}_{i},O,m,n),$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003cp\u003ewhere \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:O\\)\u003c/span\u003e\u003c/span\u003e denotes the cursor at the origin, the position of \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:X\\)\u003c/span\u003e\u003c/span\u003eat \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:(m,\\:0)\\:\\)\u003c/span\u003e\u003c/span\u003erepresents counter \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:1\\)\u003c/span\u003e\u003c/span\u003e, and the position of \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:Y\\)\u003c/span\u003e\u003c/span\u003eat \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:(0,\\:n)\\:\\)\u003c/span\u003e\u003c/span\u003erepresents counter \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:2\\)\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e \u003cp\u003eEncode the four instruction forms as finite navigation macros. An instruction \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\text{I}\\text{n}\\text{c}}_{1}\\left({\\mathcal{l}}_{j}\\right)\\:\\)\u003c/span\u003e\u003c/span\u003eis implemented by moving the cursor east step by step from the origin along the \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:x\\)\u003c/span\u003e\u003c/span\u003e-axis until the cursor reaches \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:X\\)\u003c/span\u003e\u003c/span\u003e, shifting \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:X\\)\u003c/span\u003e\u003c/span\u003e one step east, returning west step by step to the origin, and entering control state \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{q}_{j}\\)\u003c/span\u003e\u003c/span\u003e. An instruction \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\text{I}\\text{n}\\text{c}}_{2}\\left({\\mathcal{l}}_{j}\\right)\\:\\)\u003c/span\u003e\u003c/span\u003eis implemented analogously on the \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:y\\)\u003c/span\u003e\u003c/span\u003e-axis. An instruction \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\text{J}\\text{Z}\\text{D}\\text{e}\\text{c}}_{1}\\left({\\mathcal{l}}_{j},{\\mathcal{l}}_{k}\\right)\\:\\)\u003c/span\u003e\u003c/span\u003efirst checks at the origin whether the current position coincides with \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:X\\)\u003c/span\u003e\u003c/span\u003e. If so, the machine leaves \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:X\\:\\)\u003c/span\u003e\u003c/span\u003eunchanged and enters \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{q}_{j}\\)\u003c/span\u003e\u003c/span\u003e. If not, it moves east step by step until the cursor reaches \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:X\\)\u003c/span\u003e\u003c/span\u003e, shifts \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:X\\:\\)\u003c/span\u003e\u003c/span\u003eone step west, returns west step by step to the origin, and enters \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{q}_{k}\\)\u003c/span\u003e\u003c/span\u003e. The instruction \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\text{J}\\text{Z}\\text{D}\\text{e}\\text{c}}_{2}\\left({\\mathcal{l}}_{j},{\\mathcal{l}}_{k}\\right)\\:\\)\u003c/span\u003e\u003c/span\u003eis symmetric. Every macro terminates because the cursor traverses only a finite distance equal to the current counter value.\u003c/p\u003e \u003cp\u003eOne-step correctness follows by inspection of the four instruction forms. If \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:M\\:\\)\u003c/span\u003e\u003c/span\u003eperforms an increment instruction, then the corresponding marker in \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{A}_{M}\\:\\)\u003c/span\u003e\u003c/span\u003eis shifted exactly one unit in the appropriate axis direction and the control state changes exactly as prescribed. If \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:M\\:\\)\u003c/span\u003e\u003c/span\u003eperforms \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\text{J}\\text{Z}\\text{D}\\text{e}\\text{c}\\:\\)\u003c/span\u003e\u003c/span\u003eon a zero counter, then the cursor at the origin detects the corresponding marker there and \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{A}_{M}\\)\u003c/span\u003e\u003c/span\u003e follows the zero branch without moving the marker. If the counter is positive, \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{A}_{M}\\:\\)\u003c/span\u003e\u003c/span\u003emoves the marker one unit toward the origin and takes the nonzero branch. In every case, the resulting navigation configuration is exactly the encoding of the successor configuration of \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:M\\)\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e \u003cp\u003eInduction on the number of machine steps now yields: whenever\u003cdiv id=\"Equk\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equk\" name=\"EquationSource\"\u003e\n$$\\:{C}_{0}\\to\\:{C}_{1}\\to\\:\\cdots\\:\\to\\:{C}_{k}$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003cp\u003eis a run of \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:M\\)\u003c/span\u003e\u003c/span\u003e, the encoded sequence\u003cdiv id=\"Equl\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equl\" name=\"EquationSource\"\u003e\n$$\\:E\\left({C}_{0}\\right)\\Rightarrow\\:E\\left({C}_{1}\\right)\\Rightarrow\\:\\cdots\\:\\Rightarrow\\:E\\left({C}_{k}\\right)$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003cp\u003eis a run of \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{A}_{M}\\)\u003c/span\u003e\u003c/span\u003e, where each double arrow denotes one encoded macro-step. Halting is preserved because \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{q}_{h}\\:\\)\u003c/span\u003e\u003c/span\u003eis reached if and only if \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\mathcal{l}}_{h}\\:\\)\u003c/span\u003e\u003c/span\u003eis reached. Therefore, \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{A}_{M}\\:\\)\u003c/span\u003e\u003c/span\u003ecomputes the same partial function as \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:M\\)\u003c/span\u003e\u003c/span\u003e. Since deterministic two-counter machines are universal, the architecture is Turing universal. This first proof is mathematically straightforward and historically unsurprising, but it makes vivid the idea that a two-dimensional map can already function as unbounded memory by purely spatial means. ∎\u003c/p\u003e"},{"header":"5. Direct universality via a writable tape-path in the map","content":"\u003cp\u003eThe second construction makes the simulation more direct. Instead of encoding memory arithmetically as distances of markers from the origin, it places writable labels on landmarks along a distinguished bi-infinite path through the allocentric map. The current simulated location plays the role of the Turing head, and movement along the path plays the role of left and right head motion. In effect, this construction is an isomorphic recoding of an ordinary one-tape Turing machine into allocentric-map terms: the path realizes the tape, the current simulated location realizes the head position, and the stored labels on path landmarks realize the tape contents.\u003c/p\u003e \u003cp\u003e \u003cstrong\u003eDefinition 5.1\u003c/strong\u003e \u003cp\u003e \u003cb\u003e(Tape-path allocentric navigation machine).\u003c/b\u003e A tape-path allocentric navigation machine has an internal map \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\mathbb{Z}}^{2}\\)\u003c/span\u003e\u003c/span\u003e, a writable landmark-labeling function\u003cdiv id=\"Equm\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equm\" name=\"EquationSource\"\u003e\n$$\\:\\lambda\\::{\\mathbb{Z}}^{2}\\to\\:{\\Gamma\\:},$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003c/p\u003e \u003cp\u003ea distinguished bi-infinite path\u003cdiv id=\"Equn\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equn\" name=\"EquationSource\"\u003e\n$$\\:\\pi\\::\\mathbb{Z}\\to\\:{\\mathbb{Z}}^{2},$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003cp\u003ea finite control set \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:Q\\)\u003c/span\u003e\u003c/span\u003e, and a current simulated location constrained to lie on the path. In one computational step the machine checks the stored label at the current path location, updates that label, changes control state, and moves to the predecessor or successor location on the path.\u003c/p\u003e \u003cp\u003e \u003cstrong\u003eTheorem 5.2\u003c/strong\u003e \u003cp\u003eFor every deterministic one-tape Turing machine \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:M\\)\u003c/span\u003e\u003c/span\u003e, there exists a tape-path allocentric navigation machine \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{A}_{M}\\:\\)\u003c/span\u003e\u003c/span\u003ethat simulates \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:M\\:\\)\u003c/span\u003e\u003c/span\u003eexactly, step for step. Consequently, the class of tape-path allocentric navigation machines is Turing universal.\u003c/p\u003e \u003c/p\u003e \u003cp\u003e \u003cstrong\u003eProof\u003c/strong\u003e \u003cp\u003eLet\u003cdiv id=\"Equo\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equo\" name=\"EquationSource\"\u003e\n$$\\:M=(Q,{\\Gamma\\:},\\square\\:,{q}_{0},{q}_{h},\\delta\\:)$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003c/p\u003e \u003cp\u003ebe a deterministic one-tape Turing machine. Build \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{A}_{M}\\:\\)\u003c/span\u003e\u003c/span\u003ewith the same finite control states, the same tape alphabet, and the same transition table. This is essentially an isomorphic recoding of \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:M\\)\u003c/span\u003e\u003c/span\u003e: no new computational resources are introduced beyond a spatial redescription of the tape and head. Represent tape cell \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:i\\:\\)\u003c/span\u003e\u003c/span\u003eby the path location \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\pi\\:\\left(i\\right)\\)\u003c/span\u003e\u003c/span\u003e. Represent the Turing head position \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:h\\:\\)\u003c/span\u003e\u003c/span\u003eby the current simulated location \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\pi\\:\\left(h\\right)\\)\u003c/span\u003e\u003c/span\u003e. Represent the tape content function \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:t\\)\u003c/span\u003e\u003c/span\u003e by storing the label \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:t\\left(i\\right)\\:\\)\u003c/span\u003e\u003c/span\u003eat landmark \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\pi\\:\\left(i\\right)\\)\u003c/span\u003e\u003c/span\u003e. Thus encode a Turing configuration \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:(q,\\:h,\\:t)\\:\\)\u003c/span\u003e\u003c/span\u003eby\u003cdiv id=\"Equp\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equp\" name=\"EquationSource\"\u003e\n$$\\:E(q,h,t)=(q,\\pi\\:(h),{\\lambda\\:}_{t}),$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003cp\u003ewhere \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\lambda\\:}_{t}\\left(\\pi\\:\\left(i\\right)\\right)=t\\left(i\\right)\\:\\)\u003c/span\u003e\u003c/span\u003efor every integer \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:i\\)\u003c/span\u003e\u003c/span\u003e and all non-path locations are blank.\u003c/p\u003e \u003cp\u003eNow take one Turing step from \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:C=(q,h,t)\\)\u003c/span\u003e\u003c/span\u003e. Let \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:a=t\\left(h\\right)\\)\u003c/span\u003e\u003c/span\u003e, and suppose\u003cdiv id=\"Equq\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equq\" name=\"EquationSource\"\u003e\n$$\\:\\delta\\:(q,a)=({q}^{{\\prime\\:}},b,D).$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003cp\u003eThe Turing successor configuration is \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{C}^{{\\prime\\:}}=({q}^{{\\prime\\:}},{h}^{{\\prime\\:}},{t}^{{\\prime\\:}})\\)\u003c/span\u003e\u003c/span\u003e, where \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{t}^{{\\prime\\:}}\\)\u003c/span\u003e\u003c/span\u003ediffers from \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:t\\:\\)\u003c/span\u003e\u003c/span\u003eonly in writing \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:b\\:\\)\u003c/span\u003e\u003c/span\u003eat cell \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:h\\)\u003c/span\u003e\u003c/span\u003e, and \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{h}^{{\\prime\\:}}=h-1\\:\\)\u003c/span\u003e\u003c/span\u003eif \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:D=L\\:\\)\u003c/span\u003e\u003c/span\u003eor \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{h}^{{\\prime\\:}}=h+1\\:\\)\u003c/span\u003e\u003c/span\u003eif \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:D=R\\)\u003c/span\u003e\u003c/span\u003e. In the encoded navigation configuration, the current location is \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\pi\\:\\left(h\\right)\\:\\)\u003c/span\u003e\u003c/span\u003eand the current label is \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:a\\)\u003c/span\u003e\u003c/span\u003e. The encoded transition rule writes \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:b\\:\\)\u003c/span\u003e\u003c/span\u003eat \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\pi\\:\\left(h\\right)\\)\u003c/span\u003e\u003c/span\u003e, changes state to \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{q}^{{\\prime\\:}}\\)\u003c/span\u003e\u003c/span\u003e, and moves to \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\pi\\:\\left(h-1\\right)\\:\\)\u003c/span\u003e\u003c/span\u003eor \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\pi\\:\\left(h+1\\right)\\:\\)\u003c/span\u003e\u003c/span\u003eaccording to \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:D\\)\u003c/span\u003e\u003c/span\u003e. Therefore, the resulting navigation configuration is exactly \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:E\\left({C}^{{\\prime\\:}}\\right)\\)\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e \u003cp\u003eInduction on run length yields a full step-for-step simulation. Every run of \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:M\\:\\)\u003c/span\u003e\u003c/span\u003eis mirrored by a run of \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{A}_{M}\\:\\)\u003c/span\u003e\u003c/span\u003ethat preserves the control state, the complete tape contents, the head location, and halting behavior at every stage. Hence \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{A}_{M}\\:\\)\u003c/span\u003e\u003c/span\u003ecomputes the same partial function as \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:M\\)\u003c/span\u003e\u003c/span\u003e. Because ordinary one-tape Turing machines are universal, the tape-path architecture is Turing universal. Relative to the first proof, this construction is more direct and conceptually closer to standard Turing-machine organization. Relative to older graph-based formalisms, however, it remains a familiar kind of tape-on-graph encoding. ∎\u003c/p\u003e"},{"header":"6. Direct universality via a fully local two-dimensional landmark layout","content":"\u003cp\u003eThe third construction removes the globally designated path from the machine\u0026rsquo;s operative resources. Memory is realized as a two-dimensional field of landmarks, and the machine moves only by following local predecessor/successor information available at the landmark currently occupied by the simulated head. Equivalently, the construction gives a local two-dimensional embedding of a linear Turing tape into a zigzag track in the allocentric map: the machine itself accesses only local predecessor/successor cues, while the linear order appears only in the metatheory.\u003c/p\u003e \u003cp\u003e \u003cstrong\u003eDefinition 6.1\u003c/strong\u003e \u003cp\u003e \u003cb\u003e(Local-layout allocentric navigation machine).\u003c/b\u003e Let the internal map be \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\mathbb{Z}}^{2}\\)\u003c/span\u003e\u003c/span\u003e, and let the memory landmarks occupy the two-row track\u003cdiv id=\"Equr\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equr\" name=\"EquationSource\"\u003e\n$$\\:T\\:=\\:\\left\\{\\right(x,y)\\mathbb{\\:}\\in\\:\\mathbb{\\:}\\mathbb{Z}\u0026sup2;\\mathbb{\\:}|\\mathbb{\\:}y\\:\\in\\:\\:\\left\\{\\text{0,1}\\right\\}\\}.$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003c/p\u003e \u003cp\u003eThe landmarks are arranged in a zigzag chain through the plane:\u003cdiv id=\"Equs\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equs\" name=\"EquationSource\"\u003e\n$$\\:\\cdots\\:\\to\\:(-\\text{2,0})\\to\\:(-\\text{2,1})\\to\\:(-\\text{1,1})\\to\\:(-\\text{1,0})\\to\\:\\left(\\text{0,0}\\right)\\to\\:\\left(\\text{0,1}\\right)\\to\\:\\left(\\text{1,1}\\right)\\to\\:\\left(\\text{1,0}\\right)\\to\\:\\left(\\text{2,0}\\right)\\to\\:\\cdots\\:\\text{\\hspace{0.17em}}.$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003cp\u003eEach landmark stores a writable label from \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\Gamma\\:}\\)\u003c/span\u003e\u003c/span\u003e, a head marker indicating whether the simulated head is currently there, and a fixed local landmark type determining only two local directions: predecessor and successor. The machine has no access to any global index over the chain.\u003c/p\u003e \u003cp\u003e \u003cstrong\u003eDefinition 6.2\u003c/strong\u003e \u003cp\u003e \u003cb\u003e(The four local landmark types).\u003c/b\u003e Type A landmarks occur at \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:(2k,\\:0)\\)\u003c/span\u003e\u003c/span\u003e and point west as predecessor and north as successor. Type B landmarks occur at (2\u003cem\u003ek\u003c/em\u003e, 1)\u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\:\\)\u003c/span\u003e\u003c/span\u003eand point south as predecessor and east as successor. Type C landmarks occur at \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\left(2k+1,\\:1\\right)\\:\\)\u003c/span\u003e\u003c/span\u003eand point west as predecessor and south as successor. Type D landmarks occur at \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\left(2k+1,\\:0\\right)\\:\\)\u003c/span\u003e\u003c/span\u003eand point north as predecessor and east as successor. These local arrows are the only navigation data available to the machine.\u003c/p\u003e \u003c/p\u003e \u003cp\u003e \u003cstrong\u003eLemma 6.3\u003c/strong\u003e \u003cp\u003eThere exists a bijection\u003cdiv id=\"Equt\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equt\" name=\"EquationSource\"\u003e\n$$\\:\\eta\\::\\mathbb{Z}\\to\\:T$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003c/p\u003e \u003cp\u003esuch that following the local successor pointer from \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\eta\\:\\left(i\\right)\\:\\)\u003c/span\u003e\u003c/span\u003ereaches \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\eta\\:(i+1)\\)\u003c/span\u003e\u003c/span\u003e, while following the local predecessor pointer from \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\eta\\:\\left(i\\right)\\:\\)\u003c/span\u003e\u003c/span\u003ereaches \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\eta\\:(i-1)\\)\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e \u003cp\u003e \u003cstrong\u003eProof\u003c/strong\u003e \u003cp\u003eDefine \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\eta\\:\\:\\)\u003c/span\u003e\u003c/span\u003eby listing the zigzag in order:\u003c/p\u003e \u003c/p\u003e \u003cp\u003e \u003cspan class=\"InlineEquation\"\u003e \u003cspan class=\"mathinline\"\u003e\\(\\:\\eta\\:\\left(4k\\right)=\\left(2k,0\\right),\\:\\:\\eta\\:(4k+1)=(2k,1),\\)\u003c/span\u003e \u003c/span\u003e \u003cspan class=\"InlineEquation\"\u003e \u003cspan class=\"mathinline\"\u003e\\(\\:\\eta\\:\\left(4k+2\\right)=\\left(2k+1,\\:1\\right),\\:\\:\\eta\\:(4k+3)=(2k+1,\\:0).\\)\u003c/span\u003e \u003c/span\u003e \u003c/p\u003e \u003cp\u003eThe successor and predecessor claims are then verified case by case from the four landmark types. From a type A landmark, successor is north; from B, east; from C, south; from D, east. The predecessor directions are the corresponding reverses. Hence predecessor and successor along the local arrows coincide exactly with decrement and increment of the hidden index \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:i\\)\u003c/span\u003e\u003c/span\u003e. The bijection \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\eta\\:\\:\\)\u003c/span\u003e\u003c/span\u003eis used only in the metatheory to prove correctness; it is not available to the machine itself. ∎\u003c/p\u003e \u003cp\u003e \u003cstrong\u003eTheorem 6.4\u003c/strong\u003e \u003cp\u003eFor every deterministic one-tape Turing machine \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:M\\)\u003c/span\u003e\u003c/span\u003e, there exists a local-layout allocentric navigation machine \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{A}_{M}\\)\u003c/span\u003e\u003c/span\u003e that simulates \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:M\\:\\)\u003c/span\u003e\u003c/span\u003eexactly, step for step. Consequently, the class of local-layout allocentric navigation machines is Turing universal.\u003c/p\u003e \u003c/p\u003e \u003cp\u003e \u003cstrong\u003eProof\u003c/strong\u003e \u003cp\u003eLet\u003cdiv id=\"Equu\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equu\" name=\"EquationSource\"\u003e\n$$\\:M=(Q,{\\Gamma\\:},\\square\\:,{q}_{0},{q}_{h},\\delta\\:)$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003c/p\u003e \u003cp\u003ebe a deterministic one-tape Turing machine. Build \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{A}_{M}\\)\u003c/span\u003e\u003c/span\u003e with the same finite control set and the same transition table. Thus, the linear tape of \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:M\\:\\)\u003c/span\u003e\u003c/span\u003eis embedded into the two-dimensional track \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:T\\:\\)\u003c/span\u003e\u003c/span\u003ein such a way that the machine follows only local predecessor/successor structure; the indexing \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\eta\\:\\)\u003c/span\u003e\u003c/span\u003e is used only to prove that this local structure recovers the usual left/right tape dynamics. If\u003cdiv id=\"Equv\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equv\" name=\"EquationSource\"\u003e\n$$\\:\\delta\\:(q,a)=({q}^{{\\prime\\:}},b,L),$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003cp\u003ethen \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{A}_{M}\\)\u003c/span\u003e\u003c/span\u003e, when in state \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:q\\:\\)\u003c/span\u003e\u003c/span\u003eat a landmark storing \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:a\\)\u003c/span\u003e\u003c/span\u003e, writes \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:b\\)\u003c/span\u003e\u003c/span\u003e, changes state to \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{q}^{{\\prime\\:}}\\)\u003c/span\u003e\u003c/span\u003e, and moves the head marker to the locally designated predecessor landmark. If\u003cdiv id=\"Equw\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equw\" name=\"EquationSource\"\u003e\n$$\\:\\delta\\:(q,a)=({q}^{{\\prime\\:}},b,R),$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003cp\u003eit writes \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:b\\)\u003c/span\u003e\u003c/span\u003e, changes state to \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{q}^{{\\prime\\:}}\\)\u003c/span\u003e\u003c/span\u003e, and moves to the locally designated successor landmark instead.\u003c/p\u003e \u003cp\u003eEncode a Turing configuration \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:(q,\\:h,\\:t)\\:\\)\u003c/span\u003e\u003c/span\u003eby\u003cdiv id=\"Equx\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equx\" name=\"EquationSource\"\u003e\n$$\\:E(q,h,t)=(q,{\\lambda\\:}_{t},\\eta\\:(h\\left)\\right),$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003cp\u003ewhere \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\lambda\\:}_{t}\\left(\\eta\\:\\right(i\\left)\\right)=t\\left(i\\right)\\)\u003c/span\u003e\u003c/span\u003e for each integer \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:i\\)\u003c/span\u003e\u003c/span\u003e. Thus, tape cell \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:i\\)\u003c/span\u003e\u003c/span\u003e is represented by landmark \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\eta\\:\\left(i\\right)\\)\u003c/span\u003e\u003c/span\u003e, and the Turing head position \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:h\\)\u003c/span\u003e\u003c/span\u003e is represented by the unique head-marked landmark \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\eta\\:\\left(h\\right)\\)\u003c/span\u003e\u003c/span\u003e. Now take one Turing step from \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:C=(q,h,t)\\)\u003c/span\u003e\u003c/span\u003e. Let \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:a=t\\left(h\\right)\\)\u003c/span\u003e\u003c/span\u003e, and suppose\u003cdiv id=\"Equy\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equy\" name=\"EquationSource\"\u003e\n$$\\:\\delta\\:(q,a)=({q}^{{\\prime\\:}},b,D).$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003cp\u003eThe Turing successor configuration is \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{C}^{{\\prime\\:}}=({q}^{{\\prime\\:}},{h}^{{\\prime\\:}},{t}^{{\\prime\\:}})\\)\u003c/span\u003e\u003c/span\u003e, where \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{t}^{{\\prime\\:}}\\)\u003c/span\u003e\u003c/span\u003ediffers from \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:t\\)\u003c/span\u003e\u003c/span\u003e only in writing \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:b\\:\\)\u003c/span\u003e\u003c/span\u003eat cell \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:h\\:\\)\u003c/span\u003e\u003c/span\u003eand \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{h}^{{\\prime\\:}}=h-1\\:\\)\u003c/span\u003e\u003c/span\u003eif \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:D=L\\:\\)\u003c/span\u003e\u003c/span\u003eor \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{h}^{{\\prime\\:}}=h+1\\:\\)\u003c/span\u003e\u003c/span\u003eif \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:D=R\\)\u003c/span\u003e\u003c/span\u003e. In the encoded navigation configuration, the current landmark is \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\eta\\:\\left(h\\right)\\)\u003c/span\u003e\u003c/span\u003e and the label stored there is \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:a\\)\u003c/span\u003e\u003c/span\u003e. The encoded local rule writes \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:b\\)\u003c/span\u003e\u003c/span\u003e, changes state to \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{q}^{{\\prime\\:}}\\)\u003c/span\u003e\u003c/span\u003e, and moves the head marker by following the current landmark\u0026rsquo;s predecessor or successor pointer according to \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:D\\)\u003c/span\u003e\u003c/span\u003e. By Lemma \u003cspan refid=\"FPar13\" class=\"InternalRef\"\u003e6.3\u003c/span\u003e, this local move reaches \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\eta\\:\\left(h-1\\right)\\:\\)\u003c/span\u003e\u003c/span\u003ein the left case and \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\eta\\:\\left(h+1\\right)\\:\\)\u003c/span\u003e\u003c/span\u003ein the right case. Therefore, the resulting navigation configuration is exactly \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:E\\left({C}^{{\\prime\\:}}\\right)\\)\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e \u003cp\u003eInduction on run length yields a full step-for-step simulation. Every run of \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:M\\:\\)\u003c/span\u003e\u003c/span\u003eis mirrored by a run of \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{A}_{M}\\:\\)\u003c/span\u003e\u003c/span\u003ethat preserves the control state, tape contents, head location, and halting behavior at every stage. Hence \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{A}_{M}\\:\\)\u003c/span\u003e\u003c/span\u003ecomputes the same partial function as \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:M\\)\u003c/span\u003e\u003c/span\u003e. Because ordinary one-tape Turing machines are universal, the local-layout architecture is Turing universal. This third proof is the most faithful to the idea of computation by internal navigation among landmarks because the operative resources of the machine are entirely local. In that respect it lies especially close, in mathematical spirit, to local graph-based machine models studied in computability theory, even though it is recast here in allocentric cognitive-map terms. ∎\u003c/p\u003e \u003cp\u003eWhile the proofs of Theorems \u003cspan refid=\"FPar9\" class=\"InternalRef\"\u003e5.2\u003c/span\u003e and \u003cspan refid=\"FPar15\" class=\"InternalRef\"\u003e6.4\u003c/span\u003e assign locations within a cognitive map formal roles corresponding to entries in the tape alphabet \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\Gamma\\:}\\)\u003c/span\u003e\u003c/span\u003e, this should not be taken to imply that allocentric navigation requires \u0026ldquo;symbols\u0026rdquo; in any language-like sense. Letters of a finite alphabet are just uninterpreted labels. Nothing in the universality proofs depends on the stored items in the map being symbolic in any richer sense.\u003c/p\u003e \u003cp\u003eTo make this explicit, let \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:O\\:\\)\u003c/span\u003e\u003c/span\u003ebe a finite set of reliably distinguishable stored item-types, and let\u003cdiv id=\"Equz\" class=\"Equation\"\u003e\u003cdiv format=\"TEX\" class=\"mathdisplay\" id=\"FileID_Equz\" name=\"EquationSource\"\u003e\n$$\\:\\rho\\::O\\to\\:{\\Gamma\\:}$$\u003c/div\u003e\u003c/div\u003e\u003c/p\u003e \u003cp\u003ebe a fixed bijection onto the tape alphabet \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\Gamma\\:}\\)\u003c/span\u003e\u003c/span\u003e. Each relevant location in the allocentric map stores an item of type \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:o\\in\\:O\\)\u003c/span\u003e\u003c/span\u003e, and this item realizes the tape letter \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:\\rho\\:\\left(o\\right)\\)\u003c/span\u003e\u003c/span\u003e. Thus, rather than assuming that the map literally stores elements of \u003cspan class=\"InlineEquation\"\u003e\u003cspan class=\"mathinline\"\u003e\\(\\:{\\Gamma\\:}\\)\u003c/span\u003e\u003c/span\u003e, we may assume that it stores one of finitely many reliably distinguishable item-types. The universality proofs go through unchanged.\u003c/p\u003e"},{"header":"7. Comparative significance","content":"\u003cp\u003eThe three theorems establish the same computability-theoretic conclusion while differing in how they apply navigation-based processing. The counter proof is the most austere. It uses a two-dimensional map essentially, because the \u003cem\u003ex\u003c/em\u003e- and \u003cem\u003ey\u003c/em\u003e-axes encode different unbounded stores, yet its memory is encoded purely by spatial location. This makes the proof conceptually economical.\u003c/p\u003e \u003cp\u003eThe tape-path proof is more direct. In fact, it is essentially an isomorphic recoding of an ordinary one-tape Turing machine into an allocentric cognitive map. If a navigation architecture can maintain a track of landmarks with replaceable stored items and move a simulated location along that track, then the standard Turing model is already present almost verbatim. The advantage is interpretive clarity: landmarks are memory cells, their stored items are tape entries, and navigation is head movement. Within cognitive maps, those items may be interpreted as information associated with objects or features at landmarks. The disadvantage is that the architecture still presupposes a globally distinguished path whose adjacency relations are simply handed to the machine.\u003c/p\u003e \u003cp\u003eThe local-layout proof is more local and spatially natural. It may be viewed as a local two-dimensional embedding of a linear Turing tape into a field of landmarks. The memory is realized as a genuinely two-dimensional field of landmarks, and the machine moves only by inspecting local directional cues at its present position. The hidden indexing used in the proof exists only at the meta-level to establish correctness. Thus, the operative resources of the machine are fully local even though the proof uses a global enumeration for convenience.\u003c/p\u003e \u003cp\u003eThe mathematical content of these constructions is similar to earlier work on graph-based computation and locally rewritable memory. Kolmogorov-Uspensky machines and storage-modification machines already show that graph-structured memory plus local operations can realize universal computation. Graph Turing machines show that Turing computation can be reproduced inside labeled graphs. Graph-walking automata and exploration models show how navigation itself becomes a computational lens, while also revealing that navigation without sufficient writable memory is too weak. Against that background, the present proofs are a reconstruction of those results within a framework motivated by empirical work on neurocognitive architecture. This reconstruction makes clear that computational universality is not tied to any particular representational format, but can arise within a variety of structured systems, including those based on spatial organization and local interaction.\u003c/p\u003e \u003cp\u003eThe present contribution is therefore about the representational and computational power of allocentric navigation, particularly the kind of offline navigation that might underlie many cognitive functions. These universality results make explicit how standard computability-theoretic constructions can be reinterpreted inside a navigation-based allocentric-map architecture that relies on representational and computational resources independently studied in neuroscience. The full universal machines proved here remain heavily idealized, but the allocentric-map vocabulary is anchored in the mainstream empirical literature on spatial coding and cognitive maps.\u003c/p\u003e \u003cp\u003eFrom this perspective, the results may be seen not merely as demonstrations of sufficiency, but as clarification of the structural resources already present in allocentric navigation architectures. Such systems involve storage at landmarks, locally defined transitions between states, and structured spatial organization. Once these elements are in place, the capacity for universal computation follows. The present constructions therefore make explicit what is already implicit in these architectures: that structured spatial organization, together with local update rules, is sufficient to support arbitrarily complex computable transformations.\u003c/p\u003e \u003cp\u003eThis has direct implications for the claim that navigation-based or otherwise nonclassical architectures lack sufficient representational or computational power to support cognition. This sort of objection appears to depend on an additional assumption, namely that adequate representation must take a symbolic, language-like form. The results developed here undermine that assumption and flip the script. They show that systems grounded in structured spatial relations and local transition rules can realize the same class of computable transformations typically associated with symbolic architectures. Accordingly, symbolic processing could be understood as a special case of spatial navigation, where symbols are items represented at locations within a cognitive map and symbolic operations are actions taken on such items. Developing this suggestion in detail is a research program to be pursued in future work.\u003c/p\u003e"},{"header":"8. Limitations and scope","content":"\u003cp\u003eThese universality theorems require standard idealizations. They assume an unbounded allocentric map, perfectly reliable landmark identity, exact storage, exact local movement, and arbitrarily long navigation. None of those assumptions should be attributed to biological systems. These results therefore do not establish that animals, humans, or hippocampal-entorhinal systems literally implement Turing-universal navigation machines. They establish only that allocentric navigation-based architectures, if idealized in the usual way familiar from computability theory, are computationally universal.\u003c/p\u003e \u003cp\u003eThe evidence from neuroscience supports allocentric spatial representation, place and grid coding, and map-like navigation capacities, including offline navigation. It does not by itself support the stronger assumptions required for universal computation, such as exact unbounded writable memory at landmarks. The contribution is thus a formal reconstruction that begins from an empirically motivated representational vocabulary and then idealizes it into a universal machine model.\u003c/p\u003e \u003cp\u003eThe theorems also do not show that every navigation architecture is universal. Universality depends on specific structural enrichments: unbounded storage, reliable update operations, and sufficiently precise control. A purely finite navigation system, or a system lacking sufficiently stable memory, could not be strictly universal. That said, the navigation and action processes discussed here may also occur partly within the external environment, which under suitable idealization may be treated as an unbounded memory store. In that case, the same type of universality construction can be realized by an allocentric navigation architecture that uses environmental as well as internal storage. This suggests how cognitive maps may help explain calculations performed by humans on paper or other external media.\u003c/p\u003e"},{"header":"9. Conclusion","content":"\u003cp\u003eThis article has presented three formal routes from allocentric cognitive-map architectures to computational universality. The first uses two-dimensional spatial position to encode counter values. The second turns a distinguished path of writable landmarks into a direct analogue of a Turing tape. The third replaces that global path with a fully local two-dimensional layout whose predecessor and successor relations are available only through local landmark structure.\u003c/p\u003e \u003cp\u003eThese results are mathematically continuous with earlier work on graph-based computation, but they make explicit how universal computational capacity can be reconstructed within the framework of navigation within allocentric cognitive maps. In that way, they clarify the representational and computational significance of a class of architectures that are independently motivated by empirical work in neuroscience.\u003c/p\u003e \u003cp\u003eNone of this is to say that biological navigation literally implements classical Turing-style computation. On the contrary, the point is that, if allocentric navigation\u0026mdash;which is normally nonclassical in most respects\u0026mdash;is expressive enough to implement classical Turing computation, it may be expressive enough to explain cognition nonclassically (cf. Piccinini, \u003cspan citationid=\"CR20\" class=\"CitationRef\"\u003e2025\u003c/span\u003e). That is enough to motivate a research program in which higher cognition, including symbolic processing, is reconstructed in map-based terms.\u003c/p\u003e"},{"header":"Declarations","content":" \u003ch2\u003eCompeting Interests\u003c/b\u003e.\u003c/h2\u003e \u003cp\u003eNo funding was received for conducting this study. The authors has no relevant financial or non-financial interests to disclose.\u003c/p\u003e \u003c/p\u003e\u003ch2\u003eAuthor Contribution\u003c/h2\u003e\u003cp\u003eI used generative AI (ChatGPT 5.4 Thinking and Pro and Google Gemini 3.1 Pro) to help with research assistance, proof writing and checking, and draft feedback. All substantive ideas, arguments, interpretations, source selection, and final wording are my own and were reviewed and approved by me. I take full responsibility for the work.\u003c/p\u003e\u003ch2\u003eAcknowledgement\u003c/h2\u003e\u003cp\u003eThis work was partially done on the land of the Osage Nation, Otae-Missouri, Chikasaw, Illni, Ioway, Quapaw, Shawnee, Delaware, Kickapoo, Sac \u0026amp; Fox, Omaha, and Santee Sioux. I thank Carl Sachs for recently reminding me of Wells\u0026rsquo;s (2006) work, which may have helped inspire this project. Mart\u0026iacute;nez (2025) may also have been a source of inspiration. Thanks to Jeff Dauer, Pawel Pachniewski, Waldemar Rohloff, and Stephen Selesnick for helpful feedback on the manuscript.\u003c/p\u003e"},{"header":"References","content":"\u003col\u003e\u003cli\u003e\u003cspan\u003eAckerman, N.L., Freer, C.E.: Graph Turing machines. In J. Kennedy and R. J. G. B. de Queiroz (Eds.), \u003cem\u003eLogic, Language, Information, and Computation\u003c/em\u003e (Lecture Notes in Computer Science, Vol. 10388, pp. 1\u0026ndash;13). Springer. (2017). \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1007/978-3-662-55386-2_1\u003c/span\u003e\u003cspan address=\"10.1007/978-3-662-55386-2_1\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eBasu, J., Nagel, K.I.: Neural circuits for goal-directed navigation across species. Trends Neurosci. \u003cb\u003e47\u003c/b\u003e(11), 904\u0026ndash;917 (2024). \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1016/j.tins.2024.09.005\u003c/span\u003e\u003cspan address=\"10.1016/j.tins.2024.09.005\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eBehrens, T.E.J., Muller, T.H., Whittington, J.C.R., Mark, S., Baram, A.B., Stachenfeld, K.L., Kurth-Nelson, Z.: What is a cognitive map? Organizing knowledge for flexible behavior. Neuron. \u003cb\u003e100\u003c/b\u003e(2), 490\u0026ndash;509 (2018). \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1016/j.neuron.2018.10.002\u003c/span\u003e\u003cspan address=\"10.1016/j.neuron.2018.10.002\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eCarr, M.F., Jadhav, S.P., Frank, L.M.: Hippocampal replay in the awake state: A potential substrate for memory consolidation and retrieval. Nat. Neurosci. \u003cb\u003e14\u003c/b\u003e(2), 147\u0026ndash;153 (2011). \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1038/nn.2732\u003c/span\u003e\u003cspan address=\"10.1038/nn.2732\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eCourellis, H.S., Minxha, J., Cardenas, A.R., Kimmel, D.L., Reed, C.M., Valiante, T.A., Salzman, C.D., Mamelak, A.N., Fusi, S., Rutishauser, U.: Abstract representations emerge in human hippocampal neurons during inference. Nature. \u003cb\u003e632\u003c/b\u003e(8026), 841\u0026ndash;849 (2024). \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1038/s41586-024-07799-x\u003c/span\u003e\u003cspan address=\"10.1038/s41586-024-07799-x\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eDragoi, G., Tonegawa, S.: Preplay of future place cell sequences by hippocampal cellular assemblies. Nature. \u003cb\u003e469\u003c/b\u003e(7330), 397\u0026ndash;401 (2011). \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1038/nature09633\u003c/span\u003e\u003cspan address=\"10.1038/nature09633\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eDudenhefner, A.: Certified decision procedures for two-counter machines. In A. P. Felty (Ed.), \u003cem\u003e7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022)\u003c/em\u003e (Leibniz International Proceedings in Informatics [LIPIcs], Vol. 228, Article 16, p. 16:1\u0026ndash;16:18). Schloss Dagstuhl\u0026mdash;Leibniz-Zentrum fuer Informatik. (2022). \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.4230/LIPIcs.FSCD.2022.16\u003c/span\u003e\u003cspan address=\"10.4230/LIPIcs.FSCD.2022.16\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eEpstein, R.A., Patai, E.Z., Julian, J.B., Spiers, H.J.: The cognitive map in humans: Spatial navigation and beyond. Nat. Neurosci. \u003cb\u003e20\u003c/b\u003e(11), 1504\u0026ndash;1513 (2017). \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1038/nn.4656\u003c/span\u003e\u003cspan address=\"10.1038/nn.4656\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eFraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph exploration by a finite automaton. Theor. Comput. Sci. \u003cb\u003e345\u003c/b\u003e(2\u0026ndash;3), 331\u0026ndash;344 (2005). \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1016/j.tcs.2005.07.014\u003c/span\u003e\u003cspan address=\"10.1016/j.tcs.2005.07.014\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eFodor, J.A., Pylyshyn, Z.W.: Connectionism and cognitive architecture: A critical analysis. Cognition. \u003cb\u003e28\u003c/b\u003e(1\u0026ndash;2), 3\u0026ndash;71 (1988). \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1016/0010-0277(88)90031-5\u003c/span\u003e\u003cspan address=\"10.1016/0010-0277(88)90031-5\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eGallistel, C.R., King, A.P.: Memory and the computational brain: Why cognitive science will transform neuroscience. Wiley (2009)\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eKolmogorov, A.N., Uspensky, V.A.: On the definition of an algorithm. Am. Math. Soc. Translations: Ser. \u003cb\u003e2\u003c/b\u003e, 217\u0026ndash;245 (1963). (Original work published 1958)\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eKrakauer, J.W., Ramsey, W.: Mental representation without neural representation: Understanding the evidence. Philos. Mind Sci., \u003cb\u003e7\u003c/b\u003e(1). (2026)\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eMart\u0026iacute;nez, M.: Structural representation as complexity management. In: Neurocognitive foundations of mind, pp. 120\u0026ndash;143. Routledge (2025)\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eMinsky, M.L.: Computation: Finite and infinite machines. Prentice-Hall (1967)\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eMoser, E.I., Kropff, E., Moser, M.-B.: Place cells, grid cells, and the brain's spatial representation system. Annu. Rev. Neurosci. \u003cb\u003e31\u003c/b\u003e, 69\u0026ndash;89 (2008). \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1146/annurev.neuro.31.061307.090723\u003c/span\u003e\u003cspan address=\"10.1146/annurev.neuro.31.061307.090723\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eO'Keefe, J., Dostrovsky, J.: The hippocampus as a spatial map: Preliminary evidence from unit activity in the freely-moving rat. Brain Res. \u003cb\u003e34\u003c/b\u003e(1), 171\u0026ndash;175 (1971). \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1016/0006-8993(71)90358-1\u003c/span\u003e\u003cspan address=\"10.1016/0006-8993(71)90358-1\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eO'Keefe, J., Nadel, L.: The hippocampus as a cognitive map. Oxford University Press (1978)\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eOkhotin, A.: Graph-walking automata: From whence they come, and whither they are bound. In M. Hospodar \u0026amp; G. Jiraskova (Eds.), \u003cem\u003eImplementation and Application of Automata\u003c/em\u003e (Lecture Notes in Computer Science, Vol. 11601, pp. 10\u0026ndash;29). Springer. (2019). \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1007/978-3-030-23679-3_2\u003c/span\u003e\u003cspan address=\"10.1007/978-3-030-23679-3_2\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003ePiccinini, G.: Neural hardware for the language of thought: New rules for an old game. arXiv:2510.10251 (2025)\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eSch\u0026ouml;nhage, A.: Storage modification machines. SIAM J. Comput. \u003cb\u003e9\u003c/b\u003e(3), 490\u0026ndash;508 (1980). \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1137/0209036\u003c/span\u003e\u003cspan address=\"10.1137/0209036\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eShepherdson, J.C., Sturgis, H.E.: Computability of recursive functions. J. ACM. \u003cb\u003e10\u003c/b\u003e(2), 217\u0026ndash;255 (1963). \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1145/321160.321170\u003c/span\u003e\u003cspan address=\"10.1145/321160.321170\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eTuring, A.M.: On computable numbers, with an application to the Entscheidungsproblem. \u003cem\u003eProceedings of the London Mathematical Society, s2-42\u003c/em\u003e(1), 230\u0026ndash;265. (1937). \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1112/plms/s2-42.1.230\u003c/span\u003e\u003cspan address=\"10.1112/plms/s2-42.1.230\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eWells, A.: Rethinking cognitive computation: Turing and the science of the mind. Macmillan (2006)\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eWhittington, J.C.R., McCaffary, D., Bakermans, J.J.W., Behrens, T.E.J.: How to build a cognitive map. Nat. Neurosci. \u003cb\u003e25\u003c/b\u003e(10), 1257\u0026ndash;1272 (2022). \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1038/s41593-022-01153-y\u003c/span\u003e\u003cspan address=\"10.1038/s41593-022-01153-y\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eWikenheiser, A.M., Schoenbaum, G.: Over the river, through the woods: Cognitive maps in the hippocampus and orbitofrontal cortex. Nat. Rev. Neurosci. \u003cb\u003e17\u003c/b\u003e(8), 513\u0026ndash;523 (2016). \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttps://doi.org/10.1038/nrn.2016.56\u003c/span\u003e\u003cspan address=\"10.1038/nrn.2016.56\" targettype=\"DOI\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e\u003c/ol\u003e"}],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":true,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":false,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":false,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"journal-of-biological-physics","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"jobp","sideBox":"Learn more about [Journal of Biological Physics](http://link.springer.com/journal/10867)","snPcode":"10867","submissionUrl":"https://submission.nature.com/new-submission/10867/3","title":"Journal of Biological Physics","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"Turing universality, Turing machines, cognitive maps, allocentric representation, navigation-based computation","lastPublishedDoi":"10.21203/rs.3.rs-9307584/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-9307584/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eThis 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\u0026rsquo;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.\u003c/p\u003e","manuscriptTitle":"Navigation within Allocentric Cognitive Maps is Computationally Universal","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2026-04-10 20:18:49","doi":"10.21203/rs.3.rs-9307584/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"editorInvitedReview","content":"","date":"2026-05-13T23:32:27+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2026-04-30T16:59:41+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"291486248815965566728137439496290993913","date":"2026-04-22T12:36:20+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"27889466596610698815525569996418979267","date":"2026-04-06T18:20:12+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2026-04-06T17:29:51+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2026-04-06T17:23:06+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2026-04-06T04:52:02+00:00","index":"","fulltext":""},{"type":"submitted","content":"Journal of Biological Physics","date":"2026-04-03T01:06:24+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"journal-of-biological-physics","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"jobp","sideBox":"Learn more about [Journal of Biological Physics](http://link.springer.com/journal/10867)","snPcode":"10867","submissionUrl":"https://submission.nature.com/new-submission/10867/3","title":"Journal of Biological Physics","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"e8338515-b26e-400f-ae50-39491a96aaf9","owner":[],"postedDate":"April 10th, 2026","published":true,"recentEditorialEvents":[{"type":"editorInvitedReview","content":"","date":"2026-05-13T23:32:27+00:00","index":18,"fulltext":""},{"type":"editorInvitedReview","content":"","date":"2026-04-30T16:59:41+00:00","index":17,"fulltext":""}],"rejectedJournal":[],"revision":"","amendment":"","status":"under-review","subjectAreas":[],"tags":[],"updatedAt":"2026-04-10T20:18:49+00:00","versionOfRecord":[],"versionCreatedAt":"2026-04-10 20:18:49","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-9307584","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-9307584","identity":"rs-9307584","version":["v1"]},"buildId":"XKTyCvWXoU3ODBz1xrDgd","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}