Unproven conjectures

[kuluma]

Of course calcyman is correct, in my previous message I meant that the previous proof does not work at all because of stabilization. The observation of calcyman is that, for the same reason, another (even intuitively simpler) proof gives even smaller higher orphans, though unlike in the previous proof you don't get a handle on the order.

[kuluma]

In a similar vein, it is PSPACE-hard whether a given pattern appears in the limit set, just run a Turing machine inside the hole to determine whether it blows up.

[Sokwe]

New results (by me and Ville Salo). There exists a finite pattern that forces itself to occur entirely in each of its preimages. It's this one (surrounded by gray cells):

Awesome! I'm not sure if anyone has done this already, but I confirmed the result with JLS (took a few hours, I think). Has anyone been able to make the conjecture precise for a "complete" still life, and not just a still life-compatible patch?

[Ilkka Törmä]

I'm not sure if anyone has done this already, but I confirmed the result with JLS (took a few hours, I think).

It's great to have an independent confirmation! Also, this showcases the power of modern SAT solvers: with our encoding, Glucose 4.1 verifies the result in less than 2 minutes on my old-ish laptop, running on a single core.

Has anyone been able to make the conjecture precise for a "complete" still life, and not just a still life-compatible patch?

This is one of the issues I have with the unique father conjecture: it's not precisely stated. Does it ask for an actual still life whose fathers must contain that entire still life, or is a still life-compatible patch enough? What does "some fading junk some distance away not being counted" mean? Hence I'm not 100% sure if our pattern qualifies as a solution.

One interpretation would be that we're looking for a finite pattern P, meaning an assignment of cell states on some finite set of cells, such that:

1. All of its predecessors contain P at the same position. By "predecessor" I mean another finite pattern that specifies exactly the contents of the neighborhood of every cell in P.
2. If all cells outside P are assigned dead, the result is a still life.

Our pattern satisfies 1. but not 2.

[Macbi]

This is one of the issues I have with the unique father conjecture: it's not precisely stated. Does it ask for an actual still life whose fathers must contain that entire still life, or is a still life-compatible patch enough? What does "some fading junk some distance away not being counted" mean? Hence I'm not 100% sure if our pattern qualifies as a solution.

Here dvgrn and I agreed that a good formal restatement of the unique father problem would be whether there exists an arrangement of alive and dead cells which could be extended to a still life and such that the parent of any pattern containing that arrangement also contained that arrangement (in the same position). Your solution definitely satisfies that.

[dani]

