論文の概要: Basic interactive algorithms: Preview

• arxiv url: http://arxiv.org/abs/2508.05798v1
• Date: Thu, 07 Aug 2025 19:13:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-11 20:39:05.991609
• Title: Basic interactive algorithms: Preview
• Title（参考訳）: 基本的な対話型アルゴリズム: プレビュー
• Authors: Yuri Gurevich,
• Abstract要約: 現代のアルゴリズムの概念は1930年代から1950年代にかけて解明された。 公理化は、すべての基本アルゴリズムに振る舞いに等価な抽象状態機械が存在することを示すために用いられた。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This dialog paper offers a preview and provides a foretaste of an upcoming work on the axiomatization of basic interactive algorithms. The modern notion of algorithm was elucidated in the 1930s--1950s. It was axiomatized a quarter of a century ago as the notion of ``sequential algorithm'' or ``classical algorithm''; we prefer to call it ``basic algorithm" now. The axiomatization was used to show that for every basic algorithm there is a behaviorally equivalent abstract state machine. It was also used to prove the Church-Turing thesis as it has been understood by the logicians. Starting from the 1960s, the notion of algorithm has expanded -- probabilistic algorithms, quantum algorithms, etc. -- prompting introduction of a much more ambitious version of the Church-Turing thesis commonly known as the ``physical thesis.'' We emphasize the difference between the two versions of the Church-Turing thesis and illustrate how nondeterministic and probabilistic algorithms can be viewed as basic algorithms with appropriate oracles. The same view applies to quantum circuit algorithms and many other classes of algorithms.
• Abstract（参考訳）: このダイアログペーパーは,基本的な対話型アルゴリズムの公理化に関する今後の研究の先駆けとなる,プレビューを提供する。 現代のアルゴリズムの概念は1930年代から1950年代にかけて解明された。 一世紀半前に『逐次アルゴリズム』や『古典的アルゴリズム』の概念として公理化され、現在では『基本アルゴリズム』と呼ぶのが好まれている。 公理化は、すべての基本アルゴリズムに振る舞いに等価な抽象状態機械が存在することを示すために用いられた。 また、論理学者によって理解されているチャーチ・チューリングの論文を証明するためにも用いられた。 1960年代以降、確率論的アルゴリズムや量子アルゴリズムなどのアルゴリズムの概念が拡大し、より野心的なチャーチ・チューリングの論文が「物理論」として知られるようになった。 チャーチ・チューリングの論文の2つのバージョンの違いを強調し、不決定性アルゴリズムと確率性アルゴリズムを適切なオーラクルを持つ基本アルゴリズムとみなす方法について説明する。 同じ見解は量子回路アルゴリズムや他の多くのアルゴリズムのクラスにも当てはまる。

関連論文リスト

• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。 3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。 数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
  論文  参考訳（メタデータ） (2023-11-19T00:06:11Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Basic Quantum Algorithms [0.0]
  量子コンピューティングは急速に進化しており、理論の基礎を再検討し、書き直し、更新せざるを得ない。 基本量子アルゴリズムは、初期の量子アルゴリズムを再考する。
  論文  参考訳（メタデータ） (2022-01-25T19:00:10Z)
• How to transfer algorithmic reasoning knowledge to learn new algorithms? [23.335939830754747]
  我々は,実行トレースにアクセス可能なアルゴリズムを用いて,そうでない同様のタスクを解く方法について検討する。 9つのアルゴリズムと3つの異なるグラフタイプを含むデータセットを作成します。 我々はこれを実証的に検証し、その代わりにマルチタスク学習を用いてアルゴリズム推論知識の伝達を実現する方法を示す。
  論文  参考訳（メタデータ） (2021-10-26T22:14:47Z)
• Quantum Inspired Adaptive Boosting [0.0]
  量子アンサンブル法は古典的アルゴリズムに勝らないことを示す。 本稿では,量子アンサンブル法と適応的なブースティングを組み合わせた手法を提案する。 アルゴリズムはテストされ、公開データセット上のAdaBoostアルゴリズムに匹敵することがわかった。
  論文  参考訳（メタデータ） (2021-02-01T16:33:14Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  メタラーニング強化学習アルゴリズムの手法を提案する。 学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。 従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
  論文  参考訳（メタデータ） (2021-01-08T18:55:07Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)

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

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