Fugu-MT 論文翻訳(概要): Beyond the Turing threshold: Productive grammars generate essentially undecidable languages

論文の概要: Beyond the Turing threshold: Productive grammars generate essentially undecidable languages

arxiv url: http://arxiv.org/abs/2609.11385v1
Date: Thu, 10 Sep 2026 11:20:29 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-11 23:53:35.312543
Title: Beyond the Turing threshold: Productive grammars generate essentially undecidable languages
Title（参考訳）: チューリングしきい値を超えて:生産文法は本質的に決定不能な言語を生成する
Abstract要約: エミール・ポストの生産的集合は半計算可能ではなく、計算可能であり、本質的に計算不能である。私は自然数の生産的集合の構成をエミュレートする形式文法を設計し、従ってチューリング決定性を超えている。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by-sa/4.0/
Abstract: Emil Post's productive sets are not even semi-computable, let alone computable, being thus essentially incomputable. Accordingly, formal languages whose set of words is a (completely) productive set are essentially undecidable. In this article, I elaborate on Post productivity from the viewpoint of formal language theory: I design formal grammars that emulate the construction of productive sets of natural numbers and are thus beyond Turing-decidability.
Abstract（参考訳）: エミール・ポストの生産的集合は半計算可能ではなく、計算可能であり、本質的に計算不能である。したがって、単語の集合が(完全に)生産的な集合である形式言語は本質的に決定不可能である。本稿では、形式言語理論の観点から、ポスト生産性について詳述する: 私は、自然数の生産的集合の構成をエミュレートする形式文法を設計し、従ってチューリング決定性を超えた。

関連論文リスト

Complexity Theory of Randomised Testing [0.6999740786886536]
ソフトウェアテストにおけるランダムジェネレータの最初の複雑性理論の基礎を提示する。理論的に生成可能な言語は、エネルブル言語と正確に一致することを示す。これは、決定可能性の境界でのテストに直接的な意味を持つ。
論文参考訳（メタデータ） (2026-07-13T17:08:03Z)
Linguistic Productivity in Large Language Models: Models Coerce, but do not Preempt [5.856894361762095]
大規模言語モデルでは, コーカシオンの場合, 建設的生産性(エンクエンチメント)を保ちながら再現可能であることを示す。また、最も大きなモデルでさえ、新規言語に対する否定的な証拠を拡張できないことも示している。
論文参考訳（メタデータ） (2026-06-01T23:11:39Z)
Position: Natural Language Should Not Fully Replace Formal Languages [11.90605417129287]
自然言語はオープンな文脈における不特定に最適化されていると論じる。より厳密な要求のあるタスクでは形式言語が有利であるのに対して、自然言語は低特異性タスクで優れていることを示す。
論文参考訳（メタデータ） (2026-05-10T15:01:16Z)
Thinking Before Constraining: A Unified Decoding Framework for Large Language Models [1.2468700211588883]
自然生成と構造生成の両方の利点を組み合わせた簡単なアプローチを提案する。提案手法は,構造化された出力の信頼性を確保しつつ,自然言語推論の表現力を維持する。
論文参考訳（メタデータ） (2026-01-12T13:25:28Z)
Language Generation: Complexity Barriers and Implications for Learning [51.449718747429756]
単純でよく研究された言語ファミリであっても、成功した生成に必要なサンプルの数は極端に多いことが示される。これらの結果は、理論的可能性と効率的な学習可能性の間に大きなギャップがあることを明らかにする。
論文参考訳（メタデータ） (2025-11-07T23:06:48Z)
Unnatural Languages Are Not Bugs but Features for LLMs [92.8332103170009]
大規模言語モデル(LLM)は、ジェイルブレイクプロンプトなどの非可読テキストシーケンスを処理するために観察されている。我々はこの認識に挑戦する体系的な調査を行い、非自然言語にはモデルで使用可能な潜在的特徴が含まれていることを示した。
論文参考訳（メタデータ） (2025-03-02T12:10:17Z)
Linguistic Generalizations are not Rules: Impacts on Evaluation of LMs [13.700007279857081]
LMがいかにうまく一般化するかの言語学的評価は、自然言語は象徴的な規則によって生成されるという当然の事である。ここでは、LMが象徴的なルールに従わなかったことはバグではなく機能かもしれないことを示唆する。新しい発話は、柔軟性、相互関連性、文脈に依存した構成の組み合わせによって生成され、理解される。
論文参考訳（メタデータ） (2025-02-18T17:40:20Z)
Natural Language Embedded Programs for Hybrid Language Symbolic Reasoning [84.12154024070024]
本研究では,数学・記号的推論,自然言語理解,後続の課題に対処するための統合フレームワークとして,自然言語組み込みプログラム(NLEP)を提案する。我々のアプローチは,構造化知識の自然言語表現を含むデータ構造上の関数を定義する完全なPythonプログラムを生成するよう,言語モデルに促す。 Pythonインタープリタが生成されたコードを実行し、出力をプリントする。
論文参考訳（メタデータ） (2023-09-19T17:54:21Z)
Benchmarking Language Models for Code Syntax Understanding [79.11525961219591]
事前学習された言語モデルは、自然言語処理とプログラム理解の両方において素晴らしい性能を示している。本研究では,プログラムの構文構造を特定するための,最先端の事前訓練モデルの最初の徹底的なベンチマークを行う。この結果から,既存のプログラミング言語の事前学習手法の限界が指摘され,構文構造をモデル化することの重要性が示唆された。
論文参考訳（メタデータ） (2022-10-26T04:47:18Z)
On the Intersection of Context-Free and Regular Languages [71.61206349427509]
我々はBar-Hillel構造を一般化し、$varepsilon$-arcsで有限状態オートマトンを扱う。我々の構成が入力オートマトンと文法の両方の構造を符号化し、元の構成のサイズを維持した文法につながることを証明している。
論文参考訳（メタデータ） (2022-09-14T17:49:06Z)
Constrained Language Models Yield Few-Shot Semantic Parsers [73.50960967598654]
我々は,事前学習された大規模言語モデルの利用を,少ない意味論として検討する。意味構文解析の目標は、自然言語入力によって構造化された意味表現を生成することである。言語モデルを用いて、入力を英語に似た制御されたサブ言語にパラフレーズし、対象の意味表現に自動的にマッピングする。
論文参考訳（メタデータ） (2021-04-18T08:13:06Z)

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