# Q: Is chess game movement TM decidable?

If we have a finite chess board and two figures x and y. Is it possible to get y from x by following chess rules and when white is y and white starts from y placement. Is this decidable?

My reasoning is, that we have a finite sets of moves and since all finite languages are decidable and at some point x is going to get y this problem is decidable. What do you think?

• BFS on the graph of all possible positions, where two positions are connect if you can reach from one to the other in a single move (a pretty big graph, but who cares). – Ariel Sep 30 '15 at 12:47
• If the size of your board is fixed, it's even decidable in constant time. – François Sep 30 '15 at 12:59
• Note that there are cycles in chess. (In particular, even though the 50-move rule exists it requires a player to claim it, and a player may not claim it) As such, you do need to do a proper graph search. Otherwise your TM won't decide the question, just accept it, as in the case of y not being reachable from x it'll potentially get caught in a loop and never halt. – TLW Sep 30 '15 at 19:01

Then, a TM can just go over all the possible moves (there are only $C$ such moves, for some "small" constant $C$), and verify if a certain position is feasible continuation of a prior position. Hence, any such question is decidable.