The pattern can easily be completed into a still life. Since the pattern inside it can't be created by anything else than itself, it's not glider-constructible (meaning that it doesn't have a glider synthesis). More strongly, this still life can't be constructed on empty space by any gadget whatsoever, so Life doesn't support a universal constructor for all still lifes.

Code: Select all

RLE

Groundbreaking result. Would this still life also satisfy the same conditions? (has all the green cells, 40 cells smaller):

Code: Select all

x = 32, y = 26, rule = B3/S23
8b2obo2b2obo2b2obo$8bob2o2bob2o2bob2o3b2o$6b2o4b2o4b2o4b2o2bo$b2obo2bo
b2o2bob2o2bob2o2bobo$bob2obo2b2obo2b2obo2b2obo2b2o$6b2o4b2o4b2o4b2o$2b
2obo2b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o2bob2o$2o4b2o4b2o
4b2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2ob
o2b2obo$2o4b2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo2b2obo$2bob2o2b
ob2o2bob2o2bob2o2bob2o$2o4b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o
2bob2o2bo$o2b2obo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o4b2o$2b2ob
o2b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o2bob2o$6b2o4b2o4b2o
4b2o$3b2o2bob2o2bob2o2bob2o2bob2obo$4bobo2b2obo2b2obo2b2obo2bob2o$3bo
2b2o4b2o4b2o4b2o$3b2o3b2obo2b2obo2b2obo$8bob2o2bob2o2bob2o!

[Macbi]

The pattern can easily be completed into a still life. Since the pattern inside it can't be created by anything else than itself, it's not glider-constructible (meaning that it doesn't have a glider synthesis). More strongly, this still life can't be constructed on empty space by any gadget whatsoever, so Life doesn't support a universal constructor for all still lifes.

Code: Select all

RLE

Groundbreaking result. Would this still life also satisfy the same conditions? (has all the green cells, 40 cells smaller):

Code: Select all

x = 32, y = 26, rule = B3/S23
8b2obo2b2obo2b2obo$8bob2o2bob2o2bob2o3b2o$6b2o4b2o4b2o4b2o2bo$b2obo2bo
b2o2bob2o2bob2o2bobo$bob2obo2b2obo2b2obo2b2obo2b2o$6b2o4b2o4b2o4b2o$2b
2obo2b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o2bob2o$2o4b2o4b2o
4b2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o2bob2o2bo$o2b2obo2b2obo2b2obo2b2ob
o2b2obo$2o4b2o4b2o4b2o4b2o4b2o$2b2obo2b2obo2b2obo2b2obo2b2obo$2bob2o2b
ob2o2bob2o2bob2o2bob2o$2o4b2o4b2o4b2o4b2o4b2o$bob2o2bob2o2bob2o2bob2o
2bob2o2bo$o2b2obo2b2obo2b2obo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o4b2o$2b2ob
o2b2obo2b2obo2b2obo2b2obo$2bob2o2bob2o2bob2o2bob2o2bob2o$6b2o4b2o4b2o
4b2o$3b2o2bob2o2bob2o2bob2o2bob2obo$4bobo2b2obo2b2obo2b2obo2bob2o$3bo
2b2o4b2o4b2o4b2o$3b2o3b2obo2b2obo2b2obo$8bob2o2bob2o2bob2o!

The smallest you can get it is population 306. (Confirmed with LLS.)

Code: Select all

x = 34, y = 28, rule = LifeHistory
12.2C4.2C$12.C5.C$7.2C5.C5.C7.2C$6.C.A4D2A4D2A4D2AD.C$2.2C.A2DAD2A2DA
D2A2DAD2A2DADA$2.C.2ADA2D2ADA2D2ADA2D2ADA2D2A$3.4D2A4D2A4D2A4D2A3DC$
3.2ADA2D2ADA2D2ADA2D2ADA2D2AD.C$3.AD2A2DAD2A2DAD2A2DAD2A2DAD2AC$3.4D
2A4D2A4D2A4D2A4D$3.D2A2DAD2A2DAD2A2DAD2A2DAD2AD$3.D2ADA2D2ADA2D2ADA2D
2ADA2D2AD$3.4D2A4D2A4D2A4D2A4D.2C$2.C2ADA2D2ADA2D2ADA2D2ADA2D2ADA2.C$
C2.AD2A2DAD2A2DAD2A2DAD2A2DAD2AC$2C.4D2A4D2A4D2A4D2A4D$3.D2A2DAD2A2DA
D2A2DAD2A2DAD2AD$3.D2ADA2D2ADA2D2ADA2D2ADA2D2AD$3.4D2A4D2A4D2A4D2A4D$
2.C2ADA2D2ADA2D2ADA2D2ADA2D2ADA$2.C.D2A2DAD2A2DAD2A2DAD2A2DAD2A$3.C3D
2A4D2A4D2A4D2A4D$4.2A2DAD2A2DAD2A2DAD2A2DAD2A.C$5.ADA2D2ADA2D2ADA2D2A
DA2DA.2C$4.C.D2A4D2A4D2A4DA.C$4.2C7.C5.C5.2C$15.C5.C$14.2C4.2C!

[hkoenig]

The large agar can't be constructed by Gliders. Here are some small stable objects based on patches from the agar.

Code: Select all

#C w:28_ck3qp3ckz11642611 (28.128059223)
#C w:50_ck3qp3ckzp96ki6p9z23c95c23
#C w:88_ck3qp3ck3qp3ckzp96ki6p96ki6p9z23c95c23c95c23
x=44, y=14
2b2obo8b2obo2b2obo8b2obo2b2obo$2bob2o8bob2o2bob2o8bob2o2bob2o$2o4b2o4b2o4b
2o4b2o4b2o4b2o4b2o$bob2o2bo5bob2o2bob2o2bo5bob2o2bob2o2bo$o2b2obo5bo2b2ob
o2b2obo5bo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o$2b2obo8b2obo2b2obo8b
2obo2b2obo$2bob2o8bob2o2bob2o8bob2o2bob2o$30b2o4b2o4b2o$31bob2o2bob2o2bo$30b
o2b2obo2b2obo$30b2o4b2o4b2o$32b2obo2b2obo$32bob2o2bob2o!

The smallest can be constructed.

Code: Select all

x=52, y=52
13bo$11bobo$12b2o$30bo$30bobo$30b2o$26bo$26bobo$26b2o3$50bo$31bo17bo$30bo18b3o$30b3o2$32bo$31b2o$18bo12bobo$4bo9bob2o$5bo6bobo2b2o$3b3o7b2o2$7bo$8bo$6b3o$43b3o$43bo$44bo2$37b2o7b3o$33b2o2bobo6bo$34b2obo9bo$18bobo12bo$19b2o$19bo2$19b3o$3o18bo$2bo17bo$bo3$24b2o$23bobo$25bo$20b2o$19bobo$21bo$38b2o$38bobo$38bo!

Can the second one be constructed? The third? At what point does it become impossible to construct such a patch? An exercise for the student is to find the smallest object that can't be constructed. (And why it's impossible...)

[kuluma]

Though it was not discussed in this thread, we (me & Ilkka Törmä) learned on Discord that people are also interested in whether there exists a finite configuration which admits a Game of Life -preimage, but does not admit a finite one. The answer is "yes", we proved this quite soon after our previous Game of Life paper. To see the pattern, called the American Dream, evolve this configuration one step and discard the topmost row.

Code: Select all

x = 38, y = 71, rule = Life
bbbbbbbbAbAbAbAbbbAbbbAbbbbbAAbbbbbbbb$bbbbbbbbAbbbAbbbAbbbAbAbAbAbAAbbbbbbbb$bbbbbbbbbbAbbbAbAbAbAbbbAbAbAbbbbbbbbb$bbbbbbbbAbAbAbAbbbAbbbAbbbbbAAbbbbbbbb$bbbbbbbbAbbbAbbbAbbbAbAbAbAbAAbbbbbbbb$bbbbbbbbbbAbbbAbAbAbAbbbAbAbAbbbbbbbbb$bbbbbbbbAbAbAbAbbbAbbbAbbbbbAAbbbbbbbb$bbbbbbbbAbbbAbbbAbbbAbAbAbAbAAbbbbbbbb$bbbbbbbbbbAbbbAbAbAbAbbbAbAbAbbbbbbbbb$bbbbbbbbAbAbAbAbbbAbbbAbbbbbAAbbbbbbbb$bbbbbbbbAbbbAbbbAbbbAbAbAbAbAAbbbbbbbb$bbbbbbbbbbAbbbAbAbAbAbbbAbAbAbbbbbbbbb$bbbbbbbbAbAbAbAbbbAbbbAbbbbbAAbbbbbbbb$bbbbbbbbAbbbAbbbAbbbAbAbAbAbAAbbbbbbbb$bbbbbbbbbbAbbbAbAbAbAbbbAbAbAbbbbbbbbb$bbbbbbbbAbAbAbAbbbAbbbAbbbbbAAbbbbbbbb$bbbbbbbbAbbbAbbbAbbbAbAbAbAbAAbbbbbbbb$bbbbbbbbbbAbbbAbAbAbAbbbAbAbAbbbbbbbbb$bbbbbbbbAbAbAbAbbbAbbbAbbbbbAAbbbbbbbb$bbbbbbbbAbbbAbbbAbbbAbAbAbAbAAbbbbbbbb$bbbbbbbbbbAbbbAbAbAbAbbbAbAbAbbbbbbbbb$bbbbbbbbAbAbAbAbbbAbbbAbbbbbAAbbbbbbbb$bbbbbbbbAbbbAbbbAbbbAbAbAbAbAAbbbbbbbb$bbbbbbbbbbAbbbAbAbAbAbbbAbAbAbbbbbbbbb$bbbbbbbbAbAbAbAbbbAbbbAbbbbbAAbbbbbbbb$bbbbbbbbAbbbAbbbAbbbAbAbAbAbAAbbbbbbbb$bbbbbbbbbbAbbbAbAbAbAbbbAbAbAbbbbbbbbb$bbbbbbbbAbAbAbAbbbAbbbAbbbbbAAbbbbbbbb$bbbbbbbbAbbbAbbbAbbbAbAbAbAbAAbbbbbbbb$bbbbbbbbbbAbbbAbAbAbAbbbAbAbAbbbbbbbbb$bbbbbbbbAbAbAbAbbbAbbbAbbbbbAAbbbbbbbb$bbbbbbbbAbbbAbbbAbbbAbAbAbAbAAbbbbbbbb$bbbbbbbbbbAbbbAbAbAbAbbbAbAbAbbbbbbbbb$bbbbbbbbAbAbAbAbbbAbbbAbbbbbAAbbbbbbbb$bbbbbbbbAbbbAbbbAbbbAbAbAbAbAAbbbbbbbb$bbbbbbbbbbAbbbAbAbAbAbbbAbAbAbbbbbbbbb$bbbbbbbbAbAbAbAbbbAbbbAbbbbbAAbbbbbbbb$bbbbbbbbAbbbAbbbAbbbAbAbAbAbAAbbbbbbbb$bbbbbbbbbbAbbbAbAbAbAbbbAbAbAbbbbbbbbb$bbbbbbbbAbAbAbAbbbAbbbAbbbbbAAbbbbbbbb$bbbbbbbbAbbbAbbbAbbbAbAbAbAbAAbbbbbbbb$bbbbAbbbbbAbbbAbAbAbAbbbAbAbAbbbbbbbbb$bbbbbbbbAbAbAbAbbbAbbbAbbbbbAAbbbbbbbb$bbbbbAbbAbbbAbbbAbbbAbAbAbAbAAbbbAbbbb$bbbbbbbbbbAbbbAbAbAbAbbbAbAbAbbbAbbbbb$bbbbbbbbAbAbAbAbbbAbbbAbbbbbAAAAAAbbbb$bbbbbbbbAbbbAbbbAbbbAbAbAbAbAAAbAAbbbb$bbbbbbbbbbAbbbAbAbAbAbbbAbAbbAAAAbbbbb$bbbbbbbbAbAbAbAbbbAbbbAbbbbbAAbbbAbbbb$bbbbbbbbAbbbAbbbAbbbAbAbAbAbAAbAbbbbbb$bbbbbbbbbbAbbbAbAbAbAbbbAbAbbAbAbAbbbb$bbbbbbbbAbAbAbAbbbAbbbAbbbbbAbAAAbbbbb$bbbbbbbbAbbbAbbbAbbbAbAbAbAAAAAbAAbbbb$bbbbbbbbbbAbbbAbAbAbAbbbAbbbAbAAAAbbbb$bbbbbbbAAbbAbAbbbbbbbbbbbAbbbbAAAbbbbb$bbbbbbAbbbAbbbbAAbAAbAAAbAbbAbbAAbbbbb$bbbbbbbbAbbbbAAbbbAAbAAbbbbAAAbAAAbbbb$bbbbbbbAbAAAbbbbAbbbAbbbbbAbAbbbAAbbbb$bbbbbbbbbbAbbAbbAbbbbbbAAAbbbbbbAbbbbb$bbbbbbAbAbbbAbAAbAAAAbbbAbAbAbAbAAbbbb$bbbbbbbbAbbAAbAbAbbbAAbbbbbbAbAbAAbbbb$bbbbbbbbAAbAbAbbAbbbbAbAAAbAAAAAAbbbbb$bbbbbbbAAAbbAbbbbAbAAbbAbbbbbAbAbAbbbb$bbbbAbAbAAbAAbAAbAAbbbAbbAbbbAbAbbbbbb$bbbbbbbbbAAAAAAAAbbbbbbbbbbbbbbbbAbbbb$bbbbAbAbAbAAbbAAbAbAbbbbbbbAbbbbbbbbbb$bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb$bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb$bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb$bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb$bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb$

The two rows of garbage are expected, since otherwise we would have a finite-support preimage configuration, which I'm claiming does not exist. To get an infinite support preimage configuration, just extend the top three rows upward periodically. Note that there are many preimages for this configuration, this one was produced by the PicoSAT solver with the constraint that the bottom, left and right borders should be zero. We did not clean up any obvious "garbage". What matters is the beam you see on top: we prove that every preimage has such an infinite beam.

The proof has two parts. The first one is human-checkable, let's start with that: Consider the pattern

Code: Select all

0101010100010001000
0100010001000101010

which you can see on the left side of the topmost two rows, in the shown preimage of the American Dream. There are a few extra 1s but you can just ignore those. This pattern contains the subpattern

Code: Select all

0101010
0100010

This pattern has the following property: if you want to extend this upwards by one row of the same length so that the middle part maps to zeroes in the Game of Life local rule, then the only possible extension is actually 0001000. To see this, we perform a simple case analysis: suppose the extension is

Code: Select all

abcdefg
0101010
0100010

Since the leftmost 1 on the top row must map to 0, we must have a+b+c = 0 or a+b+c = 3. If a+b+c = 3, then we have the situation

Code: Select all

111defg
0101010
0100010

and now the central 1, which should map to 0 as well, forces d = e = 0:

Code: Select all

11100fg
0101010
0100010

Now the rightmost 1 on the top row forces f = g = 0, and if you look carefully you see that we have introduced a 1 in the image! This forces a = b = c = 0, and symmetrically we must have e = f = g = 0. If we also put d = 0, then we introduce a 1 in the image, so in fact d = 1.

We conclude that the extension looks like this:

Code: Select all

0001000************
0101010100010001000
0100010001000101010

Now you can check that if we are to map everything here to 0, then we can deterministically deduce the bits from left to right, e.g. the leftmost * must be a 1 because there is a 0 seeing exactly three neighbors now, so we must add a fourth, and so forth.

Code: Select all

0001000101010100010
0101010100010001000
0100010001000101010

This turns out to be the natural three-periodic extension of the last pattern where each column of 0s continues with 0s, and columns with 1s have exactly two 1s in every contiguous segment of length three. We see that the same subpattern

Code: Select all

0101010
0100010

appears in this resulting pair of rows, so we can fill the cells above it, and then fill the remaining cells by simple deterministic rules (this extend both left and right). This forces the next row to again be the 3-periodic continuation

Code: Select all

0100010001000101010
0001000101010100010
0101010100010001000

We now see the pattern on the right, so the argument applies again. That gets us where we started, so the same logic actually forces an infinite 3-periodic column of 1s.

This idea appeared already in our previous paper https://arxiv.org/abs/1912.00692. The proof was discovered using automata theory: The set Lₖ of (finite subwords of) bi-infinite words, which can be extended upwards by k steps so that GoL maps the entire strip to 0, is a regular language for any fixed k. You can easily write a nondeterministic finite-state automaton for it, and for small k you can determinize and minimize it with ease.

Similarly, for any fixed m the set Lᵐ of (finite subwords of) bi-infinite words, which can be extended upwards by m steps so that GoL maps the entire strip to 0 and the top two rows contain only zeroes, is also regular language. We experimented with this and observed that L₃ contains words which do not seem to be in Lᵐ for any m, meaning that they force non-zero continuations upwards. We simply minimized this automaton, took the smallest word in the difference, and worked out a proof on the blackboard.

Of course, the question is why this particular pattern appears on the top row in preimages of the American Dream. We have no human proof for this, we checked it by a SAT solver. We have not spent much effort trying to figure out how this works, not because we are not interested, but because we have many much simpler patterns (with only a few cells) whose forcing properties baffle us despite a lot of work. Thus, you simply have to trust that we encoded this correctly to a SAT solver, and that it gave a correct proof. (SAT solvers can produce proof certificates which are easy to check, but the encoding we use is a much more likely source of bugs, so that does not help.) We have checked this pattern several times, you can check it independently if you like. (Actually the present pattern was minimized a bit for this post, and the result has not been checked as carefully as the original, but hopefully no mistake was introduced.)

One may also wonder how this was found. I will not explain the search strategy in detail, since I am not even sure what the precise algorithm was when this was found (it was a long time ago, and the search program has evolved). We are planning to publish our search programs at some point, for now I'll outline the high level idea of the search program that found this one.

So, we want to find a pattern whose preimages all have a particular pattern in some fixed position, let's say a subpattern P should appear in the finite domain D ⊆ ℤ². We can think of the SAT solver as an oracle that quickly (not super quickly, but definitely in less than a second) gives us a preimage for a given pattern Q, or tells us that one does not exist. It is easy to make it enumerate all possible restrictions of preimages in a particular area, or to have it find preimages under some additional restrictions. The first idea is to start with a trivial pattern as Q, compute all the possible things you can see in the domain D in the preimages, and then start extending the pattern Q (by increasing its domain cell by cell and picking a bit value there) so that the number of restrictions of preimages to D decreases at a maximal rate, of course under the condition that you never drop the pattern P you want to have in the end.

Here we run into our first and very obvious problem: For the pattern we are forcing, the domain D is quite large with 38 elements, so initially we expect to have about 2³⁸ preimage restrictions. That's a lot of calls to a SAT solver! So we split D into smaller (possibly overlapping) pieces D = ∪ᵢ Dᵢ, and we only keep track of what you can see in the restrictions of preimages to the individual sets Dᵢ. Once each Dᵢ can only contain the restriction P|Dᵢ in each preimage of Q, we are of course done. You could even just just take Dᵢ = {vᵢ}$ where vᵢ are an enumeration of D, but then we have less information about the precise things that have been forced so far. We used some reasonable-seeming compromise, without any particular theoretical basis.

The next problem is perhaps more subtle. If we are always extending the existing pattern, we may run into a problem that will never go away. Namely, we can run into a diamond: Suppose there are two preimages for our present pattern Q, say R₁ and R₂, and suppose that R₁ happens to be the only preimage that actually gives the correct pattern in one of the domain pieces Dᵢ. Then we must clearly never erase the preimage R₁, i.e. every extension we make to Q must allow a corresponding extension to R₁. Now, the issue that R₂ might have a wrong restriction R₂|Dⱼ in one of the domain pieces Dⱼ, yet have the exact same contents as R₁ on the boundary of the present domain of Q. So if you now extend Q, then because you cannot erase the unique preimage R₁ with R₁|Dᵢ = P|Dᵢ, you clearly cannot erase the preimage R₂ either (since the boundary values are the same), and this means we will never get rid of (extensions of) R₂. Luckily, it turns out that diamonds can be found by the SAT solver just easily as preimages, we literally ask one to give us a pair of preimages that share the same values on the border, but differ in a relevant area. They have no problem figuring out whether that can be done at this pattern size. When we encounter diamonds, we simply backtrack. There are a few additional tricks, sometimes the configuration is modified randomly if it seems extensions do not help. And finally we ran an independent evolutionary search to extract the core pattern.

Using these ideas, the pattern is produced in a few hours of computation (on a laptop).

[erictom333]

The large agar can't be constructed by Gliders. Here are some small stable objects based on patches from the agar.

Code: Select all

#C w:28_ck3qp3ckz11642611 (28.128059223)
#C w:50_ck3qp3ckzp96ki6p9z23c95c23
#C w:88_ck3qp3ck3qp3ckzp96ki6p96ki6p9z23c95c23c95c23
x=44, y=14
2b2obo8b2obo2b2obo8b2obo2b2obo$2bob2o8bob2o2bob2o8bob2o2bob2o$2o4b2o4b2o4b
2o4b2o4b2o4b2o4b2o$bob2o2bo5bob2o2bob2o2bo5bob2o2bob2o2bo$o2b2obo5bo2b2ob
o2b2obo5bo2b2obo2b2obo$2o4b2o4b2o4b2o4b2o4b2o4b2o4b2o$2b2obo8b2obo2b2obo8b
2obo2b2obo$2bob2o8bob2o2bob2o8bob2o2bob2o$30b2o4b2o4b2o$31bob2o2bob2o2bo$30b
o2b2obo2b2obo$30b2o4b2o4b2o$32b2obo2b2obo$32bob2o2bob2o!

The smallest can be constructed.

Code: Select all

x=52, y=52
13bo$11bobo$12b2o$30bo$30bobo$30b2o$26bo$26bobo$26b2o3$50bo$31bo17bo$30bo18b3o$30b3o2$32bo$31b2o$18bo12bobo$4bo9bob2o$5bo6bobo2b2o$3b3o7b2o2$7bo$8bo$6b3o$43b3o$43bo$44bo2$37b2o7b3o$33b2o2bobo6bo$34b2obo9bo$18bobo12bo$19b2o$19bo2$19b3o$3o18bo$2bo17bo$bo3$24b2o$23bobo$25bo$20b2o$19bobo$21bo$38b2o$38bobo$38bo!

Can the second one be constructed? The third? At what point does it become impossible to construct such a patch? An exercise for the student is to find the smallest object that can't be constructed. (And why it's impossible...)

