She*_*man 3 theory algorithm executable chess detect
我想知道以下问题.我显然不希望有任何实际的解决方案,但我会感谢开发人员对此的看法:
理论上是否可以有一个程序打开其他程序(为了参数,让它说它打开.exe文件),并确定一个特定的可执行文件,当执行时(具有固定的输入和机器状态),播放国际象棋游戏(在其可能执行的任何其他任务中).
使用'下棋',我的意思是有一些棋盘和棋子的代表,应用后来的黑色和白色动作源于内置的国际象棋AI引擎.
这种理论上的"国际象棋检测程序"可以包含虚拟机或PC模拟器,或者在必要时实际模拟扫描的可执行文件的任何内容.我们可以假设它在任意快速的计算机上运行,并且具有ditto ram.
(编辑)关于暂停问题,我可以这样解决:
将程序加载到虚拟机中,该虚拟机具有N位(硬盘和存储空间以及CPU寄存器).该虚拟机可以假设最多2 ^ N个不同的状态.
逐步执行VM中的程序.每个步骤后,检查它是否停止.如果是:问题解决了(结果:是的,它停止了).如果否:获取虚拟机的当前状态,并查看此状态是否存在于我们之前已遇到的状态列表中.如果是:问题解决了(结果:不会永远运行).如果否:将此状态添加到列表中并继续.
由于可能出现最多2 ^ N个不同的状态,因此该算法将确定程序是否在有限时间内确定地停止.
(Edit2)扫描的可执行文件或其运行的(虚拟)机器的(有限)似乎有些含糊不清.假设要扫描的可执行文件最多可以是1 GB(这应该足够,因为大多数国际象棋程序都要小得多)并且它们应该在具有10 GB内存的PC(或VM)上运行.
我们的理论象棋检测程序可以使用任意数量的ram.
不,没有这样的算法可以检测可执行文件是否下棋.
这证明了以下问题(称为暂停问题)无法通过任何算法解决:
鉴于计算机程序,该程序最终会终止吗？
我们可以证明,如果有一个计算机程序可以确定另一个程序是否下棋,我们就可以解决停止问题.为此,我们将编写一个执行以下操作的计算机程序:
该程序具有以下有趣的行为:当且仅当程序P终止时,它才会玩象棋游戏.换句话说,如果我们能够检测到该程序是否可以下棋,我们将检测程序P是否终止.但是,我们知道这是不可能做到的,因此必须没有一个程序可以检测某些计算机程序是否下棋.
这种通用方法被称为从暂停问题中减少,可用于表明大量不同的问题可能无法解决.
希望这有帮助,并抱歉"不"的答案!