問題タブ [computability]

このフィドルで表示できる自分のWebサイト用のスティッキーフッターを作成しました：http：//jsfiddle.net/Aw6vn/

jsfiddleのすべてのブラウザーで機能しますが、ページにコードを配置した場合、IE8-9では機能しません。

http://s-maof.com/PRO/index2.php?fkapp=2

私も試しました：

それをしませんでした。

「MyHeadHurts」のおかげで、解決策はコメント付きのヘッダーを編集することでした

ありがとう！

DB からデータを動的にロードし、jQuery を使用して html ラベルとクラスをページに追加するページを作成しました。

htmlは

そしてjsは

FF と chrome では動作しますが、IE8 では動作しません。

ページのリンクはhttp://www.s-maof.com/PRO/index.php?fkapp=9 です (検索ボックスで「649012」を探してください - 1 つしかありません)。

また、ハイ チャート グラフが機能しません (IE のみ)。

ありがとう。

私が を持っている場合Σ={a}、 が を持っている単語は何Σ*ですか?

Σ*= {a,aa,aaa,aaaa.....}?

ありがとう

セルがビットで、+ 操作と - 操作が少し反転するだけの場合、Brainfuck Turing は完全ですか? Brainfuck のような言語がセル サイズに関係なくチューリング完全であるという簡単な証明はありますか、それともチューリング マシンをシミュレートするプログラムを考える必要がありますか? 存在しない場合、どうすればわかりますか？

編集: 私の質問に対する答えが見つかりました: ビット セルを使用した Brainfuck はBoolfuckと呼ばれます。通常の Brainfuck はそれに還元できるため、Boolfuck はチューリング完全です。

コードが実行されているターゲット実装がわからない JavaScript (他の場所ではある程度適用可能) では、基になる並べ替えアルゴリズム (の) が安定しているかどうかを検出する機能があり、仕様Array.sortに従っていることだけを知っています。 ?

webkit (1) (2)で 2 つのテストを見つけることができましたが、これらのテストの信頼性はどの程度ですか? (このチェックはPCPで行うことができますか?) 数学的に正しい解決策を探しています。

より高度なソート アルゴリズムでは、ソース配列の長さに応じてサブアルゴリズムを変更できるため (Timsort など)、これは難しい問題です。私が実行したすべてのテストでGoogle Chromeのソートが安定していることが示されているので、私は混乱していますが、私が見たすべてのドキュメントは、それが不安定であると述べています（ソースが理由を教えてくれます）。

(通常、私はこの戦略を使用してソートを安定させます。パフォーマンスへの影響は小さいですが、ときどき顕著になります)

• Google Chrome/ium - V8
• サファリ - JSC
• Firefox - *モンキー (2) (3)

独自の BigInteger 実装を行っているときに、拡張 GCD アルゴリズムに行き詰まりました。これはモジュラー乗法逆数を見つけるための基本です。よく知られているユークリッド アプローチはパフォーマンスが遅すぎ、ハイブリッド アルゴリズムとバイナリ アルゴリズムは 5 ～ 10 倍しか高速ではないため、従来のアルゴリズムに対するレーマーの修正が選択されました。しかし難しいのは、Lehmer's について説明することになると、私が見つけたすべての本 (Knuth、Handbook of Applied Cryptography、Internets など) には同じ欠点があることです。

1. 説明はいくつかのトリックに基づいています。
   • 入力数値は常に同じ長さです。
   • 抽象 CPU には符号付きレジスタがあり、数字と符号の両方を保持できます。
   • 抽象的な CPU には半無制限のレジスタがあります。つまり、オーバーフローすることはありません。
2. 逆余因子に焦点を当てることなく、基本的な GCD アルゴリズムのみが提供されます。

最初の問題については、実際の実装が見つからないことに最初は驚きました (GNU MP ライブラリを紹介しないでください。学ぶためのソースではありません)。明らかに論文「<a href="http://www.csie.nuk.edu.tw/~cychen/gcd/A%20double-digit%20Lehmer-Euclid%」のアイデアに基づいている.Net 4.0から20algorithm%20for%20finding%20the%20GCD%20of%20long%20integers.pdf" rel="nofollow">長い整数の GCD を見つけるための 2 桁の Lehmer-Euclid アルゴリズム" by Jebelean. 結果の関数は大きく、恐ろしく見えますが、うまく機能します。

