Skip to main content
replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link

Steven Landsburg has now answered the question in the case of ordinary finite chess, which because it is finite has no undecidability or independence phenomenon to speak of.

Meanwhile, the kind of phenomenon you seek in Q1, Q2 and Q3 does seem to occur in the context of infinite chess, where one plays from a finite position on an infinite board. This would be a somewhat vaster state space than you had suggested, since it is infinite, but the argument that Steven mentions shows that an infinite state space is a necessary condition for undecidability.

Specifically, as I explain in my answer to Richard Stanley's question on the Decidability of chess on an infinite boardDecidability of chess on an infinite board (see also my blog posts on infinite chess), my co-authors and I prove the decidability of the mate-in-$n$ problem of infinite chess by introducing what we call the first-order structure of chess $\frak{Ch}$, with the associated formal language of chess, in which various chess concepts are expressible. Our proof proceeds by showing that this structure is an automatic structure in the sense of finite automata theory, and its theory is consequently decidable. Thus, any infinite chess concept expressible in this formal language of chess will be decidable.

Meanwhile, not all chess concepts seem to be expressible in this particular formal language, and in particular it remains open whether the won-position problem is decidable. If it isn't, then like all undecidable problems, it will involve an independence phenomenon as in Q3, for there will be specific finite positions in infinite chess, such that the question of whether or not they are won for white or not will be independent of your favorite axiomatization.

Thus, your desired independence phenomenon seems intimately connected with the decidability problem in this infinitary context.

Steven Landsburg has now answered the question in the case of ordinary finite chess, which because it is finite has no undecidability or independence phenomenon to speak of.

Meanwhile, the kind of phenomenon you seek in Q1, Q2 and Q3 does seem to occur in the context of infinite chess, where one plays from a finite position on an infinite board. This would be a somewhat vaster state space than you had suggested, since it is infinite, but the argument that Steven mentions shows that an infinite state space is a necessary condition for undecidability.

Specifically, as I explain in my answer to Richard Stanley's question on the Decidability of chess on an infinite board (see also my blog posts on infinite chess), my co-authors and I prove the decidability of the mate-in-$n$ problem of infinite chess by introducing what we call the first-order structure of chess $\frak{Ch}$, with the associated formal language of chess, in which various chess concepts are expressible. Our proof proceeds by showing that this structure is an automatic structure in the sense of finite automata theory, and its theory is consequently decidable. Thus, any infinite chess concept expressible in this formal language of chess will be decidable.

Meanwhile, not all chess concepts seem to be expressible in this particular formal language, and in particular it remains open whether the won-position problem is decidable. If it isn't, then like all undecidable problems, it will involve an independence phenomenon as in Q3, for there will be specific finite positions in infinite chess, such that the question of whether or not they are won for white or not will be independent of your favorite axiomatization.

Thus, your desired independence phenomenon seems intimately connected with the decidability problem in this infinitary context.

Steven Landsburg has now answered the question in the case of ordinary finite chess, which because it is finite has no undecidability or independence phenomenon to speak of.

Meanwhile, the kind of phenomenon you seek in Q1, Q2 and Q3 does seem to occur in the context of infinite chess, where one plays from a finite position on an infinite board. This would be a somewhat vaster state space than you had suggested, since it is infinite, but the argument that Steven mentions shows that an infinite state space is a necessary condition for undecidability.

Specifically, as I explain in my answer to Richard Stanley's question on the Decidability of chess on an infinite board (see also my blog posts on infinite chess), my co-authors and I prove the decidability of the mate-in-$n$ problem of infinite chess by introducing what we call the first-order structure of chess $\frak{Ch}$, with the associated formal language of chess, in which various chess concepts are expressible. Our proof proceeds by showing that this structure is an automatic structure in the sense of finite automata theory, and its theory is consequently decidable. Thus, any infinite chess concept expressible in this formal language of chess will be decidable.

Meanwhile, not all chess concepts seem to be expressible in this particular formal language, and in particular it remains open whether the won-position problem is decidable. If it isn't, then like all undecidable problems, it will involve an independence phenomenon as in Q3, for there will be specific finite positions in infinite chess, such that the question of whether or not they are won for white or not will be independent of your favorite axiomatization.

Thus, your desired independence phenomenon seems intimately connected with the decidability problem in this infinitary context.

added 440 characters in body; added 1 characters in body
Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

TheSteven Landsburg has now answered the question in the case of ordinary finite chess, which because it is finite has no undecidability or independence phenomenon to speak of.

Meanwhile, the kind of reasoning thatphenomenon you seem to seek in Q1 and, Q2 and Q3 does seem to occur in the analysiscontext of infinite as opposed to finite chess, where one plays from a finite position on an infinite board. ItThis would be a somewhat vaster state space than you had suggested, since it is open whetherinfinite, but the independence phenomenon of Q3 arises inargument that Steven mentions shows that an infinite chessstate space is a necessary condition for undecidability.

