3 ms·
No chess problem on a standard board can be the halting problem, because the halting problem requires an "infinite space". I could, in principle, play out all p
by CJefferson 10y ago
No chess problem on a standard board can be the halting problem, because the halting problem requires an "infinite space". I could, in principle, play out all possible states you could reach from this position as a giant graph, and then look to see which path is best by brute force.
There are chess-like problems which invoke the halting problem, but they involve infinite boards with infinite numbers of pieces on them.