patternMinor
Is chess game movement TM decidable?
Viewed 0 times
chessdecidablemovementgame
Problem
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?
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?
Solution
The chess board problem is, although complex, a finite problem. Specifically, the number of moves, starting from any board position, is finite.
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.
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.
Context
StackExchange Computer Science Q#47722, answer score: 6
Revisions (0)
No revisions yet.