Some thoughts on a stntheses of the second.

Code: Select all

x = 89, y = 28, rule = B3/S23
15bob2o8bob2o11bob2o12bob2o13bob2o$15b2obo8b2obo11b2obo12b2obo13b2obo$
13b2o4b2o4b2o4b2o7b2o4b2o8b2o4b2o9b2o4b2o$13bo2b2obo5bo2b2obo8bo2b2obo
3b2o4bo2b2obo2bob2o4bo2b2obo2bob2o$14bob2o2bo5bob2o2bo8bob2o2bo2b2o5bo
b2o2bob2obo5bob2o2bob2obo$13b2o4b2o4b2o4b2o7b2o4b2o8b2o4b2o9b2o4b2o$
15bob2o8bob2o2b2o7bob2o2b4o6bob2o2b4o7bob2o2bob2o$15b2obo8b2obo2bobo6b
2obo2bo2bo6b2obo2bo2bo7b2obo2b2obo$34bo10$32b2o$33bo$2bob2o16bob2o2bo
2bo9bob2o2bo2bo8bob2o2bo2bo8bob2o2bob2o$2b2obo16b2obo2b5o8b2obo2b4o8b
2obo2b4o8b2obo2b2obo$2o4b2o5bo6b2o4b2o5bo5b2o4b2o4b2o4b2o4b2o4b2o4b2o
4b2o4b2o$o2b2obo2b2obobo5bo2b2obo2b2obobo4bo2b2obo2b2obo5bo2b2obo2b2ob
o5bo2b2obo2b2obo$bob2o2bob2obobo6bob2o2bob2obobo5bob2o2bob2obo6bob2o2b
ob2o2bo5bob2o2bob2o2bo$2o4b2o4b2o6b2o4b2o4b2o5b2o4b2o4b2o4b2o4b2o4b2o
4b2o4b2o4b2o$2bob2o2bob2o10bob2o2bob2o9bob2o2bob2o8bob2o2bob2o8bob2o2b
ob2o$2b2obo2b2obo10b2obo2b2obo9b2obo2b2obo8b2obo2b2obo8b2obo2b2obo!

