論文の概要: Computational Hierarchy of Elementary Cellular Automata

• arxiv url: http://arxiv.org/abs/2108.00415v1
• Date: Sun, 1 Aug 2021 10:00:54 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-04 06:18:24.004540
• Title: Computational Hierarchy of Elementary Cellular Automata
• Title（参考訳）: 基本セルオートマタの計算階層
• Authors: Barbora Hudcov\'a and Tom\'a\v{s} Mikolov
• Abstract要約: セルラーオートマトンとセルラーオートマトンをエミュレートする能力について検討した。 非自明なオートマトンをエミュレートできないのは,ある種のカオスオートマトンのみであることを示す。 我々の研究は、チューリング完全かつ計算効率のよい並列計算システムの設計に役立つと信じている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The complexity of cellular automata is traditionally measured by their computational capacity. However, it is difficult to choose a challenging set of computational tasks suitable for the parallel nature of such systems. We study the ability of automata to emulate one another, and we use this notion to define such a set of naturally emerging tasks. We present the results for elementary cellular automata, although the core ideas can be extended to other computational systems. We compute a graph showing which elementary cellular automata can be emulated by which and show that certain chaotic automata are the only ones that cannot emulate any automata non-trivially. Finally, we use the emulation notion to suggest a novel definition of chaos that we believe is suitable for discrete computational systems. We believe our work can help design parallel computational systems that are Turing-complete and also computationally efficient.
• Abstract（参考訳）: セルオートマタの複雑さは、伝統的に計算能力によって測定される。 しかし、そのようなシステムの並列性に適した難解な計算タスクを選択することは困難である。 私たちはオートマトンが互いにエミュレートする能力を研究し、この概念を使って自然に出現するタスクの集合を定義します。 本研究は,基本的なセルオートマトンについて述べるが,コアアイデアは他の計算システムにも拡張できる。 我々は,どのセルオートマトンをエミュレートできるかを示すグラフを計算し,カオスオートマトンだけが非自明にオートマトンをエミュレートできないことを示す。 最後に,エミュレーションの概念を用いて,離散計算システムに適したカオスの定義を提案する。 我々の研究は、チューリング完全かつ計算効率のよい並列計算システムの設計に役立つと信じている。

関連論文リスト

• Computational Dynamical Systems [0.6138671548064356]
  チューリングマシンをシミュレートするスムーズな力学系について、その意味について定義を与える。 カオス的」力学系と「可積分」力学系は普遍チューリングマシンを強くシミュレートできないことを示す。 より広範に、我々の研究は「機械」が他の機械をシミュレートする意味を解明し、低複雑さの「エンコーダ」と「デコーダ」を定義する必要性を強調している。
  論文  参考訳（メタデータ） (2024-09-18T17:51:48Z)
• Randomized Polar Codes for Anytime Distributed Machine Learning [66.46612460837147]
  本稿では,低速な計算ノードに対して堅牢で,線形演算の近似計算と精度の両立が可能な分散コンピューティングフレームワークを提案する。 本稿では,復号化のための計算複雑性を低く保ちながら,実数値データを扱うための逐次復号アルゴリズムを提案する。 大規模行列乗算やブラックボックス最適化など,様々な文脈において,このフレームワークの潜在的な応用を実証する。
  論文  参考訳（メタデータ） (2023-09-01T18:02:04Z)
• A full-stack view of probabilistic computing with p-bits: devices, architectures and algorithms [0.014319921806060482]
  pビットを用いた確率計算のフルスタックレビューを提供する。 pビットはエネルギー効率のよい確率システムを構築するのに使用できると我々は主張する。 我々は、機械学習からAIまで、確率的コンピュータの主な応用について概説する。
  論文  参考訳（メタデータ） (2023-02-13T15:36:07Z)
• The Basis of Design Tools for Quantum Computing: Arrays, Decision Diagrams, Tensor Networks, and ZX-Calculus [55.58528469973086]
  量子コンピュータは、古典的コンピュータが決して起こらない重要な問題を効率的に解決することを約束する。 完全に自動化された量子ソフトウェアスタックを開発する必要がある。 この研究は、今日のツールの"内部"の外観を提供し、量子回路のシミュレーション、コンパイル、検証などにおいてこれらの手段がどのように利用されるかを示す。
  論文  参考訳（メタデータ） (2023-01-10T19:00:00Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  低深度変換器は任意の有限状態オートマトンを計算できる。 我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。 さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
  論文  参考訳（メタデータ） (2022-10-19T17:45:48Z)
• A Relative Church-Turing-Deutsch Thesis from Special Relativity and Undecidability [0.0]
  本研究では,グローバルシミュレータが蓄積した時間,空間,誤差の計算がシミュレーション特性であることを示す。 これらのシミュレーション特性は、チャーチ・チューリング・ドイツ理論の構築に使用する相対モデルに特別な相対論的効果をもたらす。
  論文  参考訳（メタデータ） (2022-06-13T18:58:41Z)
• Classification of Discrete Dynamical Systems Based on Transients [0.0]
  決定論的離散空間と時間力学系の任意のクラスに適用可能な新しい分類法を提案する。 順序付けられた振る舞いからカオスへのフェーズ移行に対応する、行動の重要な領域を特定できたのです。 私たちの仕事は、複雑な構造が現れるシステムの設計に利用できます。
  論文  参考訳（メタデータ） (2021-08-03T15:34:01Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)
• Visualizing computation in large-scale cellular automata [24.62657948019533]
  セルオートマトンのような複雑なシステムの創発的プロセスは、複雑さが増大する計算を実行することができる。 セル状態,クラスタリング,オートエンコーダの周波数解析に基づく粗粒度セルオートマトンの方法を提案する。
  論文  参考訳（メタデータ） (2021-04-01T08:14:15Z)
• Predictive Coding Approximates Backprop along Arbitrary Computation Graphs [68.8204255655161]
  我々は、コア機械学習アーキテクチャを予測的符号化に翻訳する戦略を開発する。 私たちのモデルは、挑戦的な機械学習ベンチマークのバックプロップと同等に機能します。 本手法は,ニューラルネットワークに標準機械学習アルゴリズムを直接実装できる可能性を高める。
  論文  参考訳（メタデータ） (2020-06-07T15:35:47Z)
• Reservoir memory machines [79.79659145328856]
  本稿では,ニューラルチューリングマシンのベンチマークテストのいくつかを解くことができる貯水池メモリマシンを提案する。 我々のモデルは、外部メモリによるエコー状態ネットワークの拡張と見なすことができ、干渉することなく任意の長さの記憶が可能となる。
  論文  参考訳（メタデータ） (2020-02-12T01:45:00Z)

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

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