<p>I also think that a very similar question has been asked before, I think first here: <a href="https://mathoverflow.net/questions/27967/decidability-of-chess-on-an-infinite-board/63684">https://mathoverflow.net/questions/27967/decidability-of-chess-on-an-infinite-board/63684</a>
Here is my updated and modified opinion.</p>

<p>I think the problem is not solved completely, but the answer is almost surely yes. I do not have a proof for chess, as I lack the ability to design certain configurations but I think they must exist. And even if they don't, for some chess-like game they certainly do which shows that the attempts to prove decidability should be incorrect. Later I realized that there is a very similar argument to mine here: <a href="http://www.redhotpawn.com/board/showthread.php?threadid=90513&amp;page=1#post_1708006" rel="nofollow noreferrer">http://www.redhotpawn.com/board/showthread.php?threadid=90513&amp;page=1#post_1708006</a> but my proof shows that in fact two counters are enough and maybe mine is more detailed.</p>

<p>The reduction relies on the notion of a stack machine. A stack machine with only two stacks using a stack alphabet of only one letter can simulate any Turing-machine. (Some people would call this deterministic finite automaton with two counters.) So our goal would be to simulate any such machine with a chess position. I can see two ways for this.</p>

<p>i, Build two separate configurations, such that both have a starting part and a moving part that can change (to store the state). Also, the moving parts would be connected, eg. by rooks, which could checkmate, if released, so this is why if one states moves 1, the other has to move k, and so on.</p>

<p>ii, Build a single configuration, that depending on its state, moves l horizontally and -k vertically. Also, place a rook at (0,0) that would never move but could guarantee that the configuration can "sense" when it gets back to an empty counter.</p>

<p>So all left to do is to design such configurations, which I guess should be possible with some effort and knowledge of chess. Also, note that in both cases the construction uses a piece whose range is not bounded, I wonder if this is really necessary. As a first step, I proposed to give a position equivalent to the Collatz conjecture:
<a href="https://mathoverflow.net/questions/64966/is-there-a-chess-position-equivalent-to-the-collatz-conjecture">https://mathoverflow.net/questions/64966/is-there-a-chess-position-equivalent-to-the-collatz-conjecture</a></p>

CC BY-SA 3.0
2011-10-15T05:12:57.010Z
2011-10-15T05:12:57.010Z
2017-04-13T12:57:54.777Z
domotorp
<p>Yesterday I googled around to check the status of this problem and I found this new (2012) result:</p>

<p><a href="http://arxiv.org/abs/1201.5597" rel="nofollow">Dan Brumleve, Joel David Hamkins and Philipp Schlicht, The mate-in-n problem of infinite chess is decidable (2012)</a> </p>

<p>So the mate-in-n problem of infinite chess cannot be Turing complete.</p>

<p>The decidability of infinite chess  with no restrictions on the number of moves for a mate seems still open.</p>

