18
$\begingroup$

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?

Improve this question
$\endgroup$
14
  • 8
    $\begingroup$ This question is also posted on math.SE, please read the faq about cross-posting. $\endgroup$
    – Gopi
    Commented Oct 11, 2011 at 21:47
  • 10
    $\begingroup$ 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) $\endgroup$
    – Suresh Venkat
    Commented Oct 11, 2011 at 22:09
  • 9
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Commented Oct 13, 2011 at 23:14
  • 1
    $\begingroup$ @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. $\endgroup$
    – Aaron Sterling
    Commented Oct 14, 2011 at 16:54
  • 2
    $\begingroup$ @JE: The questioner asserted that the answers on other sites were unsatisfactory, so I reopened. $\endgroup$
    – Suresh Venkat
    Commented Oct 15, 2011 at 5:23

2 Answers 2

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Nice though the statement is not too surprising. $\endgroup$
    – domotorp
    Commented Sep 5, 2013 at 13:39
  • 1
    $\begingroup$ @domotorp: I agree :(, but the proof (using a first-order structure definable in the decidable Presburger arithmetic) is neat. $\endgroup$
    – Marzio De Biasi
    Commented Sep 5, 2013 at 14:31
  • $\begingroup$ @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 ... $\endgroup$
    – Marzio De Biasi
    Commented Sep 6, 2013 at 21:34
  • $\begingroup$ 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. $\endgroup$
    – domotorp
    Commented Sep 7, 2013 at 8:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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