[Ohhhhhhhhh]

What's the maxium speed for any spaceship in Life?
Is there a specific calculator for such speed(s), depending on the direction?
Can we make sure that all such speed(s) can be achieved by actual spaceships?
In all of such spaceships, what's the fastest one, comparing with the following algorithm: sqrt(height^2+width^2)/period?
Finally, for all the previous questions, why (not)?

We already know the fastest speeds are c/2o and c/4d in Life.
For knightships, the fastest is (2,1)c/6.
For camelships, the fastest is (3,1)c/8......
And what's next?

[hotdogPi]

What's the maxium speed for any spaceship in Life?
Is there a specific calculator for such speed(s), depending on the direction?
Can we make sure that all such speed(s) can be achieved by actual spaceships?
In all of such spaceships, what's the fastest one, comparing with the following algorithm: sqrt(height^2+width^2)/period?
Finally, for all the previous questions, why (not)?

We already know the fastest speeds are c/2o and c/4d in Life.
For knightships, the fastest is (2,1)c/6.
For camelships, the fastest is (3,1)c/8......
And what's next?

You can extrapolate and interpolate linearly.

[Macbi]

What's the maxium speed for any spaceship in Life?
Is there a specific calculator for such speed(s), depending on the direction?

If a ship translates itself by (x,y) the number of generations it takes to do that must be at least 2(x+y).

Can we make sure that all such speed(s) can be achieved by actual spaceships?

We can hit c/2, (1,1)c/4 and (2,1)c/6 exactly. For every other direction, we don't know if we can hit the speed limit, but we know we can get arbitrarily close. For example, we don't know if there exists a (3,1)c/8 ship, but we do know how to construct a (3,1)c/8.000000001 ship.

In all of such spaceships, what's the fastest one, comparing with the following algorithm: sqrt(height^2+width^2)/period?

It's c/2 orthogonal. Plotted in space, the maximum speeds form a diamond, so its vertices are the furthest point from the origin.

[GUYTU6J]

[offtopic]

If a ship translates itself by (x,y) the number of generations it takes to do that must be at least 2(x+y). ...

There is a related question: it is known that Day and Night has a (2,1)c/5 knightship but in Game of Life the minimum knightwise period is 6. Is it because of the S4 transition (specifically non-totalistic S4w, which is indeed used at the leading edge of the p5 knightship) in the former rule but not the latter? It looks like I am supposed to read Nathaniel's blog post on this topic, but I am not sure if I really get it.
[/offtopic]
Conjecture: there is a finite spaceship in Game of Life that has pi-heptominoes as its only forward-moving mechanism, and advances by 9 cells in a period of 30 ticks. (Taming the pi-heptomino has been a long unsettled problem. An infinite example would be 3c/10 pi wave, and a finite example but has period 60 in a close-Life non-totalistic rule can be found here.)

[FractalFusion]

If a ship translates itself by (x,y) the number of generations it takes to do that must be at least 2(x+y). ...

There is a related question: it is known that Day and Night has a (2,1)c/5 knightship but in Game of Life the minimum knightwise period is 6. Is it because of the S4 transition (specifically non-totalistic S4w, which is indeed used at the leading edge of the p5 knightship) in the former rule but not the latter? It looks like I am supposed to read Nathaniel's blog post on this topic, but I am not sure if I really get it.

dvgrn also posted John Conway's proof from long ago in this post; it may or may not be easier to follow.

If you want a "LifeHistory"-annotated version of the proof, it goes something like this:

(Click "Show in Viewer" to see the LifeHistory diagrams below)

The diagonal white line in the diagram below represents the upper right boundary of the pattern in Generation 0 (cells on the boundary can be ON); the red squares are empty cells one square to the upper right of this white line (assume the diagram extends indefinitely to the top-left and to the bottom-right). The key of the proof is that none of the red cells will be ON in Generation 2.

(Note: It should also be clear that none of the cells above or to the right of the red cells will be ON in Gen. 2, but I have left that out to be concise.)

Code: Select all

x = 31, y = 31, rule = LifeHistory
11.D$10.C.D$9.2BC.D$8.4BC.D$7.6BC.D$6.8BC.D$5.10BC.D$4.12BC.D$3.14BC.
D$2.16BC.D$.18BC.D$20BC.D$.20BC.D$2.20BC.D$3.20BC.D$4.20BC.D$5.20BC.D
$6.20BC.D$7.20BC.D$8.20BC.D$9.20BC$10.19B$11.17B$12.15B$13.13B$14.11B
$15.9B$16.7B$17.5B$18.3B$19.B!

Proof: There is no B0 or B1, so the red cells will definitely not be ON in Gen. 1.

Now consider the following LifeHistory diagram focusing on one of the white cells (re-marked as yellow), the red cell to its upper-right, cells marked green to the right and above, and cells marked blue to the left and below:

Code: Select all

x = 3, y = 3, rule = LifeHistory
CAD$BEA$.BC!

Since there is no B2, in order for this red cell to be ON in Gen. 2, the neighboring cells to the left, lower-left, and below (the green and yellow cells in the diagram), must all have been ON in Gen. 1. For the same reason, for the green cells to be ON in Gen. 1, its neighboring cells to the left, lower-left, and below (in white, yellow, and blue) must all have been ON in Gen. 0. However, since there is no S4 or S5, the yellow cell (which must have been ON in Gen. 0) would not have survived into Gen. 1 due to the neighboring white and blue cells.

So this confirms that it is impossible for a red cell to be ON in Gen. 2. QED

In other words, it is impossible for a diagonal boundary of a pattern to advance any faster than one horizontal-cell length (that is, 1 hd) every 2 generations. So for a ship to displace itself by (x,y), it would require at least 2(x+y) generations to do so.

The proof above works for every rule from B/S to B345678/S0123678, since it only requires not having B0, B1, B2, S4 and S5. The Day and Night rule contains S4, so the proof does not apply to that rule.

[Ohhhhhhhhh]

If a ship translates itself by (x,y) the number of generations it takes to do that must be at least 2(x+y). ...

There is a related question: it is known that Day and Night has a (2,1)c/5 knightship but in Game of Life the minimum knightwise period is 6. Is it because of the S4 transition (specifically non-totalistic S4w, which is indeed used at the leading edge of the p5 knightship) in the former rule but not the latter? It looks like I am supposed to read Nathaniel's blog post on this topic, but I am not sure if I really get it.

dvgrn also posted John Conway's proof from long ago in this post; it may or may not be easier to follow.

If you want a "LifeHistory"-annotated version of the proof, it goes something like this:

(Click "Show in Viewer" to see the LifeHistory diagrams below)

The diagonal white line in the diagram below represents the upper right boundary of the pattern in Generation 0 (cells on the boundary can be ON); the red squares are empty cells one square to the upper right of this white line (assume the diagram extends indefinitely to the top-left and to the bottom-right). The key of the proof is that none of the red cells will be ON in Generation 2.

(Note: It should also be clear that none of the cells above or to the right of the red cells will be ON in Gen. 2, but I have left that out to be concise.)

Code: Select all

x = 31, y = 31, rule = LifeHistory
11.D$10.C.D$9.2BC.D$8.4BC.D$7.6BC.D$6.8BC.D$5.10BC.D$4.12BC.D$3.14BC.
D$2.16BC.D$.18BC.D$20BC.D$.20BC.D$2.20BC.D$3.20BC.D$4.20BC.D$5.20BC.D
$6.20BC.D$7.20BC.D$8.20BC.D$9.20BC$10.19B$11.17B$12.15B$13.13B$14.11B
$15.9B$16.7B$17.5B$18.3B$19.B!

Proof: There is no B0 or B1, so the red cells will definitely not be ON in Gen. 1.

Now consider the following LifeHistory diagram focusing on one of the white cells (re-marked as yellow), the red cell to its upper-right, cells marked green to the right and above, and cells marked blue to the left and below:

Code: Select all

x = 3, y = 3, rule = LifeHistory
CAD$BEA$.BC!

Since there is no B2, in order for this red cell to be ON in Gen. 2, the neighboring cells to the left, lower-left, and below (the green and yellow cells in the diagram), must all have been ON in Gen. 1. For the same reason, for the green cells to be ON in Gen. 1, its neighboring cells to the left, lower-left, and below (in white, yellow, and blue) must all have been ON in Gen. 0. However, since there is no S4 or S5, the yellow cell (which must have been ON in Gen. 0) would not have survived into Gen. 1 due to the neighboring white and blue cells.

