On the Holographic Geometry of Deterministic Computation

• URL: http://arxiv.org/abs/2512.00607v2
• Date: Fri, 05 Dec 2025 03:53:46 GMT
• Title: On the Holographic Geometry of Deterministic Computation
• Authors: Logan Nye,
• Abstract summary: 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 at time $t$.<n>We show that any length-$t$ run can be simulated using $O(sqrtt)$ work-tape cells via a Height Compression Theorem for succinct trees together with an Algebraic Replay Engine.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Quantifying Memory Use in Reinforcement Learning with Temporal Range [51.98491034847041]
  Temporal Range is a model-agnostic metric that treats first-order sensitivities of multiple vector outputs across a temporal window to the input sequence as a temporal influence profile.<n>We also report Temporal Range for a compact Long Expressive Memory (LEM) policy trained on the task, using it as a proxy readout of task-level memory.
  arXiv  Detail & Related papers  (2025-12-05T22:58:09Z)
• Accelerated Evolving Set Processes for Local PageRank Computation [75.54334100808022]
  This work proposes a novel framework based on nested evolving set processes to accelerate Personalized PageRank computation.<n>We show that the time complexity of such localized methods is upper bounded by $mintildemathcalO(R2/epsilon2), tildemathcalO(m)$ to obtain an $epsilon$-approximation of the PPR vector.
  arXiv  Detail & Related papers  (2025-10-09T09:47:40Z)
• HGE: Embedding Temporal Knowledge Graphs in a Product Space of Heterogeneous Geometric Subspaces [31.808046956138757]
  Temporal knowledge graphs represent temporal facts $(s,p,o,tau)$ relating a subject $s$ and an object $o$ at time $tau$, where $tau$ could be a time point or time interval. We propose an embedding approach that maps temporal facts into a product space of several heterogeneous geometric subspaces with distinct geometric properties.
  arXiv  Detail & Related papers  (2023-12-21T09:04:30Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure. We introduce a new class of manifold, named soft manifold, that can solve this situation. Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
  arXiv  Detail & Related papers  (2023-11-29T12:48:33Z)
• On the Representational Capacity of Recurrent Neural Language Models [56.19166912044362]
  We show that a rationally weighted RLM with computation time can simulate any deterministic probabilistic Turing machine (PTM) with rationally weighted transitions. We also provide a lower bound by showing that under the restriction to real-time computation, such models can simulate deterministic real-time rational PTMs.
  arXiv  Detail & Related papers  (2023-10-19T17:39:47Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Learning Transition Operators From Sparse Space-Time Samples [11.859913430860335]
  We consider the nonlinear problem of learning a transition operator $mathbfA$ from partial observations at different times. We show that no more than $mathcalOrn log(nT)$ space-time samples are sufficient to ensure accurate recovery of a rank-$r$ operator.
  arXiv  Detail & Related papers  (2022-12-01T18:33:59Z)
• Fast Stabiliser Simulation with Quadratic Form Expansions [0.8122270502556371]
  This is a representation of a quantum state which specifies a formula for the expansion in the standard basis. We show how, with deft management of the quadratic form expansion representation, we may simulate individual stabiliser operations in $O(n2)$ time.
  arXiv  Detail & Related papers  (2021-09-17T16:17:21Z)
• Abstract Geometrical Computation 11: Slanted Firing Squad Synchronisation on Signal Machines [0.0]
  Firing Squad Synchronisation on Cellular Automata is the dynamical synchronisation of finitely many cells without any prior knowledge of their range. Most of the proposed constructions naturally translate to the continuous setting of signal machines. This paper provides basic tools for further study of computable accumulation lines in the signal machine model.
  arXiv  Detail & Related papers  (2021-06-21T15:15:01Z)
• Space-filling Curves for High-performance Data Mining [0.0]
  Space-filling curves like the Hilbert-curve, Peano-curve and Z-order map natural or real numbers from a two or higher dimensional space to a one dimensional space preserving locality. They have numerous applications like search structures, computer graphics, numerical simulation, cryptographics and can be used to make various algorithms cache-oblivious.
  arXiv  Detail & Related papers  (2020-08-04T16:41:16Z)
• Spatial Pyramid Based Graph Reasoning for Semantic Segmentation [67.47159595239798]
  We apply graph convolution into the semantic segmentation task and propose an improved Laplacian. The graph reasoning is directly performed in the original feature space organized as a spatial pyramid. We achieve comparable performance with advantages in computational and memory overhead.
  arXiv  Detail & Related papers  (2020-03-23T12:28:07Z)
• Linear-time inference for Gaussian Processes on one dimension [17.77516394591124]
  We investigate data sampled on one dimension for which state-space models are popular due to their linearly-scaling computational costs. We provide the first general proof of conjecture that state-space models are general, able to approximate any one-dimensional Gaussian Processes. We develop parallelized algorithms for performing inference and learning in the LEG model, test the algorithm on real and synthetic data, and demonstrate scaling to datasets with billions of samples.
  arXiv  Detail & Related papers  (2020-03-11T23:20:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.