問題タブ [computability]

チューリングマシンとは何ですか?なぜ人々はそれについて言及し続けるのですか? IBM PC だけで計算を行うことができます。なぜ誰もがこれらのマシンを気にするのですか?

私は最近、人工生命について読んでいて、 「コンウェイのライフ ゲームは、普遍的な機械として分類されるのに十分な複雑さを示している」という記述に出くわしました。私はユニバーサル マシンとは何かについて大まかにしか理解していませんでした。ウィキペディアは、ウィキペディアがかつてないほど理解に近づいただけでした。誰かがこの非常にセクシーな声明に光を当てることができるのだろうか?

コンウェイのライフ ゲームは、私には、いくつかの途方もない含意を伴う素敵な気晴らしのように思えます。それは私がすべき飛躍ですか？

Stephen Wolfram はTEDで Mathematica と Wolfram Alpha に関する彼の研究について興味深い講演を行いました. とりわけ、彼は、非常に単純な計算が非常に複雑な動作を生み出す可能性があることを指摘しました。(彼は、物理的な宇宙全体を計算するという彼の野望について話し続けます。あなたが何と言おうと、あなたは彼の突飛なアイデアを称賛しなければなりません...)

例として、彼はいくつかのセルオートマトンを示しました。

魅力的な結果をもたらす簡単な計算の例を他に知っていますか?

ウィキペディアから：

問題Hは、多項式時間チューリングでHに還元可能な（つまり、L≤TH）NP完全問題Lがある場合にのみ、NP困難です。

なぜ問題（それをWと呼ぶ）がNP完全である必要から減らされるのですか？なぜそれはNP困難でもないのですか？NPではなく、Wが「ハード」であることを気にかけているようです。

考え？

解析関数のパワーを再構築することに制限はありますか？css2 / css 3仕様全体を解析できるのでしょうか、それともいくつかのルールを形成することが理論的に不可能になるのでしょうか。

HostileForkの回答後の更新：正規表現では、それはかなり不可能だと思いますが、解析ははるかに強力ですか？

はいの場合、html5と互換性のあるrebol vidでブラウザを構築できることを意味しますか？

XOR暗号化は非常に弱いことが知られています。しかし、異なる（理想的にはプライム）長さの複数のキーで構成され、それらを組み合わせてより長いキーを作成するキーがある場合、それはどれほど弱いかです。たとえば、長さ5、9、11のテキストキーがあります。XOR暗号化を使用して最初のキーを適用するだけの場合、暗号化バイトは5バイトごとに繰り返されるため、簡単に破ることができます。ただし、これらのキーの3つを「オーバーレイ」すると、5 * 9 * 11=495の有効な非反復長が得られます。これはかなり強いように聞こえます。各行をキーとして使用して詩の2節を使用すると、繰り返されない長さはほとんどのファイルよりもはるかに長くなります。これはどれほど強力でしょうか（キーを提供することは秘密のままです！:)）

私は計算に関する本（Minksy 1967）を読み進めており、再帰関数をループで定義された関数に関連付けるのに苦労しています。具体的には、彼は2つの機能間の関係を見つけるように求めています。

アッカーマン関数（すべてPythonのコード）：

そして、n個のネストされたループで計算する関数：

これを（1つのループで）再帰的に記述する方法は次のとおりです。

または、それを書くための完全に再帰的な方法は次のようになります。

これらの2つの機能を関連付ける簡単な方法はありますか？霧の中を這い回っているような気がします。この種の問題にどのように取り組むかについての洞察をいただければ幸いです。また、3番目のパラメーターを導入せずに完全再帰ループ関数を実装する方法はありますか？ありがとう。

プログラムで行う数値演算は、特定のデータ型 (またはハードウェアがサポートするもの) に対して言語が指定するバイト数によって制限されます。整数を使用して給料の計算を行うことができるとします (「短い」ものでも、1 年間の収入には十分すぎる!!! ;)) が、ビル ゲイツの富については同じことができません。それで、私たちは長い長いものなどに行きます。しかし、私たちはまだ与えられたビット数に翻弄されていませんか。

では、ソフトウェアで数値演算をエミュレートしたらどうでしょうか。数千桁の数値を抽象化し、数値演算を実行できるクラスを考えてみましょう...もちろん遅すぎますが、複雑さについてはあまり心配していませんが、計算可能性だけを見てください...

多分私はそれを使って PI を 1 ヶ月で 1000 桁の精度で計算するか、数年で Mersenne Primes を計算し、10 万ドルを家に持ち帰ることができます ;)

だから今、私の質問は、1）この種のことを行うためのそのようなライブラリはすでにありますか（C / C ++で）。2) 実装する場合、何か提案はありますか? (+、-、​​、/、%、<<、>> 操作で十分だと思います)

PS:

1. 私は C/C++ プログラマーです。

2. そして、この制限は学生時代から私を悩ませ始めました。

私の知る限り、計算可能な数値のチューリングは、チューリング マシンによって i 番目のインデックスを返すことができる数値です。したがって、計算不可能な数値は、他のプログラムが他の入力で停止した場合などに小数点が決定される数値のようなものになります。ただし、PI は実数であり、TM によって列挙できないため、計算されますか？では、どの学派が正しいのでしょうか？

これは私がコースで解決した問題であり、私の解決策が正しいかどうか疑問に思っていました。私は通常、純粋数学の問題を投稿しませんが、それは計算不可能であり、したがってコンピュータサイエンスの問題であると私は信じています。

あなたは与えられます：

P（S）= 10％

P（Theta1 | S）= P（Theta2 | S）= 96％

P（Theta1ではない| Sではない）= P（Theta2ではない| Sではない）= 98％

そして、通常の公理と確率論の定義以外の情報はありません。

特に、イベントの独立性に関する情報は提供されません。

P（S | Theta1およびTheta2）を計算するように求められます。

これは解決可能ですか？そうでない場合は、計算不能の証拠を提供してください。

おもしろいね