So this confirms that it is impossible for a red cell to be ON in Gen. 2. QED

In other words, it is impossible for a diagonal boundary of a pattern to advance any faster than one horizontal-cell length (that is, 1 hd) every 2 generations. So for a ship to displace itself by (x,y), it would require at least 2(x+y) generations to do so.

The proof above works for every rule from B/S to B345678/S0123678, since it only requires not having B0, B1, B2, S4 and S5. The Day and Night rule contains S4, so the proof does not apply to that rule.

What’s more, if an range-1 INT rule contains S4w,S5a or B2e, it can reach the maxium speed of (n,m)/k with k=min(n,m)*3+abs(n-m)*2.
Something else: if abs function is considered as a formal mathematical calculation, we can use ((a-b)/abs(a-b)+1)/2 as f(a,b), and use a*f(b,a)+b*f(a,b) as min(a,b).

[GUYTU6J]

Yes, but I was referring to knightwise speed specifically. Should I view oblique movements as weighted combinations of orthogonal and diagonal movements?

[Ohhhhhhhhh]

Yes, but I was referring to knightwise speed specifically. Should I view oblique movements as weighted combinations of orthogonal and diagonal movements?

That can be as the same.
Whatever you say, my idea is certainly more general(though not general enough for the rulespaces). But if you want to, the (2,1)c/5 knightship is the fastest possible speed for D&N rule, but not for CGoL - it’s impossible to build such one.

[Wyirm]

I have a conjecture based off of the concept of infinity: Any rule that is capable of periodicity is Turing complete, we just may not be able to find it. So, no rules with b1c, both b2a and b1e. Finite Turing machines can be constructed in any rule that can be periodic, we will just likely never find it. This is because there are an infinite number of patterns. With an infinite number of patterns, we can guarantee that there are an infinite number of functioning Turing machines in every rule.

[dvgrn]

Finite Turing machines can be constructed in any rule that can be periodic, we will just likely never find it.

I suspect it may be possible to find a counterexample that involves a rule that provably allows only a very specific type of periodicity. If you can characterize the behavior of all oscillators in a rule, and none of them allow for signal processing, then you can't build a Turing machine.

The example I thought of is the B4 rule, which allows for an infinite oscillator

Code: Select all

x = 10, y = 10, rule = B4/S:T10,10
obobobobo$bobobobobo$obobobobo$bobobobobo$obobobobo$bobobobobo$obobobo
bo$bobobobobo$obobobobo$bobobobobo!

but doesn't have great prospects for universal computation, since finite patterns always shrink around the edges.

Can anyone think of (or engineer) a rule that allows for finite oscillators, but only of particular limited types -- no oscillators above period 2, for example? That would certainly make Turing completeness impossible. Maybe B3/S is such a rule? It doesn't seem possible to design phoenix-based circuitry capable of carrying signals of any kind.

[GUYTU6J]

Can anyone think of (or engineer) a rule that allows for finite oscillators, but only of particular limited types -- no oscillators above period 2, for example? That would certainly make Turing completeness impossible. Maybe B3/S is such a rule? It doesn't seem possible to design phoenix-based circuitry capable of carrying signals of any kind.

Be careful that the circutry does not even have to be reusable - two examples would be the one-time/burnt-after-using Rule 110 unit cell in LWoD or DotLife. Basically you can have many options for presenting and interacting signals, so B3/S could actually have adequate signal manipulations.

Unrelated, how about the pi-heptomino spaceship I mentioned above?

[toroidalet]

It is possible to send signals in B3/S, shown with an OR and XOR gate (with which it should be possible to construct any logic gate after dealing with timing) and some variations:

Code: Select all

x = 122, y = 180, rule = B3/S
40b2ob6ob2o$42bo6bo$38b2o12b2o$38bo14bo$36bo7b4o7bo$36bo18bo$37bo4bobo
2bobo4bo$36bo5bo6bo5bo$36bo5bobo2bobo5bo$38bo14bo13b2o$38b2o4b4o4b2o$
39b2o10b2o12b2o2b2o$40b2o8b2o13bo4bo$41b2o6b2o12bo8bo$42b2o4b2o15bo4bo
$43b2o2b2o16b2o2b2o2$45b2o20b2o2$40b2ob6ob2o10b2ob6ob2o$42bo6bo14bo6bo
$38b2o12b2o6b2o12b2o$38bo14bo6bo14bo$36bo7b4o7bo2bo7b4o7bo$36bo18bo2bo
18bo$37bo4bobo2bobo4bo4bo4bobo2bobo4bo$36bo5bo6bo5bo2bo5bo6bo5bo$36bo
5bobo2bobo5bo2bo5bobo2bobo5bo$38bo14bo6bo14bo$38b2o4b4o4b2o6b2o4b4o4b
2o$39b2o10b2o8b2o10b2o$40b2o8b2o10b2o8b2o$41b2o6b2o12b2o6b2o$42b2o4b2o
14b2o4b2o$43b2o2b2o16b2o2b2o2$45b2o20b2o2$40b2ob6ob2o2b2o2b2o2b2ob6ob
2o$42bo6bo2b2o2b2o2b2o2bo6bo$38b2o34b2o$38bo36bo$36bo7b4o18b4o7bo$36bo
40bo$37bo4bobo2bobo14bobo2bobo4bo$36bo5bo6bo14bo6bo5bo$36bo5bobo2bobo
14bobo2bobo5bo$38bo36bo$38b2o4b4o18b4o4b2o$39b2o32b2o$40b2o30b2o$41b2o
28b2o$42b2o26b2o$43b2o24b2o$44b2o22b2o$45b2o20b2o$46b2o18b2o$47b2o16b
2o$48b2o14b2o$49b2o12b2o$50b2o10b2o$51b2o8b2o$52b2o6b2o$53b2o4b2o$54b
2o2b2o2$56b2o2$51b2ob6ob2o$53bo6bo$49b2o12b2o$49bo14b2o$47bo7b4o6b2o$
47bo18b2o$48bo4bobo2bobo6b2o$47bo5bo6bo7b2o$47bo5bobo2bobo8b2o$49bo20b
o$49b2o4b4o13bo$50b2o18bo$51b2o16b2o$52b2o14b2o$53b2o12b2o$54b2o10b2o$
55b2o8b2o$56b2o6b2o$57b2o4b2o$58b2o2b2o$20b2ob2o14b2ob2o34b2ob2o14b2ob
2o$22bo18bo18b2o18bo18bo$18b2o5b2o10b2o5b2o30b2o5b2o10b2o5b2o$17b2o7bo
9b2o7bo9b2ob6ob2o9bo7b2o9bo7b2o$16b2o10bo6b2o10bo9bo6bo9bo10b2o6bo10b
2o$15b2o11bo5b2o11bo5b2o12b2o5bo11b2o5bo11b2o$14b2o4b3o4bo5b2o4b3o4bo
5b2o14b2o5bo4b3o4b2o5bo4b3o4b2o$13b2o13bo3b2o13bo3b2o6b4o6b2o3bo13b2o
3bo13b2o$12b2o4bobobobo3bo3bo4bobobobo3bo3bo18bo3bo3bobobobo4bo3bo3bob
obobo4b2o$11b2o5bo5bo3bobo6bo5bo3bobo7bobo2bobo7bobo3bo5bo6bobo3bo5bo
5b2o$10b2o6bo5bo3bobo6bo5bo3bobo7bo6bo7bobo3bo5bo6bobo3bo5bo6b2o$9b2o
7bobobobo3bo3bo4bobobobo3bo3bo5bobo2bobo5bo3bo3bobobobo4bo3bo3bobobobo
7b2o$8b2o18bo3b2o13bo3b2o16b2o3bo13b2o3bo18b2o$7b2o11b3o4bo5b2o4b3o4bo
5b2o5b4o5b2o5bo4b3o4b2o5bo4b3o11b2o$6b2o20bo5b2o11bo5b2o12b2o5bo11b2o
5bo20b2o$5b2o21bo6b2o10bo6b2o10b2o6bo10b2o6bo21b2o$4b2o21bo8b2o7bo9b2o
8b2o9bo7b2o8bo21b2o$3b2o22bo9b2o5b2o10b2o6b2o10b2o5b2o9bo22b2o$2b2o24b
o12bo15b2o4b2o15bo12bo24b2o$2bo25bo10b2ob2o14b2o2b2o14b2ob2o10bo25bo$o
26bo66bo26bo$o26bo32b2o32bo26bo$2bo25bo64bo25bo$2b2o24bo64bo24b2o$3b2o
22bo66bo22b2o$4b2o21bo66bo21b2o$5b2o21bo64bo21b2o$6b2o20bo5b2o2b2o2b2o
2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o5bo20b2o$7b2o11b3o4bo8b2o
2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o2b2o8bo4b3o11b2o$8b2o18bo
3b2o54b2o3bo18b2o$9b2o7bobobobo3bo3bo56bo3bo3bobobobo7b2o$10b2o6bo5bo
3bobo60bobo3bo5bo6b2o$11b2o5bo5bo3bobo60bobo3bo5bo5b2o$12b2o4bobobobo
3bo3bo56bo3bo3bobobobo4b2o$13b2o13bo3b2o54b2o3bo13b2o$14b2o4b3o4bo5b2o
52b2o5bo4b3o4b2o$15b2o11bo5b2o50b2o5bo11b2o$16b2o10bo6b2o48b2o6bo10b2o
$17b2o7bo9b2o46b2o9bo7b2o$18b2o5b2o10b2o44b2o10b2o5b2o$22bo15b2o42b2o
15bo$20b2ob2o14b2o40b2o14b2ob2o$40b2o38b2o$41b2o36b2o$42b2o34b2o$43b2o
32b2o$44b2o30b2o$45b2o28b2o$46b2o26b2o$47b2o24b2o$48b2o22b2o$49b2o20b
2o$50b2o18b2o$51b2o16b2o$52b2o14b2o$53b2o12b2o$54b2o10b2o$55b2o8b2o$
56b2o6b2o$57b2o4b2o$58b2o2b2o2$60b2o2$60b2o2$58b2o2b2o$58bo4bo$56bo8bo
$58bo4bo$58b2o2b2o2$60b2o2$55b2ob6ob2o$57bo6bo$53b2o12b2o$53bo14bo$51b
o7b4o7bo$51bo18bo$52bo4bobo2bobo4bo$51bo5bo6bo5bo$51bo5bobo2bobo5bo$
53bo14bo$53b2o4b4o4b2o$54b2o10b2o$55b2o8b2o$56b2o6b2o$57b2o4b2o$58b2o
2b2o2$60b2o!

