3

次の問題が気になります。私は明らかに実用的な解決策を期待していませんが、これに関する開発者の考えをいただければ幸いです。

理論的には、他のプログラムを開き (引数のために、.exe ファイルを開くとしましょう)、特定の実行可能ファイルが実行されたときに (入力とマシンの状態が固定されている場合)、チェスのゲーム (それが実行する可能性のある他のタスクの中で)。

「チェスをする」とは、チェスの盤と駒を表現し、組み込みのチェス AI エンジンに由来する黒と白の後続の動きを適用することを意味します。

このような理論上の「チェス検出プログラム」には、必要に応じてスキャンされた実行可能ファイルを実際にシミュレートする仮想マシンまたは PC エミュレーターなどを含めることができます。同上RAMを備えた任意の速度のコンピューターで実行されると想定できます。

（編集）停止の問題に関しては、次のように解決できます。

プログラムを仮想マシンにロードします。仮想マシンには N ビット (ハード ディスクとメモリ空間と CPU レジスタを合わせたもの) があります。この仮想マシンは、最大で 2^N の異なる状態を想定できます。

VM でプログラムを段階的に実行します。各ステップの後、停止したかどうかを確認します。はいの場合: 問題は解決しました (結果: はい、停止します)。いいえの場合: 仮想マシンの現在の状態を取得し、この状態が以前に遭遇した状態のリストに存在するかどうかを確認します。はいの場合: 問題は解決しました (結果: いいえ、永久に実行されます)。いいえの場合: この州をリストに追加して続行します。

発生する可能性のある異なる状態は最大で 2^N であるため、このアルゴリズムは、プログラムが有限時間内に確実に停止するかどうかを判断します。

(編集 2) スキャンされた実行可能ファイルまたはそれが実行される (仮想) マシンの (無限) 無限性について、あいまいさがあるようです。スキャンする実行可能ファイルが最大で 1 GB (ほとんどのチェス プログラムはかなり小さいため、これで十分なはずです) であり、10 GB の RAM を搭載した PC (または VM) で実行されるとします。

私たちの理論的なチェス検出器プログラムは、任意の量の RAM を使用できます。

4

4 に答える 4

7

いいえ、実行可能ファイルがチェスをプレイしているかどうかを検出できるアルゴリズムはありません。

これの証拠は、次の問題 (停止問題と呼ばれる) がどのアルゴリズムでも解決できないという事実にあります。

コンピューター プログラムが与えられた場合、そのプログラムは最終的に終了しますか?

別のプログラムがチェスのゲームをプレイしているかどうかを判断できるコンピューター プログラムがあれば、停止問題を解決できることを示すことができます。そのためには、次のことを行うコンピューター プログラムを作成します。

  1. 他のコンピュータープログラム P を入力として取ります。
  2. プログラム P を実行します。
  3. プログラム P が終了したら、チェスのゲームをプレイします。

このプログラムには、次の興味深い動作があります。プログラム P が終了した場合にのみ、チェスのゲームをプレイします。つまり、このプログラムがチェスをプレイできるかどうかを検出できれば、プログラム P が終了するかどうかを検出することになります。ただし、これは不可能であることがわかっているため、コンピューター プログラムがチェスをプレイしているかどうかを検出するプログラムは存在しないはずです。

この一般的なアプローチは、停止問題からの還元と呼ばれ、膨大な数のさまざまな問題がおそらく解決できないことを示すために使用できます。

これが役に立てば幸いです。「いいえ」の回答で申し訳ありません。

于 2011-11-29T22:34:05.000 に答える
4

あなたの編集された質問に関して:はい、メモリのサイズを制限して、可能なプログラムの数を有限に制限する場合、理論的には可能なすべてのプログラムを列挙し、それらを「チェスをする」と「チェスをしない」に手動で分割できます"あなたが望む基準のセットによって。

この場合、チューリング マシンがなくなるため、停止問題は適用されません。代わりに、有限状態マシンを使用します (そうです、これは、現実の世界では、すべてのコンピューターが実際にはチューリング マシンの有限状態近似であることを意味します)。

ただし、この制限を追加したのは、「理論的ではなく実用的」であることを望んでいたためです。ここで、もう 1 つの実用性を示します。256 ビット プログラムをすべて列挙します(10 億台の PC で、それぞれが 10 億個のプログラムを列挙します)。 2 番目)完了するには、宇宙の年齢よりもかなり長い時間がかかります。したがって、1 GB (約 1,000,000,000 ビット) 未満のすべてのプログラムを列挙するのにどれだけの時間がかかるか想像もつきません。

このため、実際のコンピューターを有限状態マシンとしてモデル化するよりも、チューリング マシンとしてモデル化する方が現実的です。このモデルでは、@templatetypedef が証明したように、それは不可能です。

于 2011-11-29T23:34:31.513 に答える
1

いいえ、これは停止問題と同じです。

于 2011-11-29T22:32:38.130 に答える
0

プログラムがチェスをするということはどういう意味ですか? 私は、この問題の正確な数学的定義が存在するとは信じていません。

たとえば、「このプログラムがチェスをプレイする際の動きのエンコードは存在しますか?」と尋ねるとします。次に、裸のPythonインタープリターがチェスをプレイします-入力する必要があると規定するエンコーディングの下で​​：

  • チェスをプレイする Python プログラムと、対戦相手を黒くしたい場合の最初の動き
  • 白でプレイしたい場合は、チェスをプレイする Python プログラム

エンコーディングを修正すると、問題は退屈になります。チェス ゲームは (50 手の規則により) 有限であるため、唯一の難しい質問は、「このプログラムは、チェス ゲームの有限セットのいずれかの動きの間にハングするか」ということです。エンコーディングを尊重せず、常にエンコーディングを尊重する (そして有効な動きをする、これはすべてチェックするのは簡単です) 場合、チェスをプレイします。もちろん、ハングするかどうかを確認することはできません。すべてのチェス ゲームを列挙することは治療可能ですが、実際的な考慮事項を考慮すると、もちろん完全に不可能でもあります。

于 2011-11-30T09:34:55.080 に答える