4 ms·
You can change "might not" to "have not". The Game of Life is Turing complete. And therefore a complete analysis of how to write programs in it would imply a s
by btilly 10mo ago
You can change "might not" to "have not".
The Game of Life is Turing complete. And therefore a complete analysis of how to write programs in it would imply a solution to the Halting problem. Which is impossible.
- londons_explore 10mo agoTuring completeness relies on infinite state. With finite state, one could theoretically brute force search every possible 1D sequence to find a glider shorter than the one discovered here. Obviously that's impractical, but turns the whole thing into a search problem - find the best/a good solution in a huge search space.