20
$\begingroup$

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff the program halts?

The rules are the same as ordinary chess minus the 50 move rule, exchanges and castling.

And what is the minimum number of different types of pieces (i.e. the simplest game) that is needed for a chess-like game to be Turing-complete? (Each type of piece having a set of allowed moves that is invariant under translations)

  • 8
    How different from regular chess can the rules of the game be in order to call it "chess"?2011-10-11
  • 0
    The rules must be the same as ordinary chess except pawn-exchange and castling. This includes the game ending if it is in the same state 3 times.2011-10-11
  • 6
    There is a closely related question on MathOverflow: [Decidability of chess on an infinite board](http://mathoverflow.net/questions/27967/decidability-of-chess-on-an-infinite-board).2011-10-11
  • 2
    Also crossposted on cstheory.SE: http://cstheory.stackexchange.com/questions/8582/can-chess-simulate-a-universal-turing-machine#question2011-10-11
  • 0
    Is the first part of the question the same as the linked MO question?2011-10-14
  • 0
    On an infinite board, will we still restrict movement to a maximum of 8 squares at a time? I doubt that this will affect the answer, but it would be nice (in general) to figure out exactly what changes for chess on an `infinite board'.2011-10-17

4 Answers 4