0
$\begingroup$

Consider a deterministic, perfect information, abstract strategy, finite game , with absurdly large state space, say ...chess

Q1 Is the game translatable to an axiomatic system?

Q2 Can all statements in the game be proven or dis proven, are they decidable? Do we have an 'Incompleteness" at play here? (Assuming that the game has not/cannot be solved given our computation resources.)

Examples : Statements in Chess :

*"There is a set of moves (starting from initial position) which lead white to win regardless
of black's moves" (Perfect strategy)

"There is a set of moves which lead white not to loose regardless of black's moves" (Perfect strategy)

"All games are decidable (White wins looses or stalemates)after n-moves into the game" (Forcing a win)

"Given a position, exists a function which tells if a game is decidable from that point on"*

Q3 Is there an 'intuitive' truth in statements of chess, say as seen by grandmasters which can not be proven?

Aim of the questions is to check behavior for infinitely large state spaces with rule based transitions.

Improve this question
$\endgroup$
6
  • $\begingroup$ What does it mean for something to be "homologous" to an axiomatic system? $\endgroup$
    – Gerry Myerson
    Commented Jun 12, 2013 at 6:02
  • 1
    $\begingroup$ Not really an answer but a comment to the statement “Assuming that the game has not/cannot be solved given our compute resources”. Let’s look at the calculations showing how difficult it is to solve chess by brute-force. Chess game tree complexity = 10^123 ; Bremermann's Limit = 1.36 × 10^50 bits per second per kilogram ; Mass of the Universe = 10^53 kg ; Age of the universe = 4.354 × 10^17 seconds ; No. of chess games analyzed by the universe turned into the best computer possible < 10^121 $\endgroup$
    – Waldemar
    Commented Jun 12, 2013 at 6:56
  • 2
    $\begingroup$ That "given our computational resources" bit makes it much trickier to view this as an axiomatic system, because proofs aren't entirely compositional. Knowing that a proof of $p$ exists and that a proof of $q$ exists does not necessarily imply that a proof of $p \land q$ exists—the latter proof may be too long to be valid. $\endgroup$
    – dfeuer
    Commented Jun 12, 2013 at 7:39
  • 1
    $\begingroup$ Looking at your other questions as well, I think you should put in more effort to make precise what you are asking for. I have no idea what an answer to this question, for example, would consist of. $\endgroup$
    – Noah Schweber
    Commented Jun 12, 2013 at 12:49
  • 1
    $\begingroup$ It might be off-topic, but this reminds me of a nice description/comparison by Bourbaki: « Si la mathématique formalisée était aussi simple que le jeu d’échecs, une fois décrit le langage formalisé que nous avons choisi, il n’y aurait plus qu’à rédiger nos démonstrations dans ce langage, comme l’auteur d’un traité d’échecs écrit dans sa notation les parties qu’il se propose d’enseigner, en les accompagnant au besoin de commentaires. » $\endgroup$
    – The User
    Commented Jun 12, 2013 at 13:21

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Yes, I know you asked about a finite board. But on a finite board, the decidability and independence questions are trivial, since every finite set is Turing computable. $\endgroup$
    – Joel David Hamkins
    Commented Jun 12, 2013 at 13:36
  • 2
    $\begingroup$ As for Waldemar's comment, that objection applies universally to every decidability question. But are we really to answer every decidability question with the observation that universe is finite? Once we all know, this observation, we can agree that it is commonly known. Meanwhile, the Turing computability concept provides an extremely robust concept of idealized computability, which enables deep insight into computability issues. And I'm still interested in that concept, even though the physical universe may be finite. $\endgroup$
    – Joel David Hamkins
    Commented Jun 12, 2013 at 13:40
  • 1
    $\begingroup$ If I could add sth myself. My comment was just a trivia. It wasn’t intended as an objection to anything. It has nth to do with a concept of Turing computability. From strictly mathematical perspective (not computer science one), such arguments could be of interests only if you are a follower of the ultrafinitism – a rather atypical school in the philosophy of mathematics. $\endgroup$
    – Waldemar
    Commented Jun 12, 2013 at 14:17
6
$\begingroup$

It's easy to prove that either White has a winning strategy, Black has a winning strategy, or each player can force a draw. It's not terribly hard to put an upper bound on the number of moves in a winning strategy (roughly the number of positions in the game --- the argument being that if a winning strategy required more moves than there are positions, then some position would be reached twice, meaning that the winning player could have taken a short cut and skipped the intervening moves). So it is a finite (and hence decidable) problem to determine which of the three possibilities holds.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ ari: but it's pretty easy to put an upper bound on the number of positions, and even easier to show an upper bound exists. $\endgroup$
    – Steven Landsburg
    Commented Jun 13, 2013 at 12:28

Not the answer you're looking for? Browse other questions tagged .