3

我想知道以下问题。我显然不期望任何实用的解决方案，但我会感谢任何开发人员对此的想法：

理论上是否有可能让一个程序打开其他程序（为了论证，假设它打开 .exe 文件），并确定特定可执行文件在执行时（具有固定输入和机器状态）是否播放国际象棋游戏（在它可能执行的任何其他任务中）。

对于“下棋”，我的意思是对棋盘和棋子进行一些表示，然后应用源自内置国际象棋 AI 引擎的黑白棋步。

这样一个理论上的“国际象棋检测程序”可能包含一个虚拟机或 PC 模拟器或其他任何东西，以便在必要时实际模拟扫描的可执行文件。我们可以假设它在具有同上 ram 的任意速度的计算机上运行。

（编辑）关于停机问题，我可以这样解决：

将程序加载到具有 N 位（硬盘和内存空间以及 CPU 寄存器）的虚拟机中。这个虚拟机最多可以假设 2^N 个不同的状态。

逐步执行VM中的程序。在每一步之后，检​​查它是否停止。如果是：问题已解决（结果：是，它停止了）。如果不是：获取虚拟机的当前状态，并查看该状态是否存在于我们之前已经遇到的状态列表中。如果是：问题已解决（结果：否，它将永远运行）。如果否：将此状态添加到列表并继续。

由于最多可以出现 2^N 种不同的状态，因此该算法将在有限时间内确定程序是否停止。

（Edit2）关于扫描的可执行文件或它运行的（虚拟）机器的（无限）有限性似乎有些模棱两可。假设要扫描的可执行文件最多为 1 GB（这应该足够了，因为大多数国际象棋程序要小得多），并且它们应该在具有 10 GB 内存的 PC（或 VM）上运行。

我们的理论国际象棋检测程序可以使用任意数量的 ram。

4

4 回答 4

7

不，没有这样的算法可以检测可执行文件是否下棋。

这一点的证明在于以下问题（称为停机问题）不能由任何算法解决：

给定一个计算机程序，该程序最终会终止吗？

我们可以证明，如果有一个计算机程序可以确定另一个程序是否下棋，我们就可以解决停机问题。为此，我们将编写一个执行以下操作的计算机程序：

  1. 将一些其他计算机程序 P 作为输入。
  2. 运行程序 P。
  3. 如果程序 P 终止，下棋。

该程序具有以下有趣的行为：当且仅当程序 P 终止时，它才下棋。换句话说，如果我们可以检测到这个程序是否可以下棋，我们将检测程​​序 P 是否终止。但是，我们知道这可证明是不可能的，所以一定没有程序可以检测某些计算机程序是否下棋。

这种通用方法称为停止问题的归约，可用于表明大量不同的问题可能无法解决。

希望这会有所帮助，并对“否”的答案感到抱歉！

于 2011-11-29T22:34:05.000 回答
4

关于您编辑的问题：是的，如果我们限制内存的大小，所以我们只有有限多个可能的程序，我们理论上可以枚举每个可能的程序并手动将它们分为“下棋”和“下棋” “根据您想要的任何标准。

在这种情况下，我们将不再有图灵机，因此停止问题不适用。相反，我们将有一个有限状态机（是的，这意味着在现实世界中，所有计算机实际上都是图灵机的有限状态近似）。

但是，您添加了这个限制是因为您想要“实用，而不是理论”，所以这里还有一点实用性：枚举所有 256 位程序（有 10 亿台 PC，每台 PC 都枚举了 10 亿个程序）第二）需要比宇宙年龄更长的时间才能完成。那么，您很难想象枚举所有小于 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 回答