Is there a chess position equivalent to the Collatz conjecture? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T21:56:48Z http://mathoverflow.net/feeds/question/64966 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/64966/is-there-a-chess-position-equivalent-to-the-collatz-conjecture Is there a chess position equivalent to the Collatz conjecture? domotorp 2011-05-14T06:48:24Z 2011-05-17T08:55:13Z <p>Suppose we have an infinite board with a finite number of chess pieces. The question is whether white can checkmate black (without the after 50 moves it is a draw rule). Can you give an explicit position of which you can prove that white can checkmate black if and only if the <a href="http://en.wikipedia.org/wiki/Collatz_conjecture" rel="nofollow">Collatz conjecture</a> is true?</p> <p>This problem is motivated by the fact that for my answer to the question <a href="http://mathoverflow.net/questions/27967/decidability-of-chess-on-an-infinite-board" rel="nofollow">http://mathoverflow.net/questions/27967/decidability-of-chess-on-an-infinite-board</a> I did not get any votes. I strongly believe that chess is undecidable but the proof seems to involve a lot of designing of chess positions. That is why I thought this problem would be a good warm up as the Collatz conjecture seems to be easily realizable with a "chess automaton".</p> <p>First, one should design a position for every number n that can check the parity, divide by 2 or go to 3n+1. I guess this should not be that hard. Then one should devise a mechanism that lets black choose this original number n, maybe something like suggested here <a href="http://mathoverflow.net/questions/63423/checkmate-in-omega-moves/63517#63517" rel="nofollow">http://mathoverflow.net/questions/63423/checkmate-in-omega-moves/63517#63517</a>.</p> <p>If you think this question is not for mathoverflow, please suggest some other forum.</p>