論文の概要: Recursed is not Recursive: A Jarring Result
- arxiv url: http://arxiv.org/abs/2002.05131v2
- Date: Thu, 7 May 2020 15:17:11 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-01 20:22:00.090636
- Title: Recursed is not Recursive: A Jarring Result
- Title（参考訳）: 再帰は再帰的ではない:ジャリング結果
- Authors: Erik Demaine and Justin Kopinsky and Jayson Lynch
- Abstract要約: Recursedが再完全であることを証明する。
当社の削減は「実践的」であり、PCPからの削減は、すべての制約が支配するレベルに順応する、完全なプレイ可能なレベルをもたらす。
- 参考スコア（独自算出の注目度）: 1.757892306945702
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recursed is a 2D puzzle platform video game featuring treasure chests that,
when jumped into, instantiate a room that can later be exited (similar to
function calls), optionally generating a jar that returns back to that room
(similar to continuations). We prove that Recursed is RE-complete and thus
undecidable (not recursive) by a reduction from the Post Correspondence
Problem. Our reduction is "practical": the reduction from PCP results in fully
playable levels that abide by all constraints governing levels (including the
15x20 room size) designed for the main game. Our reduction is also "efficient":
a Turing machine can be simulated by a Recursed level whose size is linear in
the encoding size of the Turing machine and whose solution length is polynomial
in the running time of the Turing machine.
- Abstract（参考訳）: Recursedは、2Dパズルのプラットフォームゲームで、宝の胸が飛び込んだら、あとで退院できる部屋(関数呼び出しに似ている)をインスタンス化し、オプションでその部屋に戻る瓶(継続と似ている)を生成する。
Recursed は Re-complete であり,それ故に Post Corssociatedence Problem の削減によって (再帰的でない) 決定不能であることを示す。
我々の削減は「実践的」であり、PCPの削減はメインゲーム用に設計されたすべての制約(15×20部屋サイズを含む)に従属する完全なプレイ可能なレベルをもたらす。
チューリングマシンは、チューリングマシンのエンコーディングサイズが線形で、チューリングマシンのランニング時間における解長が多項式である再帰レベルによってシミュレーションすることができる。
関連論文リスト
- Cut Your Losses in Large-Vocabulary Language Models [102.6981011879656]
我々は,全トークンのロジットをグローバルメモリに実体化することなく,クロスエントロピー損失を計算する手法であるカットクロスエントロピー(CCE)を提案する。
CCEはロスのメモリフットプリントを24GBから1MBに減らし、ヘッドのトレーニング時間のメモリ消費を28GBから1GBに短縮する。
論文 参考訳（メタデータ） (2024-11-13T20:30:15Z) - Universal Length Generalization with Turing Programs [24.077722969687898]
本稿では,アルゴリズムタスクをチューリングマシンを模倣するステップに分解する手法であるチューリングプログラムを提案する。
チューリングプログラムを用いることで,アルゴリズム的タスクの領域におけるロバストな長さの一般化が得られる。
次に,確率的チューリングプログラムにおいて,トランスフォーマーが長さ一般化を実現することを実証し,任意のアルゴリズムタスクに対して長さ一般化が可能であることを示唆する。
論文 参考訳（メタデータ） (2024-07-03T17:53:44Z) - Transformers Learn Shortcuts to Automata [52.015990420075944]
低深度変換器は任意の有限状態オートマトンを計算できる。
我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。
さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
論文 参考訳（メタデータ） (2022-10-19T17:45:48Z) - Batch-efficient EigenDecomposition for Small and Medium Matrices [65.67315418971688]
EigenDecomposition (ED)は多くのコンピュータビジョンアルゴリズムとアプリケーションの中心にある。
本稿では,コンピュータビジョンの応用シナリオに特化したQRベースのED手法を提案する。
論文 参考訳（メタデータ） (2022-07-09T09:14:12Z) - DCT-Former: Efficient Self-Attention with Discrete Cosine Transform [4.622165486890318]
トラスフォルマーアーキテクチャの本質的な制限は、ドット積の注意の計算から生じる。
我々のアイデアは、アテンションモジュールの近似を導き出すために、損失の多いデータ圧縮(JPEGアルゴリズムなど)の世界からインスピレーションを得ている。
実験の広範なセクションでは,提案手法が同一性能のメモリを消費しにくくする一方で,推定時間を大幅に削減することを示した。
論文 参考訳（メタデータ） (2022-03-02T15:25:27Z) - Limitations of Deep Learning for Inverse Problems on Digital Hardware [65.26723285209853]
我々は、チューリングマシンとしてモデル化された現在のハードウェアプラットフォームで実際に計算できるものを分析する。
有限次元逆問題は小さな緩和パラメータに対してバナッハ・マズール計算可能でないことを証明した。
論文 参考訳（メタデータ） (2022-02-28T00:20:12Z) - Virtual Replay Cache [20.531576904743282]
本稿では,これらの欠点に対処する新たなデータ構造であるVirtual Replay Cache(VRC)を提案する。
VRCは、DQN(lambda)のキャッシュメモリフットプリントをほぼ排除し、ハードウェアのトレーニング時間をわずかに短縮します。
論文 参考訳（メタデータ） (2021-12-06T23:40:27Z) - Sparsified Linear Programming for Zero-Sum Equilibrium Finding [89.30539368124025]
我々は、この問題に対して全く異なるアプローチを示し、それは競争力があり、しばしば、以前の最先端技術よりも桁違いに優れている。
ポーカーエンドゲームの実験により、現代の線形プログラムソルバは、ゲーム固有のCFRの現代的な変種でさえも競合することを示した。
論文 参考訳（メタデータ） (2020-06-05T13:48:26Z) - Reservoir memory machines [79.79659145328856]
本稿では,ニューラルチューリングマシンのベンチマークテストのいくつかを解くことができる貯水池メモリマシンを提案する。
我々のモデルは、外部メモリによるエコー状態ネットワークの拡張と見なすことができ、干渉することなく任意の長さの記憶が可能となる。
論文 参考訳（メタデータ） (2020-02-12T01:45:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。