Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
How different from regular chess can the rules of the game be in order to call it "chess"? –  Robert Israel Oct 11 '11 at 17:22
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. –  coffeemachine Oct 11 '11 at 17:33
There is a closely related question on MathOverflow: Decidability of chess on an infinite board. –  Tsuyoshi Ito Oct 11 '11 at 18:52
Also crossposted on cstheory.SE: cstheory.stackexchange.com/questions/8582/… –  Suresh Venkat Oct 11 '11 at 22:08
Is the first part of the question the same as the linked MO question? –  sdcvvc Oct 14 '11 at 1:30
show 1 more comment

1 Answer

The classic reference on this is the paper "Computing a Perfect Strategy for nxn Chess Requires Time Exponential in n" by Aviezri Fraenkel and David Lichtenstein; unfortunately, I can't find the (30-year-old!) paper online anywhere and while I think I have the proceedings it came from, it's buried in a pile of boxes. Of course, your board isn't finite, but your initial piece configuration is; this means that if there's any computable bound on the needed board size to resolve an initial position, then chess isn't Turing-complete. (If the status of all positions of diameter $d$ could be determined using boards of size no more than $f(d)$, then they can be determined in $\mathrm{EXP}(f(d))$ time by the EXPTIME completeness result, and thus wouldn't be Turing-complete). I vaguely recall seeing something about such a result, but unfortunately some quick searches aren't turning anything up. The expert on the mathematics of chess is Noam Elkies, so hopefully he can spot this and chime in...

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.