CC BY-SA 3.0
2013-09-05T13:39:49.903Z
Nice though the statement is not too surprising.
domotorp
CC BY-SA 3.0
2013-09-05T14:31:06.497Z
@domotorp: I agree :(, but the proof (using a first-order structure definable in the decidable Presburger arithmetic) is neat.
Marzio De Biasi
CC BY-SA 3.0
2013-09-06T21:34:49.937Z
@domotorp: ... I'm trying to understand this part: "... We now argue that the collection of such sequences of strings arising from positions is regular, by recognizing with a read-only multi-tape Turing machine that they obey the necessary requirements ... <requirements> ... *and no two live pieces occupy the same square* ...". 99.99% I'm misinterpreting it, but I don't see how a regular string can embed the information that two pieces are on distinct squares ...
Marzio De Biasi
CC BY-SA 3.0
2013-09-07T08:05:58.673Z
so I am not really familiar with this topic but isn't the thing that they have a multi-tape T-machine? It seems that they have each string on a separate tape and then it's simple to check. I guess having two tapes with the interleaved string would be just as good, if we want a bounded number of tapes.
domotorp
CC BY-SA 3.0
2013-09-05T08:24:21.917Z
2013-09-05T08:24:21.917Z
Marzio De Biasi
<p>I am looking to get a definite answer to title question.</p>

<p>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?</p>

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

<p>And what is the minimum number of different types of pieces (ie 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).</p>

<p>Is there any piece we can add to the game to prove it turing complete?</p>

CC BY-SA 3.0
2011-10-11T21:47:37.280Z
This question is also posted on [math.SE](http://math.stackexchange.com/questions/71760/is-chess-turing-complete), please read the [faq](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231) about cross-posting.
Gopi
CC BY-SA 3.0
2011-10-11T22:09:38.797Z
You only just posted this on math.SE and already received a helpful pointer to an MO link, as well as an answer. If these turn out not to be suitable, you may crosspost here, but in general we prefer not to have simultaneous crossposting as it causes discussion fracture and repetition. I'm closing for now, but you can flag it for reopening if you don't receive satisfactory answers elsewhere (please ignore the "reason for closing" - we only have a few choices)
Suresh Venkat
CC BY-SA 3.0
2011-10-13T23:14:10.023Z
It seems quite unlikely, as chess has only a fiwed number of pieces in any game, and a universal Turing machine has an unbounded number of bits. However, this isn't a proof.
Peter Shor 
CC BY-SA 3.0
2011-10-14T15:07:09.120Z
Could we see a game of chess as a finite automaton (all the configurations of the chess game: every pieces in every possible cases), then you have the transitions which consist in a move for a player. This is a regular language, hence it is [not Turing complete](http://en.wikipedia.org/wiki/Turing_completeness#Non-Turing-complete_languages)?
Gopi
CC BY-SA 3.0
2011-10-14T15:09:11.410Z
This question has a bounty both here and at math.SE.  Does (or should) this violate the cross-posting policy?
Jeffε
CC BY-SA 3.0
2011-10-14T15:50:51.310Z
Chess is EXP-Complete.. So No.
Tayfun Pay
CC BY-SA 3.0
2011-10-14T16:54:33.143Z
@Tayfun Pay: You're "solving" a different problem.  The EXP-C version of chess has specific pieces assigned to the board, depending on the value of the board width $n$.  The number of rooks, etc., grows as a fraction of $n$.  The question asked here is (a) infinite board, and (b) any number of pieces, in any proportion to one another.
Aaron Sterling
CC BY-SA 3.0
2011-10-14T17:09:37.637Z
Oups, I also missed the infinite board part.
Gopi
CC BY-SA 3.0
2011-10-14T22:12:26.413Z
@Aaron Thank you for pointing that out! I missed that part of the question.
Tayfun Pay
CC BY-SA 3.0
2011-10-14T22:33:00.130Z
Proof idea: represent a Turing machine state in unary. Choose a leftmost Columbus that encoded zero. Place a rook on the square that is that many cells to the right of zero. the took moves left or right, to the square that encodes the next state of the machine in unary.
Aaron Sterling
CC BY-SA 3.0
2011-10-14T22:39:48.377Z
Set up the pawn structure so that if white performs the room moves correctly, black has a forced move, and if white moves wrong black can force stalemate.  Then white wins iff there is a mating set of rook moves iff the machine halts. The game might not run forever, but I don't think we need it to.
Aaron Sterling
CC BY-SA 3.0
2011-10-15T00:24:01.747Z
@AaronSterling The problem is that the rook moves would have to be unbounded (since the TM state/tape can get arbitrarily large) and so you'd need infinitely many pawns to keep it in check, at least at first glance...
Steven Stadnicki
CC BY-SA 3.0
2011-10-15T05:23:37.483Z
@JE: The questioner asserted that the answers on other sites were unsatisfactory, so I reopened.
Suresh Venkat
CC BY-SA 3.0
2011-10-16T02:14:53.277Z
[This question](http://mathoverflow.net/questions/63423/checkmate-in-omega-moves/63517#63517), and N. Elkies' answer to it, seem particularly relevant.
Aaron Sterling
<computability><turing-machines><board-games><halting-problem><recreational>
Can chess simulate a Universal Turing Machine?
TROLLHUNTER
# Can chess simulate a Universal Turing Machine?

(Asked by: username_0 on 2011-10-11)

I am looking to get a definite answer to title question.

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 (ie 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).

Is there any piece we can add to the game to prove it turing complete?

**Tags:** computability, turing-machines, board-games, halting-problem, recreational

> **Comments:**
> **username_1**: This question is also posted on [math.SE](http://math.stackexchange.com/questions/71760/is-chess-turing-complete), please read the [faq](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231) about cross-posting.  
> **username_2**: You only just posted this on math.SE and already received a helpful pointer to an MO link, as well as an answer. If these turn out not to be suitable, you may crosspost here, but in general we prefer not to have simultaneous crossposting as it causes discussion fracture and repetition. I'm closing for now, but you can flag it for reopening if you don't receive satisfactory answers elsewhere (please ignore the "reason for closing" - we only have a few choices)  
> **username_3**: It seems quite unlikely, as chess has only a fiwed number of pieces in any game, and a universal Turing machine has an unbounded number of bits. However, this isn't a proof.  
> **username_1**: Could we see a game of chess as a finite automaton (all the configurations of the chess game: every pieces in every possible cases), then you have the transitions which consist in a move for a player. This is a regular language, hence it is [not Turing complete](http://en.wikipedia.org/wiki/Turing_completeness#Non-Turing-complete_languages)?  
> **username_4**: This question has a bounty both here and at math.SE.  Does (or should) this violate the cross-posting policy?  
> **username_5**: Chess is EXP-Complete.. So No.  
> **username_6**: @username_5: You're "solving" a different problem.  The EXP-C version of chess has specific pieces assigned to the board, depending on the value of the board width $n$.  The number of rooks, etc., grows as a fraction of $n$.  The question asked here is (a) infinite board, and (b) any number of pieces, in any proportion to one another.  
> **username_1**: Oups, I also missed the infinite board part.  
> **username_5**: @Aaron Thank you for pointing that out! I missed that part of the question.  
> **username_6**: Proof idea: represent a Turing machine state in unary. Choose a leftmost Columbus that encoded zero. Place a rook on the square that is that many cells to the right of zero. the took moves left or right, to the square that encodes the next state of the machine in unary.  
> **username_6**: Set up the pawn structure so that if white performs the room moves correctly, black has a forced move, and if white moves wrong black can force stalemate.  Then white wins iff there is a mating set of rook moves iff the machine halts. The game might not run forever, but I don't think we need it to.  
> **username_7**: @AaronSterling The problem is that the rook moves would have to be unbounded (since the TM state/tape can get arbitrarily large) and so you'd need infinitely many pawns to keep it in check, at least at first glance...  
> **username_2**: @JE: The questioner asserted that the answers on other sites were unsatisfactory, so I reopened.  
> **username_6**: [This question](http://mathoverflow.net/questions/63423/checkmate-in-omega-moves/63517#63517), and N. Elkies' answer to it, seem particularly relevant.  

---

## 2 answers

### Answer by username_8 on 2011-10-15. Score: 5

I also think that a very similar question has been asked before, I think first here: <https://mathoverflow.net/questions/27967/decidability-of-chess-on-an-infinite-board/63684>
Here is my updated and modified opinion.

I think the problem is not solved completely, but the answer is almost surely yes. I do not have a proof for chess, as I lack the ability to design certain configurations but I think they must exist. And even if they don't, for some chess-like game they certainly do which shows that the attempts to prove decidability should be incorrect. Later I realized that there is a very similar argument to mine here: <http://www.redhotpawn.com/board/showthread.php?threadid=90513&page=1#post_1708006> but my proof shows that in fact two counters are enough and maybe mine is more detailed.

The reduction relies on the notion of a stack machine. A stack machine with only two stacks using a stack alphabet of only one letter can simulate any Turing-machine. (Some people would call this deterministic finite automaton with two counters.) So our goal would be to simulate any such machine with a chess position. I can see two ways for this.

i, Build two separate configurations, such that both have a starting part and a moving part that can change (to store the state). Also, the moving parts would be connected, eg. by rooks, which could checkmate, if released, so this is why if one states moves 1, the other has to move k, and so on.

ii, Build a single configuration, that depending on its state, moves l horizontally and -k vertically. Also, place a rook at (0,0) that would never move but could guarantee that the configuration can "sense" when it gets back to an empty counter.

So all left to do is to design such configurations, which I guess should be possible with some effort and knowledge of chess. Also, note that in both cases the construction uses a piece whose range is not bounded, I wonder if this is really necessary. As a first step, I proposed to give a position equivalent to the Collatz conjecture:
<https://mathoverflow.net/questions/64966/is-there-a-chess-position-equivalent-to-the-collatz-conjecture>


---

### Answer by username_9 on 2013-09-05. Score: 4

Yesterday I googled around to check the status of this problem and I found this new (2012) result:

[Dan Brumleve, Joel David Hamkins and Philipp Schlicht, The mate-in-n problem of infinite chess is decidable (2012)](http://arxiv.org/abs/1201.5597)

So the mate-in-n problem of infinite chess cannot be Turing complete.

The decidability of infinite chess with no restrictions on the number of moves for a mate seems still open.

> **Comments:**
> **username_8**: Nice though the statement is not too surprising.  
> **username_9**: @username_8: I agree :(, but the proof (using a first-order structure definable in the decidable Presburger arithmetic) is neat.  
> **username_9**: @username_8: ... I'm trying to understand this part: "... We now argue that the collection of such sequences of strings arising from positions is regular, by recognizing with a read-only multi-tape Turing machine that they obey the necessary requirements ... <requirements> ... *and no two live pieces occupy the same square* ...". 99.99% I'm misinterpreting it, but I don't see how a regular string can embed the information that two pieces are on distinct squares ...  
> **username_8**: so I am not really familiar with this topic but isn't the thing that they have a multi-tape T-machine? It seems that they have each string on a separate tape and then it's simple to check. I guess having two tapes with the interleaved string would be just as good, if we want a bounded number of tapes.  

---

