Re:Any Game of Life pattern can be constructed from just 15 ...
by biggiemac42 on Tuesday July 02, 2024 @04:56PM
(#40860325)
The post (and my previous waterbear post) both talk about universal construction, it is equivalent to glider construction. There are patterns which have N generations of predecessor but not N+1, which are also non-constructible.
Re:Any Game of Life pattern can be constructed from just 15 ...
by dvgrn on Tuesday July 02, 2024 @10:10PM
(#40862179)
There are also patterns -- both stable patterns and oscillators -- that have an unbounded chain of predecessors, but still can't be glider constructed. That is, there are proven solutions to Conway's "Unique Father Problem" from over half a century ago:
https://conwaylife.com/wiki/Unique_father_problem
To put it another way, there are certain patterns that, if you see them in the Life grid, you know they've always been there from T=0 -- because they are provably their own only predecessor.
That seems to be naturally true, since they by definition cannot be constructed. Are there other patterns that cannot be constructed by a universal constructor, or are all such patterns non-constructible?