29 Mar '08 17:31>2 edits
Is there a chess problem which is undecidable (it cannot be proved if the problem has a solution or not)?
Obviously the board size or something like that should be variable, otherwise the number of possibilities is finite and in theory the (non-)existence of a solution can be determined by brute force search.
If no such problem exists, maybe we can compose one? For example, choose a known math problem which is undecidable, and then compose a chess problem which has a solution if and only if the math problem has a solution. Maybe every math problem can be reduced to a chess problem on a large enough board, in the same way that it can be transformed into a Turing machine or a game-of-life position?
Obviously the board size or something like that should be variable, otherwise the number of possibilities is finite and in theory the (non-)existence of a solution can be determined by brute force search.
If no such problem exists, maybe we can compose one? For example, choose a known math problem which is undecidable, and then compose a chess problem which has a solution if and only if the math problem has a solution. Maybe every math problem can be reduced to a chess problem on a large enough board, in the same way that it can be transformed into a Turing machine or a game-of-life position?