7
$\begingroup$

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.

Improve this question
$\endgroup$
15
  • 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
    Commented May 14, 2011 at 6:55
  • 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
    Commented May 14, 2011 at 8:15
  • 1
    $\begingroup$ I want to mention that in its original form, the Collatz conjecture is not a Halting problem (although someone might have found it equivalent to a Halting problem, I don't know). The Collatz conjecture is a (\Pi^0_2) question. So, even if halting problems can be expressed as chess problems on an infinite board, it doesn't mean that Collatz conjecture can be expressed as it. So, this question seems to be more complicated than 27967. $\endgroup$
    – Lucas K.
    Commented May 14, 2011 at 12:13
  • 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
    Commented May 14, 2011 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.
    Commented May 14, 2011 at 22:50

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .