Could a program determine if another program plays chess?

Question

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.

Answer 1

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:

Given a computer program, does that program eventually terminate?

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:

1. Take as input some other computer program P.
2. Run program P.
3. If program P terminates, play a game of chess.

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!