Perhaps B3i/S2i or B2-a345678/S01c2345678 (every non-spacefiller is either a dot, block or a blinker) might work.

EDIT: while B3i/S2i has a signal, I am unable to split or even turn it.

[Wyirm]

While B4/S is capable of supporting periodicity, not in any finite way. Wicks and agars exist, but they cannot be stabilized. However, It is a good point that circuitry does not have to be reusable, as we can work around some of the constraints of a rule where no pattern can escape it's own bounding box. However, we may just be overcomplicating it and be trying to prove this wrong rather than right. Even more infertile rules can show periodicity, (albeit not finite), and certain rules, can support agars and wicks, that could never be capable of finite periodicity, such as b1c transitions, or b1e and b2a transitions. My statement may not be as true as I once thought.

[Macbi]

Ilkka Törmä and Ville Salo have added to their gol-agars library a folder of agars that force themselves in the previous generation. So an infinite plane covered with such an agar only ever has one predecessor, the previous generation of that agar. They also found a finite patch of agar with the property that any pattern containing that patch in generation 2 also contained it in generation 0 (the p2 analogue of this stable pattern).

This pattern can be stabilized to produce a p2 oscillator that cannot be synthesised:

Code: Select all

x = 70, y = 59, rule = LifeHistory
2.A.A3.2A9.A2.A2.A.2A11.A10.A3.2A.A2.2A$2.2A.A2.A10.7A.A.A.2A2.2A2.A.
A5.A2.A.A2.A.2A2.A.A$5.A2B2.A.2A3.2A7.A2.A.A4.A2.A.A3.3A2.A2.A.A3.2A
2.A2.A$2.3A2.4A.A.A.A.B.A.3A.A.A2.A.A2.A.2A.2A.A3.2A2.2A.4A.3A.3A2.A$
.A3.3A4.B.A.AB.3A2.2B2A.2A.A.A.A.B3.A.2A.A2.2B6.3B2.A3.3A$.2A.A2.A.4A
B2A.A5.A.B.A2.A2.B3A2B3A6.3A.4A2.A2BA.A.BA$2.A.A.A2BA.A4.2A.4A.A.A.A
2.A2B.A.A.A.A.2A.2A2.A.A2.A2.2A.A.3A2.2A$A2.B3AB.B2.3A2.A.A2.A.A.A.4A
.4A.2A.A2.2A.A2.3A2.A.2A.A2B.A.2A.A$2A.B.2A.B3A.B.2AB.A4.A.A.B2.A.A2.
B.A.B.A4.B2A.B.3A.B3A.BA.B.A$2.A.A.AB2A.AB.BA.A2.4A.BA.AB2A.2ABA.AB.
2A.2A.A.AB.BA.AB.B2.2A.2B2A$2.A.A.B3.A.AB.4A.A3.2B.2A.B3.B.2A.A4.A.4A
.B.3A.BA2.A.2A.A.2A$3.2A.4ABA.2A.B.B.A.2A.2A.A2.3A2.A.2A.2A.A.B.B.3A.
B.2A.AB2A.A.A2.A$A5.A2.B.BA.AB.BA.A2.A.A.2ABA.A.AB2A.A.A2.A.AB.BA.AB.
BA.AB.BA.A.2A$4AB2A2.ABA.A.AB2A.ABA2.A.AB.BA.AB.BA.A2.ABA.2ABA.A.ABA.
2A.B3.A$4.A.ABA.A.ABA2.A.AB.B2.A3.B.3A.B3.A2.B.BA.A2.ABA.A.AB.5A.5A$
2A.3AB.BA.AB.B2.2A.AB3A.5A.B.5A.3ABA.2A2.B.BA.AB.BA.A2.A4.A$A.2B.A.B.
2A.AB3A.BA.A3.A2.A.AB.BA.A2.A3.A.AB.3ABA.A.AB.3A2.A.3A$2.A2B.3A.BA2.A
.AB.BA.2A.A2.3A.B.3A2.A.2A.AB.BA.A2.ABA.2A.B.3A.A$3.2A.A.AB.B2.3A.B.
3AB.3A.B.3A.B.3A.B3A.B.3A2.B.BA.AB.BA2.B$.B2A.AB2A.B3A.B.3A2.B.BA.AB.
BA.AB.BA.AB.B2.3A.B.3ABA.2A.B.3AB.A$2A.AB3.A.2A.AB.BA.A.DC2D3C2DCDCDC
2D3C2DCD.A.AB.BA.A2.AB.3A2.A.A.A$.B.2B3.A.A.A.AB.3ADAD2C3D2CDCDCD2C3D
2CDCDC2A.B.3A2.B.BA.A2.A.A2.A$2.2A.2A.A.2ABA.2A2.BDBCDC3DCDC3DCDC3DCD
C3D2.3A.B.3AB.2AB2A2.3A$4.2A.A.A.B.BA.A2.ADCDCDC2D2CDCDCDCDC2D2CDCDCD
.A.AB.BA.2A.A3.A.A$2.2A2.A2.A.ABA.2ABA.ADCDCD2C2DCDCDCDCD2C2DCDCDCDC
2A.BA.A.A.A3.A.4A$2.2BA2.2A.A2.3AB.BA.C3DCDC3DCDC3DCDC3DCDC3D2.2A.AB
2A.A.2A6.A$.A2B6.A.A4.B.2ADCDCD2C3D2CDCDCD2C3D2CDCDCD.A.AB.B.B.A2.3AB
.2A$2.2A3.3A.A.6A.DCDCDC2D3C2DCDCDC2D3C2DCDCDCB2A.ABABA.A.A2.2A$6.A.B
2.A.A2.A.AB2DCDC3DCDC3DCDC3DCDC3DCDCD.B3A3.2A.A.2A.4A$6.A2.B.A.2A.3A.
2D3C3D3C3D3C3D3C3D3CDB4.3A2.A2.A.AB2.A$2.B2.2A.3A.BA.A.B.A2C3D3C3D3C
3D3C3D3C3DC5A2.A2.3A2.2B.A$.3A3.A4.B2.AB.BADC3DCDC3DCDC3DCDC3DCDC3DC.
A2.A.4A3.3A.A$2.B4.A.4A2.A.BA.CDC2D3C2DCDCDC2D3C2DCDCDC2DC2A.2A.BA.A
2.2A.2A$8.2A2.A3.2A.ADCD2C3D2CDCDCD2C3D2CDCDCD2CDB.A.A2B2.2B2.2BA$11.
2A.A.A.AB2DCDC3DCDC3DCDC3DCDC3DCDCD.BA3.3AB3AB2.A$5.A2.2ABA.A2B2A.ADC
DCDC2D2CDCDCDCDC2D2CDCDCDCDCB.A4.2A2.2A.A.A2.A$3.3A2.A2.B.AB.BA.A.DCD
CD2C2DCDCDCDCD2C2DCDCDCBAD2A4.A2.A.B.2A2.3A$2.A6.3A.A.B3.A2.3DCDC3DA.
A3DCDC3DA.A3DA.A.A2.A2BA.A2.A$2.2A.4A3.7A.2ACDCD2C2D.2A.CDCD2C2DA.A.A
BA.2A2BA.A2.A.2A.A.A.2A$3.A.A2.B.A.B.A4.A3.A.AB.3A.BA.A.AB.2A.ABA2.A.
AB.B2A4.A2.A.2A.A$3.A2.AB.3A2B2.2A.A.2A.AB.BA.AB.BA.AB.BA.AB.B2.A3.B.
A6.A.A4.A$2A.2A.A.A2.A.3A.A.A.B3A.BA.A.AB.2A.AB.2A.AB3A.5A.3A2.2A.A.
2A.2A$.A4.A2.2A.2A2.A2.AB.B2.2A.ABA.2A.BA.2A.BA.A3.A5.A.A.A4.A.A.A$A
2.3A.2A2.A.A.A3.A.BA2.A.AB.BA.AB.BA.AB.BA.2A.A2.2A.A4.5A.A.A$3AB2.A2.
2A.2B.2A3.2A.AB2A.ABA.A.AB.2A.AB.3AB.2AB.A2.4A5.A.A.2A$4.BA2.A2.B.2A
2.A3.2AB.BA.A2.ABA.2A.BA.2A2.B.BA.A2.2A4.A2.A2.AB.A$2.3A.2A.AB3A2.2A
2.A.A.B3.A2.B.BA.AB.BA.A2.AB.5A3.4A2.4A2.A$.A4.2A.A2.A.2A2.3AB.5A.3AB
A.2A.BA.2ABA.2A.B3.4A6.B.3A$.A.2A.2B2.2A.B2.AB2A.B5.A.B3.A.BA.2A.AB.B
A.AB.BA.A4.2A3.2B$2A2.2A2.2A2.2B2A.2B2.3A.2A.A.B3AB.B2A2.B.B.2A.AB2A.
A.3A2.A.3A.2A$2.A4.A3.2A.3A2.2A3.2A.A.A.2A.AB.A.A.4A.BA2.A.2A.A2.2A.
2A4.A$2A.2A.2A.2A2.A.B2.A2.2A4.A.A.B2.2ABA.2A.A.AB.B2.2A.AB2.A.A.A5.A
.A$.A.A4.A.A.2A5.A.A.3A.3A2B3A3.A3.B2A.B3A.BA2.B3A.B.A2.2A.2A$A2.A4.A
3.A7.A4.AB.A.A.A.4A2.2A2.AB2A.A2B.3A3.B.2A3.A$3A3.2A2.A.A2.BAB9.BA.2A
2.B6.A.A4.A.A.2A2.A.2A6.A$7.A.2A.3A.A.AB2.BAB.AB.A2.2AB.2A3.A.A.5A3.A
.3A.A.4A.2A$3A4.A3.A2.B.A.A.2A.A.A.A.A.A.A.A2.A3.A.A8.A2B2.A2.A3.A2.A
$A2.A.2A.2A2.A2.AB.A.2B.A.B.A2.A.A2.A.A6.A.2A6.2BA2.2A3.A2.A$3.2A.A.A
.2A5.ABA2.ABA.2A3.A3.2A7.2A.A6.2A9.2A!

