論文の概要: Counting Short Trajectories in Elementary Cellular Automata using the Transfer Matrix Method
- arxiv url: http://arxiv.org/abs/2508.09768v1
- Date: Wed, 13 Aug 2025 12:53:22 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-14 20:42:00.890067
- Title: Counting Short Trajectories in Elementary Cellular Automata using the Transfer Matrix Method
- Title（参考訳）: 移動行列法による小細胞オートマトン中の短い軌跡の計数
- Authors: Cédric Koller, Barbora Hudcová,
- Abstract要約: 初等細胞オートマタ(ECA)は、ウルフラムの質的な分類によって分類される様々な行動を示す。
限られた時間ステップで短いアトラクタに繋がる全ての構成数を計算できる手法について述べる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Elementary Cellular Automata (ECAs) exhibit diverse behaviours often categorized by Wolfram's qualitative classification. To provide a quantitative basis for understanding these behaviours, we investigate the global dynamics of such automata and we describe a method that allows us to compute the number of all configurations leading to short attractors in a limited number of time steps. This computation yields exact results in the thermodynamic limit (as the CA grid size grows to infinity), and is based on the Transfer Matrix Method (TMM) that we adapt for our purposes. Specifically, given two parameters $(p, c)$ we are able to compute the entropy of all initial configurations converging to an attractor of size $c$ after $p$ time-steps. By calculating such statistics for various ECA rules, we establish a quantitative connection between the entropy and the qualitative Wolfram classification scheme. Class 1 rules rapidly converge to maximal entropy for stationary states ($c=1$) as $p$ increases. Class 2 rules also approach maximal entropy quickly for appropriate cycle lengths $c$, potentially requiring consideration of translations. Class 3 rules exhibit zero or low finite entropy that saturates after a short transient. Class 4 rules show finite positive entropy, similar to some Class 3 rules. This method provides a precise framework for quantifying trajectory statistics, although its exponential computational cost in $p+c$ restricts practical analysis to short trajectories.
- Abstract（参考訳）: 初等細胞オートマタ(ECA)は、ウルフラムの質的な分類によって分類される様々な行動を示す。
これらの振る舞いを定量的に理解するために,このようなオートマトンのグローバルなダイナミクスを考察し,限られた時間ステップでアトラクタを短くする全ての構成の数を計算できる手法について述べる。
この計算は熱力学的限界(CAグリッドのサイズが無限大に大きくなるにつれて)の正確な結果をもたらし、我々の目的に適応する転送行列法(TMM)に基づいている。
具体的には、2つのパラメータ $(p, c)$ が与えられたとき、私たちはすべての初期設定のエントロピーを計算し、$c$ のアトラクタを $p$ のタイムステップで処理することができる。
様々なECA規則に対するそのような統計量を計算することにより、エントロピーと定性的ウルフラム分類スキームの間の定量的な関係を確立する。
クラス1の規則は、p$が増加するにつれて、定常状態(c=1$)の最大エントロピーに急速に収束する。
クラス2のルールは、適切なサイクル長に対して素早く最大エントロピーにアプローチし、翻訳の考慮を必要とする可能性がある。
クラス3の規則は、短周期の後に飽和するゼロまたは低い有限エントロピーを示す。
クラス4の規則は、クラス3の規則と同様、有限正のエントロピーを示す。
この方法では、軌跡統計を定量化するための正確なフレームワークを提供するが、その指数計算コスト$p+c$は、短い軌跡に実用的な解析を制限している。
関連論文リスト
- Efficient Implementation of Gaussian Process Regression Accelerated Saddle Point Searches with Application to Molecular Reactions [39.58317527488534]
本稿では,最小モード追従法のガウス過程回帰加速度の効率的な実装について述べる。
鞍点配置に到達するために必要な電子構造計算の桁数を求める。
C++におけるGPRサロゲートモデルの実装は、サドル点探索のウォールタイムを4つのケースのうち3つに抑えるのに十分な効率である。
論文 参考訳（メタデータ） (2025-05-18T18:42:55Z) - Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
本稿では、よく知られたトランスフォーマーアーキテクチャを基盤とした、ランクの新たな特徴付けについて述べる。
関数 $f$ のランクは、単一層変換器が要求する思考ステップの EmphChain の最小値に対応していることを示す。
また、マルチヘッド単一層トランスをキャプチャするマルチヘッドランクの概念を導入し、有界なマルチヘッドランクを持つ関数クラスのPAC学習性の解析を行う。
論文 参考訳（メタデータ） (2025-01-22T16:30:58Z) - Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。
提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。
そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
論文 参考訳（メタデータ） (2024-05-14T15:28:37Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Classical and Quantum Computing of Shear Viscosity for $2+1D$ SU(2) Gauge Theory [0.0]
我々は、$(2+1)$-dimensional SU(2)ゲージ理論に対するせん断粘度の非摂動計算を行う。
せん断粘度とエントロピー密度$fracetas$の比は、よく知られたホログラフィック結果と一致している。
本研究では,グリーン関数の量子計算法を開発し,計算の系統的特徴を解析する。
論文 参考訳（メタデータ） (2024-02-06T18:25:41Z) - Lower Complexity Adaptation for Empirical Entropic Optimal Transport [0.0]
エントロピック最適輸送(EOT)は、非正規化最適輸送(OT)に代わる有効で計算可能な代替手段を示す
EOTコストの実証的なプラグイン推定のための新しい統計的境界を導出する。
この手法は経験的プロセス理論を用いており、単一関数クラス上の EOT の二重定式化に依存している。
論文 参考訳（メタデータ） (2023-06-23T16:06:13Z) - Entanglement Production and Convergence Properties of the Variational
Quantum Eigensolver [0.0]
本研究では,2次元モデルフェルミオン系の基底状態エネルギーを決定するために,変分量子固有解法(VQE)アルゴリズムを用いる。
特に,システム基底状態への最も効率的な収束を提供するエンタングルブロックの性質に着目する。
誤差の範囲内で解に到達するのに必要なゲートの数は、Solovay-Kitaevスケールに従っていることを示す。
論文 参考訳（メタデータ） (2020-03-27T15:44:56Z) - Simulation of Thermal Relaxation in Spin Chemistry Systems on a Quantum
Computer Using Inherent Qubit Decoherence [53.20999552522241]
我々は,実世界の量子システムの振舞いをシミュレーションする資源として,キュービットデコヒーレンスを活用することを目指している。
熱緩和を行うための3つの方法を提案する。
結果,実験データ,理論的予測との間には,良好な一致が得られた。
論文 参考訳（メタデータ） (2020-01-03T11:48:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。