一个程序可以确定另一个程序是否下棋吗？
我想知道以下问题。我显然不期望任何实际的解决方案，但我会感谢任何开发人员对此的想法：
理论上是否有可能有一个程序可以打开其他程序（为了便于论证，我们假设它打开 .exe 文件），并确定是否或者不是特定的可执行文件，在执行时（具有固定输入和机器状态），会下棋（以及它可能执行的任何其他任务）。
我所说的“下棋”是指对棋盘和棋子有一定的表示，应用源自内置国际象棋人工智能引擎的黑白棋的后续动作。
这种理论上的“国际象棋检测程序”可能包含虚拟机或 PC 模拟器或任何实际模拟扫描的可执行文件（如果需要）的程序。我们可以假设它在具有同上内存的任意速度的计算机上运行。
（编辑）关于停止问题，我可以这样解决：
将程序加载到一个虚拟机中，该虚拟机有N位（硬盘和内存空间以及CPU寄存器）。该虚拟机最多可以呈现 2^N 种不同的状态。
在VM中一步步执行程序。每执行完一个步骤，检查它是否停止。 如果是：问题已解决（结果：是，它停止）。 如果不是：获取虚拟机的当前状态，并查看该状态是否存在于我们之前遇到过的状态列表中。如果是：问题已解决（结果：否，它将永远运行）。如果否：将此状态添加到列表中并继续。
由于最多可能出现 2^N 种不同的状态，因此该算法将在有限时间内确定程序是否停止。
（编辑2）关于扫描的可执行文件或其运行的（虚拟）机器的（无限）性似乎存在一些含糊之处。假设要扫描的可执行文件最多为 1 GB（这应该足够了，因为大多数国际象棋程序都相当小），并且它们应该在具有 10 GB 内存的 PC（或虚拟机）上运行。
我们理论上的国际象棋检测器程序可以使用任意数量的内存。
I'm wondering about the following issue. I obviously don't expect any practical solutions but I would appreciate any developer's thoughts on this:
Would it be theoretically possible to have a program that opens other programs (for the sake of argument let's say it opens .exe files), and determines whether or not a particular executable, when executed (with fixed input and machine state), plays a game of chess (amongst whatever other tasks it may perform).
With 'play chess' I mean having some representation of a chess board and pieces, applying subsequent moves for black and white originating from a built-in chess AI engine.
Such a theoretical 'chess detection program' may contain a Virtual Machine or PC emulator or whatever to actually simulate the scanned executable if necessary. We can assume it runs on an arbitrarily fast computer with ditto ram.
(Edit) Regarding the halting problem, I can solve that like this:
Load the program in a virtual machine, which has N bits (harddisk and memory space and CPU registers altogether). This virtual machine can assume at most 2^N different states.
Execute the program in the VM step by step. After each step, check if it halted.
If yes: problem solved (result: yes, it halts).
If no: take the current state of the virtual machine, and see if this state exists in a list of states we've already encountered before. If yes: problem solved (result: no it will run forever). If no: add this state to the list and continue.
Since there are at most 2^N different states that can occur, this algorithm will determine whether the program halts or not with certainty in finite time.
(Edit2) There seems to be some ambiguity about the (in)finiteness of the scanned executable or the (virtual) machine it runs on. Let's say the executables to be scanned may be at most 1 GB (which should be enough since most chess programs are considerably smaller) and they're supposed to run on a PC (or VM) with 10 GB of ram.
Our theoretical chess detector program can use an arbitrary amount of ram.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
不，没有这样的算法可以检测可执行文件是否下棋。
证明这一点的事实是，以下问题（称为停止问题）无法通过任何算法解决：
我们可以证明，如果有一个计算机程序可以确定另一个程序是否下棋，我们就可以解决停机问题。为此，我们将编写一个执行以下操作的计算机程序：
该程序有以下有趣的行为：当且仅当程序 P 终止时，它才会下棋。换句话说，如果我们能够检测这个程序是否可以下棋，我们就可以检测程序 P 是否终止。然而，我们知道这显然是不可能做到的，因此一定没有一个程序可以检测某些计算机程序是否下棋。
这种通用方法称为减少停止问题，可以用来表明大量不同的问题可能无法解决。
希望这会有所帮助，并对“否”的答案表示歉意！
No, there is no such algorithm that can detect whether an executable plays chess.
The proof of this rests in the fact that the following problem (called the halting problem) cannot be solved by any algorithm:
We can show that if there was a computer program that could determine whether or not another program plays a game of chess, we could solve the halting problem. To do so, we would write a computer program that does the following:
This program has the following interesting behavior: it plays a game of chess if and only if the program P terminates. In other words, if we could detect whether this program could play chess, we would be detecting whether or not the program P terminates. However, we know that this is provably impossible to do, so there must be not be a program that detects whether some computer program plays chess.
This general approach is called a reduction from the halting problem and can be used to show that a huge number of different problems are probably unsolvable.
Hope this helps, and sorry for the "no" answer!
关于您编辑的问题：是的，如果我们限制内存的大小，因此我们只有有限多个可能的程序，理论上我们可以枚举每个可能的程序，并手动将它们分为“下棋”和“非下棋” “按照你想要的任何标准。
在这种情况下，我们将不再拥有图灵机，因此停止问题不适用。相反，我们有一个有限状态机（是的，这意味着在实际情况中世界上所有计算机实际上都是图灵机的有限状态近似）。
但是，您添加了此限制，因为您想要“实用，而不是理论”，因此这里还有一点实用性：枚举所有 256 位程序（有 10 亿台 PC，每台 PC 都枚举一个每秒十亿个程序）将花费比宇宙年龄更长的时间才能完成。那么，您很难想象枚举所有小于 1 GB（~1,000,000,000 位）的程序需要多长时间。
正因为如此，将真实计算机建模为图灵机实际上比有限状态机更实用；在这个模型下，正如 @templatetypedef 所证明的那样，这是不可能的。
In regards to your edited question: yes, if we limit the size of the memory so we only have finitely-many possible programs, we could theoretically enumerate every possible program and manually divide them into "chess-playing" and "non-chess playing" by whatever set of criteria you wanted.
In this case, we'd no longer have a Turing machine, so the Halting Problem doesn't apply. Instead, we'd have a finite state machine (and yes, this means in the real world, all computers are actually finite-state approximations of a Turing machine).
However, you added this limitation because you wanted to be "practical, not theoretical," so here's another bit of practicality for you: to enumerate all of the 256-bit programs (with a billion PCs, each of which enumerate a billion programs a second) would take significantly longer than the age of the universe to complete. You can hardly imagine, then, how long it would take to enumerate all programs less than 1 GB (~1,000,000,000-bits).
Because of this, it is actually more practical to model real computers as Turing machines than as finite-state machines; and under this model, as @templatetypedef proved, it is impossible.
不，这相当于停机问题。
No. This is equivalent to the halting problem.
程序下棋是什么意思？我不相信存在一个无法解决的问题的精确数学定义，并且不会简单地等同于无法解决的问题。
例如，如果您询问“是否存在该程序下国际象棋的着法编码？”然后一个裸Python解释器下棋 - 根据规定您需要输入的编码：
如果你修复了编码，那么问题就变得无聊了。国际象棋游戏是有限的（根据 50 步规则），因此唯一的难题是“这个程序是否挂在任何有限的国际象棋游戏集的移动之间”。如果它不这样做并且始终尊重编码（并做出有效的移动，所有这些检查都很简单），那么它就会下棋。当然，检查它是否挂起是无法治愈的。列举所有国际象棋比赛是可以处理的，但考虑到实际情况当然也是完全不可能的。
What does it mean that a program plays chess? I don't believe there exists a precise mathematical definition of the problem that couldn't be gamed and wouldn't be trivially equivalent to an untreatable problem.
For example, if you ask "Does there exist an encoding of moves under which this program plays chess?" then a bare Python interpreter plays chess - under the encoding that stipulates that you need to input:
If you fix the encoding, then the problem becomes boring. Chess games are finite (by the 50-move rule), so the only hard question is "does this program hang between moves on any of the finite set of chess games". If it doesn't and always respects the encoding (and makes valid move, all this is trivial to check) then it plays chess. Of course checking if it hangs is untreatable. Enumerating all chess games is treatable but of course also totally impossible given practical considerations.