I really enjoyed this read, thanks. I’m an enjoyer of Life from afar so there may be a trivial answer to this question.
Is it possible to reverse engineer a state in Life? E.g., for time state X, can you easily determine a possible time state X-1? I know that multiple X-1 time states can lead to the same X time state, but is it possible to generate one? Can you reverse engineer any possible X-100 time state for a given time state X? I ask because I wonder if you could generate an X-(10^60) time state on a 10^30 by 10^30 grid where time state X is a large smiley face.
This almost certainly wouldn’t give you a 10^20 by 10^20 corner that generates a smiley face for all or even a small fraction of iterations of the rest of the grid. But perhaps you could randomise the reverse engineering and keep generating X-(10^60) states until you get one that creates a smiley face for the greatest number of 10^30 by 10^30 states (randomly generating that part of the grid and running it for 10^60 steps), then call that your solution to the control problem
I used the numbers from your example in mine, but perhaps one could demonstrate this with a much smaller grid. Say for example, a 10^2 by 10^2 grid with 10^5 time steps, and reverse engineer a smiley face.
This might be a way of brute forcing the control problem, so to speak. Proving it is possible in a smaller grid might show it’s possible with larger grids.
Is it possible to reverse engineer a state in Life? E.g., for time state X, can you easily determine a possible time state X-1?
Wouldn’t the existence of Garden of Eden states, which have no predecessor, prove that you cannot easily create a predecessor in general? You could then make any construction non-predecessable by embedding some Garden of Eden blocks somewhere in them.
That’s true, but would I be right in saying that as long as there are no Garden of Eden states, you could in theory at least generate one possible prior state?
There is some terminological confusion in this thread: a Garden of Eden of a Cellular Automaton is a configuration which has no predecessor. (A configuration is a function assigning a state to every cell). An orphan is a finite subset of cells with their states having the property that any configuration containing the orphan is a Garden Of Eden configuration. Obviously every orphan can be extended to a Garden of Eden configuration (by choosing a state arbitrarily for the cells not in the orphan) but interestingly it is also true that every garden of eden contains an orphan. So the answer to your question is yes: if there are no orphans in the configuration then it is not a garden of eden, therefore, by definition, it has a predecessor.
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.
I really enjoyed this read, thanks. I’m an enjoyer of Life from afar so there may be a trivial answer to this question.
Is it possible to reverse engineer a state in Life? E.g., for time state X, can you easily determine a possible time state X-1? I know that multiple X-1 time states can lead to the same X time state, but is it possible to generate one? Can you reverse engineer any possible X-100 time state for a given time state X? I ask because I wonder if you could generate an X-(10^60) time state on a 10^30 by 10^30 grid where time state X is a large smiley face.
This almost certainly wouldn’t give you a 10^20 by 10^20 corner that generates a smiley face for all or even a small fraction of iterations of the rest of the grid. But perhaps you could randomise the reverse engineering and keep generating X-(10^60) states until you get one that creates a smiley face for the greatest number of 10^30 by 10^30 states (randomly generating that part of the grid and running it for 10^60 steps), then call that your solution to the control problem
I used the numbers from your example in mine, but perhaps one could demonstrate this with a much smaller grid. Say for example, a 10^2 by 10^2 grid with 10^5 time steps, and reverse engineer a smiley face.
This might be a way of brute forcing the control problem, so to speak. Proving it is possible in a smaller grid might show it’s possible with larger grids.
Wouldn’t the existence of Garden of Eden states, which have no predecessor, prove that you cannot easily create a predecessor in general? You could then make any construction non-predecessable by embedding some Garden of Eden blocks somewhere in them.
That’s true, but would I be right in saying that as long as there are no Garden of Eden states, you could in theory at least generate one possible prior state?
There is some terminological confusion in this thread: a Garden of Eden of a Cellular Automaton is a configuration which has no predecessor. (A configuration is a function assigning a state to every cell). An orphan is a finite subset of cells with their states having the property that any configuration containing the orphan is a Garden Of Eden configuration. Obviously every orphan can be extended to a Garden of Eden configuration (by choosing a state arbitrarily for the cells not in the orphan) but interestingly it is also true that every garden of eden contains an orphan. So the answer to your question is yes: if there are no orphans in the configuration then it is not a garden of eden, therefore, by definition, it has a predecessor.
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.