(This stabilization has not been optimized.)

EDIT: Improved stabilisation.

Code: Select all

x = 64, y = 53, rule = LifeHistory
3.ABA.ABA17.2A.2A13.ABA4.BAB4.ABA$2.B.A.B.BAB2.ABA11.A3.A11.AB.A.BABA
.A.ABAB.A.B$.2A.A.A4.AB.A.BA10.3A10.AB.A.A.A2.A.A.A2.A.A.2A$.B.A.A.A
4.A.A.A.BA4.2A3.A3.2A4.AB.A.A.A.2A.A.A.A.2A.A.2B$.A.A.A2.A2.2A.A.A.A.
BA.A2BA2.A2.A2BA.AB.A.A.A.A2.A2.A2.A.A2.A.A$.BA2.2A.A2.A2.A2.2A.A.B2.
B2.3A2.B2.B.A.2A.2AB.A2.A.A.2A2.A2.A$A2.2A3.2A.2ABA5.A.A2B3A.B.3A2BA.
A4.A.2B.2A.A.A2.2A.2A$B2A2.2A3.2AB2.6A.A.2A.AB.BA.2A.A.6A.2A.A2.A2.A.
A2.A$A2.A.A.3A2.B2.B6.A3.A.ABA.A3.A6.B.2A3.A2.2A3.A2.A$B.2AB4.B.2A.AB
.5A.3ABA.A.AB3A.5A.BA2.3A5.A3.2A.A$3A.2B3A2B.3A.A.B3.A2.B.BA.AB.B2.A
3.B.A.A2.A2.4A.A5.A$.B.2A.A.2A.A3.2AB.BA.A2.ABA.A.ABA2.A.AB.B2A5.A4.A
.2A3.A.A$3.2A.A2.A.A2.2A.AB2A.ABA.A.ABA.A.ABA.2ABA.2A5.A2.A2.A.A3.2A$
.2A.2BA.A.2A.A.BA2.A.AB.BA.AB.BA.AB.BA.A2.AB.A.4A2.A.A3.A$A.2A.B.2AB
3.AB.B2.2A.ABA.2A.B.2A.ABA.2A2.B.BA.A3.2A.A.2A.A2.2A$A4.3A.B3.A.B3A.B
A.A.AB.3A.BA.A.AB.3AB.A.A.A.2A.A.A.2A.A.A$.4A.A.A.2A.A.2A.AB.BA.AB.BA
.AB.BA.AB.BA.2A.A2.2A2B2.AB5.A$4.A.B.A.A.2A3.ADC2D3C2DCDCDC2D3C2DCDA
3.A5.B2A2.B3A.BA$A.A.2ABA.A4.3ADAD2C3D2CDCDCD2C3D2CDCDC2A.6A2.3A.A.2B
A$2A.A.A2.3A.2A2.BDBCDC3DCDC3DCDC3DCDC3D2.A3.B.3A5.2A$3.A.A.2A.2B.A2.
ADCDCDC2D2CDCDCDCDC2D2CDCDCD.A.AB.BA.A2.3A.2A$3A.A.A.3BA.ABA.ADCDCD2C
2DCDCDCDCD2C2DCDCDCDC.2A2BA.A.A.B.2AB$A2.A2.A.A.2A.B.BA.C3DCDC3DCDC3D
CDC3DCDC3DA.A.A2.A.A2.BA$3.A.AB.2A.3ABA.ADCDCD2C3D2CDCDCD2C3D2CDCDCD
2A4.A2.2A.BA$2.2A.A2BA.AB2.A.ADCDCDC2D3C2DCDCDC2D3C2DCDCDCB.A2.2A3.A.
A2.A$3.A3.A.A.2BA.AB2DCDC3DCDC3DCDC3DCDC3DCDCD.BA2.B3.A2.4A$.A.A.A.A.
2A.4A.2D3C3D3C3D3C3D3C3D3CDB.A.AB3.A.2A$A.A.A.2A.A4.B.A2C3D3C3D3C3D3C
3D3C3DC2A.2A.2A.A.2B.2A$A.A.A5.3AB.BADC3DCDC3DCDC3DCDC3DCDC3DC.A2.A.A
2.A2.A.2A$.A.A.4ABA.2ABA.CDC2D3C2DCDCDC2D3C2DCDCDC2DC5A2.A.4A$3.A.B2.
B.BA.A2.ADCD2C3D2CDCDCD2C3D2CDCDCD2CDB4.3A4.4A$2.A2.AB.ABA.2A2.B2DCDC
3DCDC3DCDC3DCDC3DCDCD.B3A4.2A2B3.A$2.4A.A.A.AB.3ADCDCDC2D2CDCDCDCDC2D
2CDCDCDCDCB2A.AB3A.A2.3A$5.A.2A.AB.BA.A.DCDCD2C2DCDCDCDCD2C2DCDCDCBAD
.A.AB.B.B.A.A.A$6A.A.2A.B.3A2.3DCDC3DA.A3DCDC3DA.A3D2.2A.ABA.B3AB.A$A
4.2B.AB.3A.B.2ACDCD2C2D.2A.CDCD2C2DA.A.AB3A.BA.A.A.A2.B3A$2.2A.A2.B.B
A.AB.BA.A2.AB.3A.BA.A.AB.2A.ABA2.A.AB.BA.2A2.2A4.A$3.A.4AB.3A.B.3A2.B
.BA.AB.BA.AB.BA.AB.B2.3A.B.2A.A.2A.4A$.A.A2.A.2A.A2.3A.B.3AB.3A.B.3A.
B.2A.AB3A.B.3A.BA.BA.A$A.A.AB3.A.A2.A.AB.BA.2A.A2.3A.B.3A.BA2.A.AB.BA
.AB.B2.B.3A$A.A.A.B3A.6A.BA.A.A.A2.A.AB.BA.AB.B2.3A.B.3A.B4A.B2.A$.A
3.2A2.2B4.B.2A.AB4AB4A.B.3A.B3A.B.3A2.A.2A.A.B.A.A$7.2A.B3AB.BA.AB.B
4.B.B.3A2.A.2A.AB.BA.A2.A.A2.2A.A.A$3.5A.A.A.2ABA.A.ABA.2A.A2B.A2.A.A
.A.A.AB.5A2.3A.A.A$2.A3.B.2A.A2.A2.3A2.A.A3.3A.5A.2ABA.2A.B3.2A2.2BA.
2A$2.A.AB.BA.A.3A.B2.B2.A.A4.A.A.B3.A.B.BA.AB.B2A2.2A.B.A.B2.A$2A.A.
2A.2B.2A.AB2A.A2B.A3.A.A.AB.BA.A.ABA.A.AB2A.A2B2.2A.AB.A.A$A2.A2.3A2B
2.B3.3A.2A3.A.2A2.A.2A.A.A2.3A2.A2.AB.3A.2A.A.2A$.A.ABA.2A.3A.B2A3.A
5.A3.2A5.A.A.B3.B.2A3.A5.A.A$2.A2.BAB.A3.A.A2.2A.4A.4A2.4A.A.AB2A.2AB
A.3A2.4A2.A$3.2A4.2A2.A3.2A.A4.A3.A.A2.A.A.A3.3A3.A3.2A3.A.A.2A$5.4A
2.A.A6.A.2A.A2.A2.A6.A.2A.B.2A.A2.A2.A2.A2.A2.A$5.A2.A2.2A7.2A.2A4.2A
6.2A.2A3.2A.2A2.2A2.2A4.2A!

