I would like to convince everyone that this problem is undecidable. I cannot prove it 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. Hm, after reading the comments to the original question carefully, I realised that there is already a pointer to an argument very similar to mine: http://www.redhotpawn.com/board/showthread.php?threadid=90513&page=1#post_1708006

The reduction relies on the notion of counter machine*. It is undecidable whether a counter machine with only two counters halts or not. 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.

*I realized that the definition on wikipedia is different from what I want. In fact, my machine should be probably called a 2-stack machine that can push only one letter to the stack. So I want a finite state machine with two counters that are empty at the beginning and it can increase or decrease any counter by one or check whether a counter is zero or not. The problem of whether such a machine halts or not, is undecidable.

I would like to convince everyone that this problem is undecidable. I cannot prove it 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. 

Hm, after reading the comments to the original question carefully, I realised that there is already a pointer to an argument very similar to mine by Tsuyoshi Ito: http://www.redhotpawn.com/board/showthread.php?threadid=90513&page=1#post_1708006 I still leave my proof here, as in fact two counters are enough and maybe mine is more detailed.

The reduction relies on the notion of counter machine*. It is undecidable whether a counter machine with only two counters halts or not. 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.

*I realized that the definition on wikipedia is different from what I want. In fact, my machine should be probably called a 2-stack machine that can push only one letter to the stack. So I want a finite state machine with two counters that are empty at the beginning and it can increase or decrease any counter by one or check whether a counter is zero or not. The problem of whether such a machine halts or not, is undecidable.

I would like to convince everyone that this problem is undecidable. I cannot prove it 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.

The reduction relies on the notion of counter machine*. It is undecidable whether a counter machine with only two counters halts or not. 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.

*I realized that the definition on wikipedia might be different from what I want. I want a finite state machine with two counters that are empty at the beginning and it can increase or decrease any counter by one or check whether a counter is zero or not.

I would like to convince everyone that this problem is undecidable. I cannot prove it 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. Hm, after reading the comments to the original question carefully, I realised that there is already a pointer to an argument very similar to mine: http://www.redhotpawn.com/board/showthread.php?threadid=90513&page=1#post_1708006

The reduction relies on the notion of counter machine*. It is undecidable whether a counter machine with only two counters halts or not. 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.

*I realized that the definition on wikipedia is different from what I want. In fact, my machine should be probably called a 2-stack machine that can push only one letter to the stack. So I want a finite state machine with two counters that are empty at the beginning and it can increase or decrease any counter by one or check whether a counter is zero or not. The problem of whether such a machine halts or not, is undecidable.