論文の概要: Softmax Transformers are Turing-Complete
- arxiv url: http://arxiv.org/abs/2511.20038v1
- Date: Tue, 25 Nov 2025 08:08:39 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-26 17:37:04.352576
- Title: Softmax Transformers are Turing-Complete
- Title（参考訳）: ソフトマックス変換器はチューリングコンプリート
- Authors: Hongjian Jiang, Michael Hahn, Georg Zetzsche, Anthony Widjaja Lin,
- Abstract要約: 我々は、長さ一般化可能なソフトマックスCoT変換器がチューリング完全であることを証明した。
これは任意の言語に対してチューリング完全でないことを示す。
複雑な算術的推論を必要とする言語に対してトランスフォーマーを訓練することで、我々の理論を実証的に検証する。
- 参考スコア（独自算出の注目度）: 4.231989115090749
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Hard attention Chain-of-Thought (CoT) transformers are known to be Turing-complete. However, it is an open problem whether softmax attention Chain-of-Thought (CoT) transformers are Turing-complete. In this paper, we prove a stronger result that length-generalizable softmax CoT transformers are Turing-complete. More precisely, our Turing-completeness proof goes via the CoT extension of the Counting RASP (C-RASP), which correspond to softmax CoT transformers that admit length generalization. We prove Turing-completeness for CoT C-RASP with causal masking over a unary alphabet (more generally, for letter-bounded languages). While we show this is not Turing-complete for arbitrary languages, we prove that its extension with relative positional encoding is Turing-complete for arbitrary languages. We empirically validate our theory by training transformers for languages requiring complex (non-linear) arithmetic reasoning.
- Abstract（参考訳）: CoT変換器はチューリング完全であることが知られている。
しかし、ソフトマックスアテンション チェーン・オブ・ソート (CoT) 変換器がチューリング完全であるか否かは未解決の問題である。
本稿では,長さ一般化可能なソフトマックスCoT変換器がチューリング完全であることを示す。
より正確には、チューリング完全性証明は、長さ一般化を許容するソフトマックス CoT 変換器に対応するカウントリング RASP (C-RASP) のCoT拡張によって行われる。
CoT C-RASP のチューリング完全性は、単一アルファベット(より一般的には文字境界言語)を因果マスクで証明する。
これは任意の言語に対してチューリング完全でないことを示すが、相対的な位置符号化による拡張が任意の言語に対してチューリング完全であることを証明している。
複雑な(非線形な)算術的推論を必要とする言語に対して変換器を訓練することにより、我々の理論を実証的に検証する。
関連論文リスト
- Constant Bit-size Transformers Are Turing Complete [6.70318953627082]
任意の長さの入力で動くチューリングマシンは、定ビットサイズの変圧器でシミュレートできることを示す。
提案手法は,チューリング完全計算モデルであるPostマシンのシミュレーションに依存する。
論文 参考訳（メタデータ） (2025-05-22T02:45:38Z) - Universal Length Generalization with Turing Programs [24.077722969687898]
本稿では,アルゴリズムタスクをチューリングマシンを模倣するステップに分解する手法であるチューリングプログラムを提案する。
チューリングプログラムを用いることで,アルゴリズム的タスクの領域におけるロバストな長さの一般化が得られる。
次に,確率的チューリングプログラムにおいて,トランスフォーマーが長さ一般化を実現することを実証し,任意のアルゴリズムタスクに対して長さ一般化が可能であることを示唆する。
論文 参考訳（メタデータ） (2024-07-03T17:53:44Z) - On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning [87.73401758641089]
CoT推論による現代言語モデル(LM)の性能向上
LMは弦上の分布の族を確率的チューリングマシンと同一に表現できることを示す。
論文 参考訳（メタデータ） (2024-06-20T10:59:02Z) - Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。
この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
論文 参考訳（メタデータ） (2024-02-20T10:11:03Z) - How Powerful are Decoder-Only Transformer Neural Models? [0.0]
GPT-xで採用されている基礎技術のチューリング完全性に対処する最初の研究である。
単語埋め込みの空間性/圧縮性はチューリング完全性を維持する上で重要な考慮事項であることを示す。
論文 参考訳（メタデータ） (2023-05-26T15:35:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。