Hacker News Reader

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.

View on HN

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?"

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?

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.

Reply on news.ycombinator.com