17

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?

TROLLHUNTER
  • 209
  • 2
  • 6
  • 8
    This question is also posted on math.SE, please read the faq about cross-posting. – Gopi Oct 11 '11 at 21:47
  • 10
    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 Oct 11 '11 at 22:09
  • 9
    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 Oct 13 '11 at 23:14
  • 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? – Gopi Oct 14 '11 at 15:07
  • This question has a bounty both here and at math.SE. Does (or should) this violate the cross-posting policy? – Jeffε Oct 14 '11 at 15:09
  • Chess is EXP-Complete.. So No. – Tayfun Pay Oct 14 '11 at 15:50
  • 1
    @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 Oct 14 '11 at 16:54
  • Oups, I also missed the infinite board part. – Gopi Oct 14 '11 at 17:09
  • @Aaron Thank you for pointing that out! I missed that part of the question. – Tayfun Pay Oct 14 '11 at 22:12
  • 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 Oct 14 '11 at 22:33
  • 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 Oct 14 '11 at 22:39
  • @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 Oct 15 '11 at 00:24
  • 2
    @JE: The questioner asserted that the answers on other sites were unsatisfactory, so I reopened. – Suresh Venkat Oct 15 '11 at 05:23
  • 1
    This question, and N. Elkies' answer to it, seem particularly relevant. – Aaron Sterling Oct 16 '11 at 02:14

2 Answers2

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

Community
  • 1
domotorp
  • 13,931
  • 37
  • 93
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)

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.

Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127
  • Nice though the statement is not too surprising. – domotorp Sep 05 '13 at 13:39
  • 1
    @domotorp: I agree :(, but the proof (using a first-order structure definable in the decidable Presburger arithmetic) is neat. – Marzio De Biasi Sep 05 '13 at 14:31
  • @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 ... ... 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 Sep 06 '13 at 21:34
  • 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 Sep 07 '13 at 08:05