論文の概要: Constant Bit-size Transformers Are Turing Complete

• arxiv url: http://arxiv.org/abs/2506.12027v1
• Date: Thu, 22 May 2025 02:45:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-22 23:32:14.587369
• Title: Constant Bit-size Transformers Are Turing Complete
• Title（参考訳）: ビットサイズの定型変圧器が完成
• Authors: Qian Li, Yuyi Wang,
• Abstract要約: 任意の長さの入力で動くチューリングマシンは、定ビットサイズの変圧器でシミュレートできることを示す。 提案手法は,チューリング完全計算モデルであるPostマシンのシミュレーションに依存する。
• 参考スコア（独自算出の注目度）: 8.38684825915246
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove that any Turing machine running on inputs of arbitrary length can be simulated by a constant bit-size transformer, as long as the context window is sufficiently long. This improves previous works, which require scaling up either the model's precision or the number of parameters on longer inputs. Furthermore, we prove that the complexity class SPACE$[s(n)]$ exactly characterizes the expressive power of a constant bit-size transformer with a context window of length $s(n)$. Our approach relies on simulating Post machines, a Turing-complete computational model. Post machines can be modeled as automata equipped with a queue, exhibiting computational behaviors naturally aligned with those of transformers. The behavioral similarity between transformers and Post machines may offer new insights into the mechanisms underlying the reasoning abilities of transformers.
• Abstract（参考訳）: 任意の長さの入力上で動作するチューリングマシンは、コンテキストウィンドウが十分に長い限り、一定ビットサイズの変圧器でシミュレートできることを示す。 これは以前の作業を改善し、モデルの精度や長い入力におけるパラメータの数をスケールアップする必要がある。 さらに、複雑性クラスSPACE$[s(n)]$が、長さ$s(n)$のコンテキストウィンドウを持つ定数ビットサイズの変圧器の表現力を正確に特徴付けることを証明している。 提案手法は,チューリング完全計算モデルであるPostマシンのシミュレーションに依存する。 ポストマシンはキューを備えたオートマタとしてモデル化することができ、トランスフォーマーのものと自然に一致した計算挙動を示す。 変圧器とポストマシンの挙動類似性は、変圧器の推論能力の基礎となるメカニズムに新たな洞察を与える可能性がある。

関連論文リスト

• On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning [87.73401758641089]
  CoT推論による現代言語モデル(LM)の性能向上 LMは弦上の分布の族を確率的チューリングマシンと同一に表現できることを示す。
  論文  参考訳（メタデータ） (2024-06-20T10:59:02Z)
• Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers [8.908747084128397]
  時間カウントロジックの $textsfK_textt$[#] と RASP の $textsfC-RASP$ を紹介します。 それらが互いに等価であることを示し、それらが結合されていない入力サイズを持つ将来のマスキング型ソフトアテンショントランスの形式的表現性に最もよく知られた下界であることを示す。
  論文  参考訳（メタデータ） (2024-04-05T20:36:30Z)
• Simulating Weighted Automata over Sequences and Trees with Transformers [5.078561931628571]
  DFAを仮定するモデルのクラスである重み付き有限オートマトン (WFAs) と重み付き木オートマトン (WTA) をシミュレートできることを示す。 我々はこれらの主張を正式に証明し、ターゲットオートマタの状態数の関数として必要とされる変換器モデルのサイズについて上限を与える。
  論文  参考訳（メタデータ） (2024-03-12T21:54:34Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。 この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
  論文  参考訳（メタデータ） (2024-02-20T10:11:03Z)
• The Expressive Power of Transformers with Chain of Thought [29.839710738657203]
  実際には、トランスフォーマーは「思考の連鎖」や「スクラッチパッド」を使用することで改善できる。 答えはYESであるが、増加量は中間生成量に大きく依存する。 また, 線形ステップでは, コンテクストに敏感な言語に変換器デコーダを配置することが示唆された。
  論文  参考訳（メタデータ） (2023-10-11T22:35:18Z)
• How Powerful are Decoder-Only Transformer Neural Models? [0.0]
  GPT-xで採用されている基礎技術のチューリング完全性に対処する最初の研究である。 単語埋め込みの空間性/圧縮性はチューリング完全性を維持する上で重要な考慮事項であることを示す。
  論文  参考訳（メタデータ） (2023-05-26T15:35:43Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  低深度変換器は任意の有限状態オートマトンを計算できる。 我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。 さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
  論文  参考訳（メタデータ） (2022-10-19T17:45:48Z)
• The Parallelism Tradeoff: Limitations of Log-Precision Transformers [29.716269397142973]
  入力トークン数における算術精度が対数的である変換器は、定数深さの対数空間一様しきい値回路でシミュレートできることを示す。 これは、複雑性理論の既知の結果を用いた変圧器のパワーに関する洞察を与える。
  論文  参考訳（メタデータ） (2022-07-02T03:49:34Z)
• Linearizing Transformer with Key-Value Memory Bank [54.83663647680612]
  我々は、ソースシーケンスを低次元表現に投影するアプローチであるMemSizerを提案する。 MemSizerは同じ線形時間複雑性を達成するだけでなく、効率的なリカレントスタイルの自己回帰生成も楽しめる。 我々はMemSizerがバニラ変圧器の効率と精度のトレードオフを改善することを実証した。
  論文  参考訳（メタデータ） (2022-03-23T18:10:18Z)
• Thinking Like Transformers [64.96770952820691]
  本稿では,プログラミング言語の形式で変換器エンコーダの計算モデルを提案する。 RASPは、トランスフォーマーによって確実に学習できるタスクの解決策をプログラムするのにどのように使えるかを示す。 ヒストグラム、ソート、ダイク言語のためのRASPプログラムを提供する。
  論文  参考訳（メタデータ） (2021-06-13T13:04:46Z)
• Addressing Some Limitations of Transformers with Feedback Memory [51.94640029417114]
  トランスフォーマーは、フィードフォワードネットワークであるにもかかわらず、シーケンシャルな自動回帰タスクにうまく適用されている。 本稿では、過去のすべての表現を将来のすべての表現に公開する、フィードバックトランスフォーマーアーキテクチャを提案する。 言語モデリング、機械翻訳、強化学習の様々なベンチマークにおいて、表現能力の増大は、同等のトランスフォーマーよりもはるかに強力なパフォーマンスを持つ、小さくて浅いモデルを生成することができることを実証する。
  論文  参考訳（メタデータ） (2020-02-21T16:37:57Z)

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

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