論文の概要: Turing or Cantor: That is the Question

• arxiv url: http://arxiv.org/abs/2604.10418v1
• Date: Sun, 12 Apr 2026 02:33:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-14 20:13:16.003896
• Title: Turing or Cantor: That is the Question
• Title（参考訳）: チューリングかカントールか:それが質問だ
• Authors: Eugene Eberbach,
• Abstract要約: アーラン・チューリングの業績は、ゲオルク・カントールの初期の独創的な貢献なしには存在しないことが示されている。 本研究では,入力データの確率分布に基づいてチューリングマシンが解けない問題の可否を計測する手法を提案する。 また、チューリングの無限論理とOracleマシンに関する業績を計算の超チューリングモデルに拡張することも提案されている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Alan Turing is considered as a founder of current computer science together with Kurt Godel, Alonzo Church and John von Neumann. In this paper multiple new research results are presented. It is demonstrated that there would not be Alan Turing's achievements without earlier seminal contributions by Georg Cantor in the set theory and foundations of mathematics. It is proposed to introduce the measure of undecidability of problems unsolvable by Turing machines based on probability distribution of its input data, i.e., to provide the degree of unsolvabilty based on the number of undecidable instances of input data versus decidable ones. It is proposed as well to extend the Turing's work on infinite logics and Oracle machines to a whole class of super-Turing models of computation. Next, the three new complexity classes for TM undecidable problems have been defined: U-complete (Universal complete), D-complete (Diagonalization complete) and H-complete (Hypercomputation complete) classes. The above has never been defined explicitly before by other scientists, and has been inspired by Cook/Levin NP-complete class for intractable problems. Finally, an equivalent to famous P is not equal to NP unanswered question for NP-complete class, has been answered negatively for U-complete class of complexity for undecidable problems.
• Abstract（参考訳）: アラン・チューリングはクルト・ゴデル、アロンゾ・チャーチ、ジョン・フォン・ノイマンとともに現在のコンピュータ科学の創始者と見なされている。 本稿では, 新たな研究成果について述べる。 数学の集合論と基礎において、ゲオルク・カントールの初期の独学的な貢献がなければ、アラン・チューリングの業績は存在しないことが示されている。 チューリングマシンが解けない問題の可解性(不確定性)を,その入力データの確率分布,すなわち,決定不能な入力データのインスタンス数と決定不能なデータ数に基づいて不確定性(unsolvabilty)の度合いを与える方法を提案する。 チューリングの無限論理とOracleマシンに関する業績を、計算の超チューリングモデル全体のクラスに拡張することも提案されている。 次に、TM問題に対する3つの新しい複雑性クラスが定義されている: U完全(Universal Complete)、D完全(Diagonalization Complete)、H完全(Hypercomputation Complete)クラス。 上記のことが他の科学者によって明確に定義されたことはなく、難解な問題に対してCook/Levin NP完全クラスから着想を得ている。 最後に、有名な P と同値なものは NP 完全クラスに対する NP 未解問題と等しいものではなく、決定不能な問題に対する U 完全クラスに対して負に答えられる。

関連論文リスト

• The Imitation Game: Turing Machine Imitator is Length Generalizable Reasoner [71.41162392872393]
  本稿では,大規模言語モデルの長さ一般化能力を向上させるため,Turing Machine Imitation Learning (TAIL)を提案する。 TAILはコンピュータプログラムによってチューリングマシンの実行プロセスを模倣するチェーン・オブ・思想(CoT)データを合成する。 ベルとホイッスルがなければ、TAILは様々なタスクにおけるQwen2.5-7Bの性能と同様に、長さの一般化能力を大幅に改善する。
  論文  参考訳（メタデータ） (2025-07-17T17:50:07Z)
• Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN [55.2480439325792]
  計算問題はすべて、解を返却する厳密な明示的な方程式を持つことを示す。 本稿では, インバージョン, 制約満足度, 最適化の両面から, 正確に任意の問題を解く方程式を得る方法を提案する。
  論文  参考訳（メタデータ） (2025-02-09T18:16:53Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• When Input Integers are Given in the Unary Numeral Representation [0.0]
  多くのNP完全問題は、入力インスタンスの一部として整数を取る。 数値の「統一」は、問題の計算複雑性に著しく異なる効果をもたらすことが知られている。 入力整数を単項で表すと容易に解けるNP完全問題(NP完全問題)が多数存在する。
  論文  参考訳（メタデータ） (2023-12-07T15:09:24Z)
• Exceeding Computational Complexity Trial-and-Error Dynamic Action and Intelligence [0.0]
  計算複雑性 (Computational complexity) は、計算の難易度を規定する計算機科学のコア理論である。 本稿では,概念を明確にし,不特定型コンピューティング,特化型コンピューティング,コンピュータエージェント,動的検索などの定義を提案する。 また,このフレームワーク,すなわちトライアル・アンド・エラー+動的検索を提案し,議論する。
  論文  参考訳（メタデータ） (2022-12-22T21:23:27Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Resource dependent undecidability: computability landscape of distinct Turing theories [0.0]
  我々は、異なるチューリング理論の任意の対に対して無限に多くの問題を定式化する新しい論理構造を思いついた。 重要なことに、ハルティング問題のような他の決定問題のクラスは、これらのすべての理論では解決不可能である。
  論文  参考訳（メタデータ） (2021-12-26T09:59:37Z)
• On Theoretical Complexity and Boolean Satisfiability [0.0]
  この論文は、コンピューティング理論において最も中心的な概念をいくつか導入している。 次に,Hhorn-SAT や 3-SAT などの抽出可能な変種を探索する。 最後に,3-SATから有名なNP完全グラフ問題への還元を確立する。
  論文  参考訳（メタデータ） (2021-12-22T10:13:34Z)
• Three computational models and its equivalence [0.0]
  計算可能性の研究は、1900年のヒルベルトの会議(英語版)においてアルゴリズムの概念を正確に記述することに由来する。 数学的詳細を忘れずに、現代の方法で証明を提示するこのギャップを埋めるつもりです。
  論文  参考訳（メタデータ） (2020-10-26T05:55:19Z)

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

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