4 ms·
It's a decidable problem to evolve the Game of Life fowrard a fixed number of generations. The undecidable thing is to determine the eventual fate of a pattern,
by OscarCunningham 6y ago
It's a decidable problem to evolve the Game of Life fowrard a fixed number of generations. The undecidable thing is to determine the eventual fate of a pattern, e.g. 'does it ever die out completely?'. Even then you can answer this question for large classes of patterns, just not all of them.
- aflag 6y agoMoreover, it is just like any other code you write. It's undecidable whether a function you write will ever stop in the general case, but I'm pretty sure you are able to easily prove most of your functions are going to finish.
- lubesGordi 6y agoOkay well you can 'simulate' the GoL forward and see what it's going to be in a few fixed number of generations. That's basically how you do anything with these undecidable systems. I'm not clear on how he got some state that looks like a Mona Lisa when most or almost all states that look like a Mona Lisa are Garden of Eden states, and then from there worked backwards (I'm not clear on if/how you can go backwards in GoL).