4 ms·
So my understanding is that the Game of Life is an undecidable system, so you basically can't write a solvable system of equations that will tell you that your
by lubesGordi 6y ago
So my understanding is that the Game of Life is an undecidable system, so you basically can't write a solvable system of equations that will tell you that your initial state will produce a Mona Lisa.
Even after reading the article I don't really understand what he's doing to make this happen. And especially after stating that most states are Garden of Eden states!
Can anyone ELI5?
- OscarCunningham 6y agoIt'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).