In Life, I don’t think it’s easy to generate an X-1 time state that leads to an X time state, unfortunately. The reason is that each cell in an X time state puts a logical constraint on 9 cells in an X-1 time state. It is therefore possible to set up certain constraint satisfaction problems in terms of finding an X-1 time state that leads to an X time state, and in general these can be NP-hard.
However, in practice, it is very very often quite easy to find an X-1 time state that leads to a given X time state, so maybe this experiment could be tried in an experimental form anyhow.
In our own universe, the corresponding operation would be to consider some goal configuration of the whole universe, and propagate that configuration backwards to our current time. However, this would generally just tell us that we should completely reconfigure the whole universe right now, and that is generally not within our power, since we can only act locally, have access only to certain technologies, and such.
I think it is interesting to push on this “brute forcing” approach to steering the future, though. I’d be interested to chat more about it.
It surprises me a little that there hasn’t been more work on working backwards in Life. Perhaps it’s just too hard/not useful given the number of possible X-1 time slices.
With the smiley face example, there could be a very large number of combinations for the squares outside the smiley face at X-1 which result in the same empty grid space (i.e. many possible self-destructing patterns).
I’m unreasonably fond of brute forcing problems like these. I don’t know if I’d have anything useful to say on this topic that I haven’t already, but I’m interested to follow this work. I think this is a fascinating analogy for the control problem.
Edit—It just occurred to me, thanks to a friend, that instead of reverse engineering the desired state, it might be easier to just randomise the inputs until you get the outcome you want (not sure why this didn’t occur to me). Still very intensive, but perhaps easier.
Well, there are programs like Logic Life Search that can solve reasonably small instances of backwards search. This problem is quite hard in general. Part of the reason is that you have to consider sparks in the search. The pattern in question could have evolved from small predecessor pattern, but the reaction could have moved from the starting point and a several dying sparks could have been emitted all around. So you have to somehow figure the exact location, timing and nature of these sparks to successfully evolve the pattern backwards. Otherwise, it quite quickly devolves into bigger and bigger blob of seemingly random dust.
In practice, backwards search is regularly applied to find smaller predecessors in terms of bounding box and/or population. See, for example, Max page. And the number of ticks backwards is quite small, we are talking about a single-digit number here.
Thanks for the note.
In Life, I don’t think it’s easy to generate an X-1 time state that leads to an X time state, unfortunately. The reason is that each cell in an X time state puts a logical constraint on 9 cells in an X-1 time state. It is therefore possible to set up certain constraint satisfaction problems in terms of finding an X-1 time state that leads to an X time state, and in general these can be NP-hard.
However, in practice, it is very very often quite easy to find an X-1 time state that leads to a given X time state, so maybe this experiment could be tried in an experimental form anyhow.
In our own universe, the corresponding operation would be to consider some goal configuration of the whole universe, and propagate that configuration backwards to our current time. However, this would generally just tell us that we should completely reconfigure the whole universe right now, and that is generally not within our power, since we can only act locally, have access only to certain technologies, and such.
I think it is interesting to push on this “brute forcing” approach to steering the future, though. I’d be interested to chat more about it.
It surprises me a little that there hasn’t been more work on working backwards in Life. Perhaps it’s just too hard/not useful given the number of possible X-1 time slices.
With the smiley face example, there could be a very large number of combinations for the squares outside the smiley face at X-1 which result in the same empty grid space (i.e. many possible self-destructing patterns).
I’m unreasonably fond of brute forcing problems like these. I don’t know if I’d have anything useful to say on this topic that I haven’t already, but I’m interested to follow this work. I think this is a fascinating analogy for the control problem.
Edit—It just occurred to me, thanks to a friend, that instead of reverse engineering the desired state, it might be easier to just randomise the inputs until you get the outcome you want (not sure why this didn’t occur to me). Still very intensive, but perhaps easier.
Well, there are programs like Logic Life Search that can solve reasonably small instances of backwards search. This problem is quite hard in general. Part of the reason is that you have to consider sparks in the search. The pattern in question could have evolved from small predecessor pattern, but the reaction could have moved from the starting point and a several dying sparks could have been emitted all around. So you have to somehow figure the exact location, timing and nature of these sparks to successfully evolve the pattern backwards. Otherwise, it quite quickly devolves into bigger and bigger blob of seemingly random dust. In practice, backwards search is regularly applied to find smaller predecessors in terms of bounding box and/or population. See, for example, Max page. And the number of ticks backwards is quite small, we are talking about a single-digit number here.