3 ms·
But no one could play because you can't create a Turing machine that provably halts, no?
by andorov 10y ago
But no one could play because you can't create a Turing machine that provably halts, no?
- SAI_Peregrinus 10y agoYou 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 agoThe 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 agoYes 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 agoAny 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.