論文の概要: On the Holographic Geometry of Deterministic Computation
- arxiv url: http://arxiv.org/abs/2512.00607v1
- Date: Sat, 29 Nov 2025 19:47:22 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-12-02 19:46:34.321377
- Title: On the Holographic Geometry of Deterministic Computation
- Title（参考訳）: 決定論的計算のホログラフィー幾何学について
- Authors: Logan Nye,
- Abstract要約: チューリングマシンの標準的なシミュレーションは、実行時間$t$と時間$t$で格納しなければならない情報の量との間の線形関係を示唆している。
固定有限アルファベット上の決定論的マルチテープチューリングマシンでは、この明らかな線形依存は本質的ではない。
任意の長さ$t$のランは、アルジェブラリックエンジンとともに簡潔な木に対するハイト圧縮定理を介して、空間$O(sqrtt)$でシミュレートできることを示す。
- 参考スコア（独自算出の注目度）: 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 in space $O(\sqrt{t})$ 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 dependency DAG 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 $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.
- Abstract（参考訳）: チューリングマシンの標準的なシミュレーションは、実行時間$t$と既知のシミュレーションによって保持されなければならない情報の量との間の線形関係を示唆している。
固定有限アルファベット上の決定論的マルチテープチューリングマシンの場合、この明らかな線形依存は本質的ではない:任意の長さ=$t$ランは空間$O(\sqrt{t})$でシミュレートできる。
本稿では,その構成を幾何学的および情報論的言語で再放送する。
我々は、実行トレースを時空依存性DAGとして解釈し、再帰的に定義されたホログラフィック境界要約の族を示し、平方根空間シミュレーションにより、任意の時刻に格納されたすべての境界データの総記述長が$O(\sqrt{t})$であることを示す。
コルモゴロフ複雑性を用いて、任意の内部構成が適切な境界の要約と時間指数から一定の条件記述複雑性を持つことを証明し、時空バルクはその境界を超える追加のアルゴリズム情報を持たないことを証明した。
体積$t$の時空領域を生成するのに必要なアクティブな「ホログラフィックスクリーン」の情報容量を$O(\sqrt{t})$で束縛するシミュレーションが存在する。
この正確な意味では、一次元ワークテープ上の決定論的計算はホログラフィック表現を認め、そのバルク履歴は低次元境界画面上のデータによって代数的に決定される。
関連論文リスト
- Accelerated Evolving Set Processes for Local PageRank Computation [75.54334100808022]
この研究は、パーソナライズされたPageRank計算を高速化するために、ネストした進化したセットプロセスに基づく新しいフレームワークを提案する。
このような局所化手法の時間複雑性は、PPRベクトルの$epsilon$-approximationを得るために$mintildemathcalO(R2/epsilon2), tildemathcalO(m)$によって上界となることを示す。
論文 参考訳（メタデータ） (2025-10-09T09:47:40Z) - HGE: Embedding Temporal Knowledge Graphs in a Product Space of
Heterogeneous Geometric Subspaces [31.808046956138757]
時間的知識グラフは時間的事実を表す。 $(s,p,o,tau)$ 主題 $s$ とオブジェクト $o$ at time $tau$。
本稿では,時間的事実を,異なる幾何学的性質を持つ不均一な幾何部分空間の積空間にマッピングする埋め込み手法を提案する。
論文 参考訳（メタデータ） (2023-12-21T09:04:30Z) - Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
グラフ埋め込みの信頼性は、連続空間の幾何がグラフ構造とどの程度一致しているかに依存する。
我々は、この問題を解決することができる、ソフト多様体と呼ばれる新しい多様体のクラスを導入する。
グラフ埋め込みにソフト多様体を用いることで、複雑なデータセット上のデータ解析における任意のタスクを追求するための連続空間を提供できる。
論文 参考訳（メタデータ） (2023-11-29T12:48:33Z) - Abstract Geometrical Computation 11: Slanted Firing Squad
Synchronisation on Signal Machines [0.0]
セルオートマタ上のスクワッドシンクロナイゼーションのフィリング(Firing Squad Synchronization)は、その範囲について事前の知識を持たない有限個のセルの動的シンクロナイゼーションである。
提案された構成の多くは自然に信号機の連続的な設定に翻訳される。
本稿では,信号機械モデルにおける計算可能蓄積ラインのさらなる研究のための基本的なツールを提供する。
論文 参考訳（メタデータ） (2021-06-21T15:15:01Z) - Space-filling Curves for High-performance Data Mining [0.0]
ヒルベルト曲線、ペアノ曲線、Z次曲線のような空間充填曲線は、2次元以上の空間から局所性を保存する一次元空間への自然あるいは実数の写像である。
検索構造、コンピュータグラフィックス、数値シミュレーション、暗号など多くの応用があり、様々なアルゴリズムをキャッシュオフブロードすることができる。
論文 参考訳（メタデータ） (2020-08-04T16:41:16Z) - Spatial Pyramid Based Graph Reasoning for Semantic Segmentation [67.47159595239798]
セマンティックセグメンテーションタスクにグラフ畳み込みを適用し、改良されたラプラシアンを提案する。
グラフ推論は、空間ピラミッドとして構成された元の特徴空間で直接実行される。
計算とメモリのオーバーヘッドの利点で同等のパフォーマンスを実現しています。
論文 参考訳（メタデータ） (2020-03-23T12:28:07Z) - Linear-time inference for Gaussian Processes on one dimension [17.77516394591124]
本研究では,その線形スケーリング計算コストから,状態空間モデルが人気である1次元のサンプルデータについて検討する。
状態空間モデルは一般であり、任意の1次元ガウス過程を近似できるという予想の最初の一般的な証明を提供する。
LEGモデルで推論と学習を行う並列アルゴリズムを開発し、実データおよび合成データ上でアルゴリズムをテストし、数十億のサンプルを持つデータセットへのスケーリングを実証する。
論文 参考訳（メタデータ） (2020-03-11T23:20:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。