4 ms·

There is a trivial disproof of your claim. Two players write a turing machine with at most n states with two symbols. The player that produced a terminating tu

There is a trivial disproof of your claim. Two players write a turing machine with at most n states with two symbols. The player that produced a terminating turing machine that produces the most 1 symbols on the tape before terminating wins. The optimal strategy for this game is producing a busy beaver, a feat shown not to be computable.

andorov 10y ago
But no one could play because you can't create a Turing machine that provably halts, no?
- SAI_Peregrinus 10y ago
  You can prove that any given Turing machine halts or does not halt, but there's no single algorithm that can prove that for every Turing machine. The trivial case of a Turing machine that can be proven to halt is one with only one state: halted.
  - dsp1234 10y ago
    The trivial disproof still doesn't disprove anything about go and/or chess. Both chess and go have rules preventing repetition of moves (three fold repetition, and rule 8, respectively), and have a limited pool of possible future states. Therefore, there is no game of go or chess that does not halt. Thus, "Games like go and chess are necessarily solvable by definition, right?"
  - andorov 10y ago
    Yes but this case requires Turing machines that produce very very large (BB large) outputs and then halt. Is that provable for a specific machine?
    - mafuy 10y ago
      Any specific machine can be proved to terminate or not terminate - albeit not always in ZFC. For instance, BB(10) can be computed, just as BB(10000) can, just that the latter cannot be computed in ZFC.
gohrt 10y ago
Any rule structured game with fixed finite bounds is solvable.
drdeca 10y ago
this comment im making mainly me thinking out loud. It is not insightful: I was thinking that for a fixed n that doesn't really work, because there are only finitely many options, but I guess if n>~2000 , ZFC cannot show the winning strategy to be the winning strategy? Is that what you meant? Given any two machines which halt, finding the one that ends with more ones is computable. Assuming at least one of the two machines halts, which one wins can be computed in the limit? By which I mean, if the process is allowed to have a "who is currently winning" (the one that already halted if only one has, the one that halted later if both have, or neither if both haven't) thing, and the limit of that is whatever it eventually never switches from. I guess that works even if neither halt. Uh... I'm just saying stuff you already know to try to think through it myself. Edit: I guess the question is then, what exactly do we mean by solvable? Do we mean that there is an algorithm that outputs an optimal move on every turn? For any n, there is such an algorithm. The one that has the correct move hard-coded. Maybe we mean that there is an algorithm that probably always outputs an optimal move? In this case, well, I suppose it depends on the axiom system. Hm.

andorov 10y ago

But no one could play because you can't create a Turing machine that provably halts, no?

SAI_Peregrinus 10y ago
You can prove that any given Turing machine halts or does not halt, but there's no single algorithm that can prove that for every Turing machine. The trivial case of a Turing machine that can be proven to halt is one with only one state: halted.
- dsp1234 10y ago
  The trivial disproof still doesn't disprove anything about go and/or chess. Both chess and go have rules preventing repetition of moves (three fold repetition, and rule 8, respectively), and have a limited pool of possible future states. Therefore, there is no game of go or chess that does not halt. Thus, "Games like go and chess are necessarily solvable by definition, right?"
- andorov 10y ago
  Yes but this case requires Turing machines that produce very very large (BB large) outputs and then halt. Is that provable for a specific machine?
  - mafuy 10y ago
    Any specific machine can be proved to terminate or not terminate - albeit not always in ZFC. For instance, BB(10) can be computed, just as BB(10000) can, just that the latter cannot be computed in ZFC.

gohrt 10y ago

Any rule structured game with fixed finite bounds is solvable.

drdeca 10y ago

this comment im making mainly me thinking out loud. It is not insightful: I was thinking that for a fixed n that doesn't really work, because there are only finitely many options, but I guess if n>~2000 , ZFC cannot show the winning strategy to be the winning strategy? Is that what you meant? Given any two machines which halt, finding the one that ends with more ones is computable. Assuming at least one of the two machines halts, which one wins can be computed in the limit? By which I mean, if the process is allowed to have a "who is currently winning" (the one that already halted if only one has, the one that halted later if both have, or neither if both haven't) thing, and the limit of that is whatever it eventually never switches from. I guess that works even if neither halt. Uh... I'm just saying stuff you already know to try to think through it myself. Edit: I guess the question is then, what exactly do we mean by solvable? Do we mean that there is an algorithm that outputs an optimal move on every turn? For any n, there is such an algorithm. The one that has the correct move hard-coded. Maybe we mean that there is an algorithm that probably always outputs an optimal move? In this case, well, I suppose it depends on the axiom system. Hm.