しかし、Microsoft のライブラリは基本的な機能のみを提供し、補因子は計算されません。正確に言うと、一部の補因子は速記ステップで計算され、最初のステップではそれらの補因子は単純に最初のものですが、筆記ステップが実行された後は一致しなくなります。私の現在の解決策は、「実際の」余因子を「代用」の余因子と並行して更新することですが (最初のステップを除く)、パフォーマンスがゼロ以下に低下します: 関数はバイナリよりも 25-50 % 速く完了します基本モードでの方法。したがって、問題は、入力数値が完全に更新されるのはロングハンド ステップのみであるのに対し、補因子は各ショートハンド ステップの反復でも更新されることです。、したがって、レーマーのアプローチからのほとんどすべての利益を破壊します。

少しスピードアップするために、「融合乗算加算」関数を実装しました。これは、「融合乗算乗算減算」が実際に入力数値の更新に役立つためですが、今回の影響はごくわずかでした。別の改善は、通常は 1 つの補因子のみが必要であるという事実に基づいているため、もう 1 つの補因子はまったく計算されない可能性があります。これにより、オーバーヘッドが半分になります (通常、2 番目の数値は最初の数値よりも大幅に小さいため、さらに半分になります)。ただし、実際には、オーバーヘッドは予想の25 ～ 50% しか減少しません。

したがって、私の質問は次のようになります。

1. 実世界のハードウェア (サイズが制限された符号なしワード) での実用的な実装に結び付けられた、レーマーのアルゴリズムの本格的な説明はありますか?
2. 上記と同じですが、拡張GCD 計算に関するものです。

したがって、基本的なアルゴリズムのパフォーマンスに満足しているのと同じように、拡張モードの操作には反対のことが当てはまります。

私は計算可能性に関する本でこれを読みました：

(クリーネの定理) ある言語が正則であるのは、結合、連結、反復の 3 つの操作を有限回数適用することによって有限言語から得られる場合に限ります。

私は「有限言語」に苦労しています。

この言語を考えてみましょう:L = a*

有限ではありません。{0, a, aa, aaa, ...}明らかに無限集合（0＝空の文字列）である集合です。

無限の言語ですね。つまり、「無限集合」とは「無限の言語」ということですよね？

明らかにa*正規言語です。そしてそれは無限の言語です。したがって、クリーネの定理により、正規言語になることはできません。矛盾。

よくわかりません。私は「有限言語」が何を意味するのか分からないと思います。

通常 TAλ として知られる単純型の基本システムを考えてみましょう。それを証明することができます (いわゆる主語還元特性と、型付け可能な項はすべて強力に β 正規化されているという事実の結果として)

居住問題 Γ ⊢ X : τ が与えられると、(i) X が xY_1...Y_n であるか、(ii) X が λz であるかのいずれかである、正規解の形状を段階的に非決定論的に推測するアルゴリズムを効果的に構築できます。よ:

(i) いくつかの n ≥ 0 について、Γ で x : σ_1 → ... → σ_n → τ という判断がある場合、非決定論的にそれを選択し、X = xY_1...Y_n を設定し、(n > 0 の場合のみ) 並列問題を検討します。 Γ ⊢ Y_1 : σ_1,...,Γ ⊢ Y_n : σ_n

(ii) τ が τ_1 → τ_2 の場合、新しい変数 z に対して、X = λz.Y を設定し、問題 Γ、z : τ_1 ⊢ Y : τ_2 を検討します。

さらに、アルゴリズムの各ステップでの制約内のすべてのタイプは、元の入力の適切なサブタイプであるため、アルゴリズムのステップ数は、多くても τ のサイズの多項式です。したがって、上記のアルゴリズムは居住問題の決定手順です。

私の質問は次のとおりです。上記の推論の何が問題なのですか? 単純型の生息問題の決定手順を一日中探していましたが、見つけることができるすべての証明はかなり長く、複雑な機構を使用しています (例: 長い正規形、Curry-Howard 同型など...)。見えない何かがあるに違いない。

申し訳ありませんが、私はユニコードに慣れておらず、SO は LaTeX をサポートしていません。MO https://mathoverflow.net/questions/140045/is-there-an-easy-decision-algorithm-for-the-inhabitation-problem-for-simple-typeでも同じ質問をしましたが、ラムダ計算はグループはあまり活発ではないようです。