用全息边界数据还原计算过程,只需平方根级存储空间。
On the Holographic Geometry of Deterministic Computation
- 将计算轨迹转为时空有向无环图,用递归边界摘要压缩信息。
- 长度为t的计算仅需O(√t)空间即可完整重建中间状态。
- 适合研究计算复杂性与物理全息原理交叉的学者阅读。
标准图灵机模拟表明,运行时间t与所需存储信息量呈线性关系。但对于固定有限字母表上的确定性多带图灵机,这种线性依赖并非本质:任意长度为t的运行可通过高度压缩定理与代数重播引擎,仅用O(√t)工作带单元完成模拟。本文将其重构为几何与信息论语言:将执行轨迹视为局部更新事件的时空有向无环图(spacetime DAG),并构造一族递归定义的全息边界摘要。在平方根空间模拟中,任意时刻所存边界数据的总描述长度为O(√t)。通过柯尔莫哥洛夫复杂度证明,给定适当的边界摘要与时间索引后,任一内部配置的条件描述复杂度恒定,表明时空体部不携带额外算法信息。这体现为一维计算面积律:存在一种模拟,其生成体积正比于t的时空区域时,活跃‘全息屏’的信息容量被限制在O(√t)。在此精确意义上,一维工作带上的确定性计算具有全息表示,体部历史由低维边界数据代数决定。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。