Specifically, as I explain in my answer to Richard Stanley's question on the Decidability of chess on an infinite board (see also my blog posts on infinite chess), my co-authors and I prove the decidability of the mate-in-$n$ problem of infinite chess by introducing what we call the first-order structure of chess $\frak{Ch}$, with the associated formal language of chess, in which various chess concepts are expressible. Our proof proceeds by showing that this structure is an automatic structure in the sense of finite automata theory, and its theory is consequently decidable. Thus, any infinite chess concept expressible in this formal language of chess will be decidable.

Meanwhile, not all chess concepts seem to be expressible in this particular formal language, and in particular it remains open whether the won-position problem is decidable. If it isn't, then like all undecidable problems, it will involve an independence phenomenon as in Q3, for there will be specific finite positions in infinite chess, such that the question of whether or not they are won for white or not will be independent of your favorite axiomatization.

Thus, your desired independence phenomenon seems intimately connected with the decidability problem in this infinitary context.

The kind of reasoning that you seem to seek in Q1 and Q2 does seem to occur in the analysis of infinite as opposed to finite chess. It is open whether the independence phenomenon of Q3 arises in infinite chess.

Specifically, in my answer to Richard Stanley's question on the Decidability of chess on an infinite board, my co-authors and I prove the decidability of the mate-in-$n$ problem of infinite chess by introducing what we call the first-order structure of chess $\frak{Ch}$, with the associated formal language of chess, in which various chess concepts are expressible. Our proof proceeds by showing that this structure is an automatic structure in the sense of finite automata theory, and its theory is consequently decidable. Thus, any infinite chess concept expressible in this formal language of chess will be decidable.

Meanwhile, not all chess concepts seem to be expressible in this particular formal language, and in particular it remains open whether the won-position problem is decidable. If it isn't, then like all undecidable problems, it will involve an independence phenomenon as in Q3, for there will be specific finite positions in infinite chess, such that the question of whether or not they are won for white or not will be independent of your favorite axiomatization.

Thus, your desired independence phenomenon seems intimately connected with the decidability problem in this infinitary context.

Steven Landsburg has now answered the question in the case of ordinary finite chess, which because it is finite has no undecidability or independence phenomenon to speak of.

Meanwhile, the kind of phenomenon you seek in Q1, Q2 and Q3 does seem to occur in the context of infinite chess, where one plays from a finite position on an infinite board. This would be a somewhat vaster state space than you had suggested, since it is infinite, but the argument that Steven mentions shows that an infinite state space is a necessary condition for undecidability.

Specifically, as I explain in my answer to Richard Stanley's question on the Decidability of chess on an infinite board (see also my blog posts on infinite chess), my co-authors and I prove the decidability of the mate-in-$n$ problem of infinite chess by introducing what we call the first-order structure of chess $\frak{Ch}$, with the associated formal language of chess, in which various chess concepts are expressible. Our proof proceeds by showing that this structure is an automatic structure in the sense of finite automata theory, and its theory is consequently decidable. Thus, any infinite chess concept expressible in this formal language of chess will be decidable.

Meanwhile, not all chess concepts seem to be expressible in this particular formal language, and in particular it remains open whether the won-position problem is decidable. If it isn't, then like all undecidable problems, it will involve an independence phenomenon as in Q3, for there will be specific finite positions in infinite chess, such that the question of whether or not they are won for white or not will be independent of your favorite axiomatization.

Thus, your desired independence phenomenon seems intimately connected with the decidability problem in this infinitary context.

Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

The kind of reasoning that you seem to seek in Q1 and Q2 does seem to occur in the analysis of infinite as opposed to finite chess. It is open whether the independence phenomenon of Q3 arises in infinite chess.

Specifically, in my answer to Richard Stanley's question on the Decidability of chess on an infinite board, my co-authors and I prove the decidability of the mate-in-$n$ problem of infinite chess by introducing what we call the first-order structure of chess $\frak{Ch}$, with the associated formal language of chess, in which various chess concepts are expressible. Our proof proceeds by showing that this structure is an automatic structure in the sense of finite automata theory, and its theory is consequently decidable. Thus, any infinite chess concept expressible in this formal language of chess will be decidable.

Meanwhile, not all chess concepts seem to be expressible in this particular formal language, and in particular it remains open whether the won-position problem is decidable. If it isn't, then like all undecidable problems, it will involve an independence phenomenon as in Q3, for there will be specific finite positions in infinite chess, such that the question of whether or not they are won for white or not will be independent of your favorite axiomatization.

Thus, your desired independence phenomenon seems intimately connected with the decidability problem in this infinitary context.