論文の概要: Efficient Turing Machine Simulation with Transformers

• arxiv url: http://arxiv.org/abs/2512.00003v2
• Date: Tue, 02 Dec 2025 03:55:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-07 19:06:32.370403
• Title: Efficient Turing Machine Simulation with Transformers
• Title（参考訳）: 変圧器を用いた効率的なチューリングマシンシミュレーション
• Authors: Qian Li, Yuyi Wang,
• Abstract要約: 定ビットサイズ変換器はチューリング完全であることが知られている。 既存の構成には、シミュレーションされたチューリングマシンステップ当たりの$(s(n))$チェーン・オブ・シントステップが必要である。 我々は任意の$(t(n),s(n)$-bounded multi-tape TM が定数ビットサイズ変換器でシミュレート可能であることを証明した。
• 参考スコア（独自算出の注目度）: 6.70318953627082
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Constant bit-size Transformers are known to be Turing complete, but existing constructions require $Ω(s(n))$ chain-of-thought (CoT) steps per simulated Turing machine (TM) step, leading to impractical reasoning lengths. In this paper, we significantly reduce this efficiency gap by proving that any $(t(n),s(n))$-bounded multi-tape TM can be simulated by a constant bit-size Transformer with an optimal $O(s(n))$-long context window and only $O(s(n)^c)$ CoT steps per TM step, where $c>0$ can be made arbitrarily small by letting the Transformers' head-layer product sufficiently large. In addition, our construction shows that sparse attention with fixed geometric offsets suffices for efficient universal computation. Our proof leverages multi-queue TMs as a bridge. The main technical novelty is a more efficient simulation of multi-tape TMs by synchronous multi-queue TMs, improving both time and space complexity under stricter model assumptions.
• Abstract（参考訳）: 定ビットサイズ変換器はチューリング完全であることが知られているが、既存の構成ではシミュレーションチューリングマシン(TM)のステップあたり$Ω(s(n))$ chain-of- Thought (CoT) を必要とするため、非現実的な推論長が生じる。 本稿では,任意の$(t(n),s(n))$-bounded multi-tape TM が,最適な$O(s(n))$-longコンテキストウィンドウと$O(s(n)^c)$ CoT ステップしか持たない一定ビットサイズの変換器でシミュレートできることを証明し,効率ギャップを著しく低減する。 さらに, 固定幾何オフセットによるスパースアテンションは, 効率的な普遍計算に十分であることを示す。 本稿では,マルチキューTMをブリッジとして活用する。 主な技術的新規性は、同期マルチキューTMによるマルチテープTMのより効率的なシミュレーションであり、より厳密なモデル仮定の下で時間と空間の複雑さを改善する。

関連論文リスト

• Constant Bit-size Transformers Are Turing Complete [6.70318953627082]
  任意の長さの入力で動くチューリングマシンは、定ビットサイズの変圧器でシミュレートできることを示す。 提案手法は,チューリング完全計算モデルであるPostマシンのシミュレーションに依存する。
  論文  参考訳（メタデータ） (2025-05-22T02:45:38Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。 この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
  論文  参考訳（メタデータ） (2024-02-20T10:11:03Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  低深度変換器は任意の有限状態オートマトンを計算できる。 我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。 さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
  論文  参考訳（メタデータ） (2022-10-19T17:45:48Z)
• Block-Recurrent Transformers [49.07682696216708]
  本稿では,逐次的にトランス層を適用するBlock-Recurrent Transformerを提案する。 我々のリカレントセルはシングルトークンではなくトークンブロック上で動作し、アクセルハードウェアを効率的に活用するためにブロック内の並列計算を利用する。
  論文  参考訳（メタデータ） (2022-03-11T23:44:33Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。