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 Collatz conjecture is true?

This problem is motivated by the fact that for my answer to the question Decidability of chess on an infinite board 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".

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 Checkmate in $\omega$ moves?.

If you think this question is not for mathoverflow, please suggest some other forum.

  • 12
    $\begingroup$ Don't you have to be careful with question like this to be quite precise? At the minute can't I just say "the answer is yes because Collatz is either true or false and in either case such a position exists"? $\endgroup$ – Kevin Buzzard May 14 '11 at 6:55
  • $\begingroup$ PS see Carl Mummert's answer to the first question you link to, and subsequent comments, for more evidence that, without a completely rigorous specification of what you're after, the question is ambiguous (and perhaps even subjective and argumentative!) $\endgroup$ – Kevin Buzzard May 14 '11 at 7:10
  • 3
    $\begingroup$ Note: domotorp has edited the question now and my first comment (made about a previous version) is no longer valid :-/ $\endgroup$ – Kevin Buzzard May 14 '11 at 8:15
  • 1
    $\begingroup$ Really, why can it not be formulated as a halting problem? Take a Turing machine that on input n, divides by 2 if n is even and outputs 3n+1, if n is odd, and keeps repeating this until it reaches 1. To decide whether this machine stops is a halting problem. Also, in a more complicated way, I think any mathematical statement can be formulated as whether a Turing-machine halts - just take one that tries to enumerate all possible proofs and check if one of them is correct. $\endgroup$ – domotorp May 14 '11 at 16:33
  • 2
    $\begingroup$ domotorp, for a particular n, it is a halting problem, but the Collatz conjecture is for any n. Enumerating the proofs only works with completeness. And we know that logics are not complete. $\endgroup$ – Lucas K. May 14 '11 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.