On the Holographic Geometry of Deterministic Computation

Logan Nye, MD · 2025

Read On the Holographic Geometry of Deterministic Computation by Logan Nye, MD (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-00607.txt.

Introduction

Simulating a Turing machine raises a basic question: how much information must be stored to certify a moment of its run? Logan Nye studies the holographic geometry of deterministic computation in 2025. Standard simulations suggest a linear relationship between a run's duration and the storage needed.

Certifying, verifying, or regenerating the configuration at a given time are the tasks Nye measures. A holographic viewpoint, borrowed from physics, asks whether the run's history can be encoded on a smaller boundary-like structure. The question links computability theory to information geometry in an unusual way. The holographic phrasing borrows from physics, where bulk information lives on a boundary. Deterministic computation is the cleanest setting for such storage questions.

Catalog record

CREATORLogan Nye, MD
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-00607

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Holographic Geometry of Deterministic Computation Logan Nye, MD Abstract Abstract Standard simulations of Turing machines suggest a linear relationship between the temporal duration t of a run and the amount of information that must be stored by known simulations to certify, verify, or regenerate the configuration at time t . For deterministic multitape Turing machines over a fixed finite alphabet, this apparent linear dependence is not intrinsic: any length- t run can be simulated using O(\sqrt{t}) work-tape cells via a Height Compression Theorem for succinct computation trees together with an Algebraic Replay Engine. In this paper we recast that construction in geometric and information-theoretic language. We interpret the execution trace as a spacetime DAG of local update events and exhibit a family of recursively defined holographic boundary summaries such that, along the square-root-space simulation, the total description length of all boundary data stored at any time is O(\sqrt{t}) . Using Kolmogorov complexity, we prove that every internal configuration has constant conditional description complexity given the appropriate boundary summary and time index, establishing that the spacetime bulk carries no additional algorithmic information beyond its boundary. We express this as a one-dimensional computational area law : there exists a simulation in which the information capacity of the active “holographic screen” needed to generate a spacetime region of volume proportional to t is bounded by O(\sqrt{t}) . In this precise sense, deterministic computation on a one-dimensional work tape admits a holographic representation, with the bulk history algebraically determined by data residing on a lower-dimensional boundary screen. 1 Introduction The tradeoff between deterministic time and space on Turing machines is a foundational theme in complexity theory, with a long history of upper and lower bounds relating these resources [ 1 , 2 , 3 ] . Together with classical simulations such as Savitch’s theorem relating nondeterministic and deterministic space [ 4 ] , these results establish that many natural problems admit nontrivial transformations between time and space bounds. More recently, for deterministic multitape Turing machines it has been shown that a time- t computation can be simulated in space O\!\bigl(\sqrt{t\log t}\bigr) [ 5 ] , sharpening the classical O(t/\log t) bound. In a companion work (henceforth Height Compression ) we prove a stronger square-root space simulation theorem \mathrm{TIME}[t]\;\subseteq\;\mathrm{SPACE}\bigl(O(\sqrt{t})\bigr) for deterministic multitape Turing machines, where space is measured in tape cells over a fixed finite alphabet [ 6 ] . The proof proceeds via three ingredients: a Height Compression Theorem for succinct computation trees, an Algebraic Replay Engine that regenerates local configurations from short summaries, and a rolling boundary discipline for traversing the compressed tree. Informally, the companion paper shows that the entire computation history of a deterministic run can be regenerated from a carefully chosen sequence of low-dimensional boundary summaries , using only O(\sqrt{t}) active tape cells at any moment. The present paper develops a geometric and information-theoretic interpretation of this phenomenon. We treat the execution of a deterministic machine not only as a linear sequence of configurations, but as a finite directed acyclic graph (DAG) that we regard as a discrete spacetime object, equipped with a combinatorial notion of locality induced by the machine’s transition rules. We then reinterpret the technical machinery of height compression in geometric language: • We repackage the interval summaries of height compression as holographic boundary states that encode all information flowing into and out of a spacetime sub-region. • We reinterpret the height-compressed computation tree as a static causal tree of spacetime volumes, on which linear time appears as a particular depth-first traversal. • We define an active holographic screen consisting of the boundary states and local replay window maintained by the simulator, and we show that its size satisfies a one-dimensional area law: the maximum screen size over the run is O(\sqrt{t}) . On top of these formal correspondences, we prove a precise information-theoretic statement: the bulk of the spacetime object has O(1) conditional Kolmogorov complexity relative to its boundary summaries. That is, once the machine and the boundary data of a block are fixed, any internal configuration can be produced by a fixed, constant-complexity procedure. In this sense, the interior of a deterministic computation history is an information-theoretic vacuum : all nontrivial information resides in its boundary data, and the bulk is an algebraically determined evaluation trace. Finally, we formulate conjectural extensions of the area law to higher-dimensional memory architectures, and we discuss analogies with holography in quantum gravity and with area laws for entanglement in many-body systems [ 8 , 9 , 10 , 11 , 12 ] . We distinguish carefully between rigorous theorems (which are purely combinatorial and information-theoretic) and speculative analogies. 2 Preliminaries from Height Compression We briefly recall the core constructions from the height-compression technique, specializing to the aspects needed for the present work. For background on standard models of computation and complexity-theoretic notation, see, e.g., [ 3 ] . For Kolmogorov complexity and encoding conventions, we follow [ 7 ] and make our choices explicit in Appendix A . 2.1 Machine model and spacetime diagram We fix a deterministic multitape Turing machine M=(Q,\Sigma,\Gamma,\delta,q_{0},q_{\mathrm{acc}},q_{\mathrm{rej}}), with finite state set Q , input alphabet \Sigma , work alphabet \Gamma\supseteq\Sigma , and transition function \delta:Q\times\Gamma^{k}\to Q\times\Gamma^{k}\times\{-1,0,+1\}^{k} for some fixed number of tapes k\geq 1 . We assume the standard Lipschitz locality of head motion: in one time step, each head moves by at most one cell. A run of M of length t is a sequence of configurations C_{0},C_{1},\dots,C_{t}, where each C_{\tau} encodes the tape contents, head positions, and control state at time \tau . The spacetime diagram of the run is the finite directed acyclic graph \mathcal{M}_{\mathrm{raw}}=(V,E), where V consists of all local degrees of freedom (e.g., tape cells with time labels and the control state) and E consists of directed edges representing the causal dependencies induced by \delta between consecutive configurations. For standard one-dimensional tapes we have V\subseteq\mathbb{Z}^{1+1} ; more generally one may consider higher-dimensional tape lattices. We will colloquially refer to \mathcal{M}_{\mathrm{raw}} as a “spacetime manifold”, but for our purposes it is simply a finite DAG equipped with the adjacency relation defined by \delta . 2.2 Block-respecting runs and time-blocks Fix a block size parameter b\in\mathbb{N} . We partition the time indices \{1,\dots,t\} into T=\lceil t/b\rceil contiguous time-blocks I_{k}=\bigl[(k-1)b+1,\,\min\{kb,t\}\bigr]\quad\text{for }k=1,\dots,T. We will use the following notion of block locality, which is the one realized by the height-compression construction in [ 6 ] . Definition 1 (Block-respecting run) . Let b\in\mathbb{N} and let c_{\mathrm{int}}\geq 1 be a fixed constant. A length- t run of M is block-respecting with parameters (b,c_{\mathrm{int}}) if, for every time-block I_{k} , all interactions between the computation inside I_{k} and the rest of the run occur through an interface window of size at most c_{\mathrm{int}}\cdot b on the work tape, located in the spacelike slices at the temporal boundaries of I_{k} . Concretely, the interface for I_{k} consists of: • the machine state and head positions at the entry and exit times of I_{k} , and • the contents of an interval of at most c_{\mathrm{int}}\cdot b tape cells containing all cells visited by the heads during I_{k} . The Height Compression paper [ 6 ] shows that for suitably chosen b (as a function of

Read the complete text