@Rogem There's no need to invent arbitrary restrictions with the goal of hindering people of hard-coding. Just don't say anything about hard-coding at all and let the default loopholes handle thee rest.
No I mean I understand what these things are in informal language. But this is a programming problem, we need an exact definition that applies in all cases.
(Except the width 1025 thing, that is legitimately ambiguous when even speaking informally.)
Also, one could imagine that there could be two spaceships A and B, such that the pattern is not affected when either one is individually removed, but is affected when they are simultaneously removed.
@AndersKaseorg - I don't think so. If we remove A and the evolution will not changed, then we can remove B and the evolution still won't change. Do you mind providing a hypothetical example?
The fact that the evolution of the pattern is unaffected by the removal of B does not imply that the evolution of the pattern minus A is unaffected by the removal of B.
Think about what you’re saying formally. We have some pattern A + B + C. If “A is a spaceship”, the evolution of B + C is the same as the evolution of A + B + C. If “B is a spaceship”, the evolution of A + C is the same as the evolution of A + B + C. We can make no deductions about the evolution of C itself.
if B + C = A + B + C, then A does not affect A + B + C; if A + C = A + B + C, then B does not affect A + B + C either. Hence neither A and B affect A + B + C.
Do you mind supplying a counterexample?
@BMQ I removed the 1024x1024 part due to the confusion.
Oh, so 8x8 grid is the input for a simulation on an infinite grid? Maybe that needs clarification, I understood it as the initial state of an 8x8 simulation :S
Imagine there’s an alive cell with 3 neighbors, one of which is part of A and one of which is part of B. If only A is removed, it has 2 neighbors and remains alive. If only B is removed, it has 2 neighbors and remains alive. But if both A and B are removed, it has 1 neighbor and dies.
Could this be extended from a local observation about one cell to an entire pattern? I don’t know! But that’s the whole point: “I don’t know” is not a good enough foundation for a formal definition.
Well the lowest cell isn’t directly affected by the removal of 1 glider but is affected by the removal of 2. It happens that in your example there are other cells that don’t have that property. But how do you know that in every case (not just this one) there will always be some other cell without that property?
If two gliders are connected by some chain of on cells, then the two gliders are dependent on each other's evolution in (the length of the chain)-generations, since evolution propagates at the speed of light. (Not exactly the most formal proof.)
The burden is on you to prove that your definition makes sense.
I honestly don’t know whether it does or doesn’t at this point.
If it does, it depends on a very nonobvious claim that needs to be proved, not just failed-to-be-disproved.
Even if it does, I can’t imagine how it could be checked efficiently by a program.
In fact, since one can build Turing machines in life, even the question “is this pattern a spaceship” is undecidable.
Given a Turing machine T, one can build a Life pattern that (1) simulates T until it halts, and if so (2) translates itself in some direction and restarts. Then it’s a spaceship iff T halts.
But then how is it possible to determine when a CGoL state halts? There are common long-lived patterns and search programs for them; how do they determine if they halt? I'm a little confused...
Discussion on question by Baaing Cow:…
Discussion on question by Baaing Cow:…