論文の概要: 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) - The Expressive Power of Transformers with Chain of Thought [29.839710738657203]
実際には、トランスフォーマーは「思考の連鎖」や「スクラッチパッド」を使用することで改善できる。
答えはYESであるが、増加量は中間生成量に大きく依存する。
また, 線形ステップでは, コンテクストに敏感な言語に変換器デコーダを配置することが示唆された。
論文 参考訳（メタデータ） (2023-10-11T22:35:18Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。