Imagine if the whole of the world was a giant, spherical game of life board. The memory isn’t infinite, but it continues to advance by the rules as long as the sun burns.
Yeah, that makes sense to me.
Why is infinite tape required for undecidability to be an issue?
Because otherwise I can list all the states and transitions. Take your game of life board: We don’t get an issue like a halting problem: if you have a finite game of life, with n cells then there exist 2^n possible states, since the game is deterministic, it must repeat after at least 2^n steps in exactly the same sequence of states (halting in this universe might be interpreted as the same step repeating over and over, which is rather rare in the game of life I believe). Now we compute this sequence from within an even bigger game of life. The “real” problem is that the number of possible states is growing exponentially and there is no even bigger version of our universe to turn to, which is why we can’t even solve chess. As TAG highlighted in his comment, in some sense chess (at least currently) is undecidable for us (just not in the very rigorous sense).
Yeah, that makes sense to me.
Because otherwise I can list all the states and transitions. Take your game of life board: We don’t get an issue like a halting problem: if you have a finite game of life, with n cells then there exist 2^n possible states, since the game is deterministic, it must repeat after at least 2^n steps in exactly the same sequence of states (halting in this universe might be interpreted as the same step repeating over and over, which is rather rare in the game of life I believe). Now we compute this sequence from within an even bigger game of life. The “real” problem is that the number of possible states is growing exponentially and there is no even bigger version of our universe to turn to, which is why we can’t even solve chess. As TAG highlighted in his comment, in some sense chess (at least currently) is undecidable for us (just not in the very rigorous sense).