4 ms·
so it's the halting problem? https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Halting_problem
by jlebrech 10y ago
so it's the halting problem? https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Halting_problem
- umanwizard 10y agoHow is this related to the halting problem? I'm not seeing it.
- jlebrech 10y agounless you catch 50 moves it's a runaway algorithm
- umanwizard 10y agoThe fact that a particular algorithm never halts is only tangentially related to the halting problem. It's even possible to write non-halting algorithms in non-Turing-complete systems for which the Halting problem doesn't hold.
- sweeneyrod 10y agono
- CJefferson 10y agoNo 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.