[yujh]

WLS sucks. anyways, some manual work

Code: Select all

x = 64, y = 53, rule = LifeHistory
3.ABA.ABA17.2A.2A13.ABA4.BAB4.ABA$2.B.A.B.BAB2.ABA11.A3.A11.AB.A.BABA
.A.ABAB.A.B$.2A.A.A4.AB.A.BA10.3A10.AB.A.A.A2.A.A.A2.A.A.2A$.B.A.A.A4.
A.A.A.BA4.2A3.A3.2A4.AB.A.A.A.2A.A.A.A.2A.A.2B$.A.A.A2.A2.2A.A.A.A.BA
.A2BA2.A2.A2BA.AB.A.A.A.A2.A2.A2.A.A2.A.A$.BA2.2A.A2.A2.A2.2A.A.B2.B2.
3A2.B2.B.A.2A.2AB.A2.A.A.2A2.A2.A$A2.2A3.2A.2ABA5.A.A2B3A.B.3A2BA.A4.
A.2B.2A.A.A2.2A.2A$B2A2.2A3.2AB2.6A.A.2A.AB.BA.2A.A.6A.2A.A2.A2.A.A2.
A$A2.A.A.3A2.B2.B6.A3.A.ABA.A3.A6.B.2A3.A2.2A3.A2.A$B.2AB4.B.2A.AB.5A
.3ABA.A.AB3A.5A.BA2.3A5.A3.2A.A$3A.2B3A2B.3A.A.B3.A2.B.BA.AB.B2.A3.B.
A.A2.A2.4A.A5.A$.B.2A.A.2A.A3.2AB.BA.A2.ABA.A.ABA2.A.AB.B2A5.A4.A.2A3.
A.A$3.2A.A2.A.A2.2A.AB2A.ABA.A.ABA.A.ABA.2ABA.2A5.A2.A2.A.A3.2A$.2A.2B
A.A.2A.A.BA2.A.AB.BA.AB.BA.AB.BA.A2.AB.A.4A2.A.A3.A$A.2A.B.2AB3.AB.B2.
2A.ABA.2A.B.2A.ABA.2A2.B.BA.A3.2A.A.2A.A2.2A$A4.3A.B3.A.B3A.BA.A.AB.3A
.BA.A.AB.3AB.A.A.A.2A.A.A.2A.A.A$.4A.A.A.2A.A.2A.AB.BA.AB.BA.AB.BA.AB
.BA.2A.A2.2A2B2.AB5.A$4.A.B.A.A.2A3.ADC2D3C2DCDCDC2D3C2DCDA3.A5.B2A2.
B3A.BA$A.A.2ABA.A4.3ADAD2C3D2CDCDCD2C3D2CDCDC2A.6A2.3A.A.2BA$2A.A.A2.
3A.2A2.BDBCDC3DCDC3DCDC3DCDC3D2.A3.B.3A5.2A$3.A.A.2A.2B.A2.ADCDCDC2D2C
DCDCDCDC2D2CDCDCD.A.AB.BA.A2.3A.2A$3A.A.A.3BA.ABA.ADCDCD2C2DCDCDCDCD2C
2DCDCDCDC.2A2BA.A.A.B.2AB$A2.A2.A.A.2A.B.BA.C3DCDC3DCDC3DCDC3DCDC3DA.
A.A2.A.A2.BA$3.A.AB.2A.3ABA.ADCDCD2C3D2CDCDCD2C3D2CDCDCD2A4.A2.2A.BA$
2.2A.A2BA.AB2.A.ADCDCDC2D3C2DCDCDC2D3C2DCDCDCB.A2.2A3.A.A2.A$3.A3.A.A
.2BA.AB2DCDC3DCDC3DCDC3DCDC3DCDCD.BA2.B3.A2.4A$.A.A.A.A.2A.4A.2D3C3D3C
3D3C3D3C3D3CDB.A.AB3.A.2A$A.A.A.2A.A4.B.A2C3D3C3D3C3D3C3D3C3DC2A.2A.2A
.A.2B.2A$A.A.A5.3AB.BADC3DCDC3DCDC3DCDC3DCDC3DC.A2.A.A2.A2.A.2A$.A.A.
4ABA.2ABA.CDC2D3C2DCDCDC2D3C2DCDCDC2DC5A2.A.4A$3.A.B2.B.BA.A2.ADCD2C3D
2CDCDCD2C3D2CDCDCD2CDB4.3A4.4A$2.A2.AB.ABA.2A2.B2DCDC3DCDC3DCDC3DCDC3D
CDCD.B3A4.2A2B3.A$2.4A.A.A.AB.3ADCDCDC2D2CDCDCDCDC2D2CDCDCDCDCB2A.AB3A
.A2.3A$5.A.2A.AB.BA.A.DCDCD2C2DCDCDCDCD2C2DCDCDCBAD.A.AB.B.B.A.A.A$2.
4A.A.2A.B.3A2.3DCDC3DA.A3DCDC3DA.A3D2.2A.ABA.B3AB.A$.A3.2B.AB.3A.B.2A
CDCD2C2D.2A.CDCD2C2DA.A.AB3A.BA.A.A.A2.B3A$2.2A.A2.B.BA.AB.BA.A2.AB.3A
.BA.A.AB.2A.ABA2.A.AB.BA.2A2.2A4.A$3.A.4AB.3A.B.3A2.B.BA.AB.BA.AB.BA.
AB.B2.3A.B.2A.A.2A.4A$3.A2.A.2A.A2.3A.B.3AB.3A.B.3A.B.2A.AB3A.B.3A.BA
.BA.A$.2A.AB3.A.A2.A.AB.BA.2A.A2.3A.B.3A.BA2.A.AB.BA.AB.B2.B.3A$A.A.A
.B3A.6A.BA.A.A.A2.A.AB.BA.AB.B2.3A.B.3A.B4A.B2.A$.A3.2A2.2B4.B.2A.AB4A
B4A.B.3A.B3A.B.3A2.A.2A.A.B.A.A$7.2A.B3AB.BA.AB.B4.B.B.3A2.A.2A.AB.BA
.A2.A.A2.2A.A.A$3.5A.A.A.2ABA.A.ABA.2A.A2B.A2.A.A.A.A.AB.5A2.3A.A.A$2.
A3.B.2A.A2.A2.3A2.A.A3.3A.5A.2ABA.2A.B3.2A2.2BA.2A$2.A.AB.BA.A.3A.B2.
B2.A.A4.A.A.B3.A.B.BA.AB.B2A2.2A.B.A.B$2A.A.2A.2B.2A.AB2A.A2B.A3.A.A.
AB.BA.A.ABA.A.AB2A.A2B2.2A.AB.2A$A2.A2.3A2B2.B3.3A.2A3.A.2A2.A.2A.A.A
2.3A2.A2.AB.3A.2A.A.A$.A.ABA.2A.3A.B2A3.A5.A3.2A5.A.A.B3.B.2A3.A5.A.A
$2.A2.BAB.A3.A.A2.2A.2A4.3A2.4A.A.AB2A.2ABA.3A2.4A2.A$3.2A4.2A2.A3.2A
.A2.A5.A.A2.A.A.A3.3A3.A3.2A3.A.A$5.4A2.A.A6.A.A6.A.A6.A.2A.B.2A.A2.A
2.A3.A$5.A2.A2.2A7.2A8.A6.2A.2A3.2A.2A2.2A!