論文の概要: 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 のチューリング完全性は、単一アルファベット(より一般的には文字境界言語)を因果マスクで証明する。 これは任意の言語に対してチューリング完全でないことを示すが、相対的な位置符号化による拡張が任意の言語に対してチューリング完全であることを証明している。 複雑な(非線形な)算術的推論を必要とする言語に対して変換器を訓練することにより、我々の理論を実証的に検証する。

関連論文リスト

• Context-Free Recognition with Transformers [57.46376097734401]
  我々は、$mathcalO(log n)$ looping layerと$mathcalO(n6)$ padding tokensで全てのCFLを認識可能であることを示す。 実験の結果を実証的に検証し,対数深度を必要とする言語にループが有効であることを示す。
  論文  参考訳（メタデータ） (2026-01-05T03:14:23Z)
• Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization [53.89723291716722]
  AI推論に関する重要な問題は、モデルが学習した推論パターンを外挿して、より長いチェーン・オブ・シークレット(CoT)で難しいタスクを解決できるかどうかである。 状態追跡問題の代数構造が、学習されたCoTの外挿の度合いをいかに支配するかを数学的に証明する。 定数深度変換器はCoTで$mathsfNC1$-complete問題を確実に学習することを保証する。
  論文  参考訳（メタデータ） (2025-11-10T18:40:24Z)
• Constant Bit-size Transformers Are Turing Complete [6.70318953627082]
  任意の長さの入力で動くチューリングマシンは、定ビットサイズの変圧器でシミュレートできることを示す。 提案手法は,チューリング完全計算モデルであるPostマシンのシミュレーションに依存する。
  論文  参考訳（メタデータ） (2025-05-22T02:45:38Z)
• Ask, and it shall be given: On the Turing completeness of prompting [47.08833920586575]
  大規模言語モデル(LLM)は機械学習に革命をもたらし、いわゆるLLMプロンプトパラダイムを開始した。 本稿では, LLMプロンプトパラダイムに関する最初の理論的研究を, 我々の知識を最大限活用するために提示する。 有限サイズの変換器が存在し、計算可能な任意の関数に対して、変換器が関数を演算する対応するプロンプトが存在することを示す。
  論文  参考訳（メタデータ） (2024-11-04T11:26: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)
• 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)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)
• On the Computational Power of Transformers and its Implications in Sequence Modeling [10.497742214344855]
  特に、位置エンコーディング、アテンションヘッド、残差接続、フィードフォワードネットワークといったトランスフォーマーにおける様々なコンポーネントの役割は明確ではない。 バニラ変換器がチューリング完全であることを示すための代替的で単純な証明を提供する。 さらに、ネットワークのチューリング完全性に対する各コンポーネントの必要性を分析する。
  論文  参考訳（メタデータ） (2020-06-16T16:27:56Z)

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

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