Don presented on "Recreational Computing" at the Joint Mathematics Meeting in San Francisco this past Saturday, and one of the things he talked about was this problem. I'm also interested in this problem. As I see it, there are two ways it can go. Either, we find a set of constructions that (jointly) cover the plane, or we find a particular coordinate and prove it cannot be set by any pattern in the required time.
I've burnt some CPU cycles a few years ago on this, and I can find a pattern that sets the required cell for all cells with a generation value of 50 or less. The next few cases are:
-9,30,51 -10,31,52 -19,36,53 -11,32,53 -9,31,53 -32,43,54 -20,37,54 -10,32,54 -19,37,55 -11,33,55 -9,32,55
This means, can you find a pattern that lives entirely in cell coordinates with x<=0 and y<=0, that has cell (-9,30) alive at generation 51?
And another (or possibly the same!) that has cell (-10,11) alive at generation 52? The generation value is always
x[x>0]+y[y>0]+(x+y)[x+y>0]
where [exp] means 0 if exp is false, and 1 if exp is true. (This is a really neat and useful notation.)
I've experimented with just generating random patterns, and also with using SAT solvers. I think this is an interesting problem and worthy of some effort. In particular, if someone is able to find a value (x,y) that cannot be satisfied, we've proved the overall conjecture false.
Conversely, if we can find patterns that generate spaceships that populate an infinite number of values, that's highly useful as well.
At the moment I'm not making any effort to minimize the solutions I find. For instance, a recent find is this one which solves -8,27 (at generation 46):
Code:
Select all
x = -16, y = -16, rule = B3/S23
17o$bob2o3b2o4b2o$8b2ob2o2b2o$obob2ob2o7bo$o3b2obo4b2ob2o$2bo2b2ob2ob
2o2b2o$3bo3bo3bo2b2o$bo2bobob2o2bobobo$2o2bo2bo8bo$obo6bo2b2o2bo$4o2bo
2b2obo2bo$bo3b2o4b2o2b2o$obo3bob2o3bob2o$obob2obo4b2obo$7b2ob2o3bo$7bo
3b2obobo$b4o2b2o!
The blob below has an ASCII representation of values I have and ones I lack (you may need to zoom out and/or widen your window). If there's a digit, that means I have a solution; if there is a dot, I don't. The x coordinate is vertical; the last digit of the y coordinate is used for values I have (although the problem is symmetric x vs y so feel free to visualize it the other way if you want).
Code: Select all
-74 5
-73 45
-72 345
-71 2345
-70 12345
-69 012345
-68 9012345
-67 89012345
-66 789012345
-65 6789012345
-64 56789012345
-63 456789012345
-62 3456789012345
-61 2345678901234.
-60 1234...........
-59 0123456789012345
-58 90123456789012345
-57 8901234567........
-56 78901234...........
-55 67890123456789......
-54 56789012345678.......
-53 45678901234567........
-52 34567890123456789012345
-51 23456789012345678901234.
-50 12345678901..............
-49 012345....................
-48 9012345678901234...........
-47 8901234567890123............
-46 78901234567890...............
-45 6789012345....................
-44 5678901234567890...............
-43 4567890123456789................
-42 34567890123456...................
-41 23456789012345....................
-40 12345678901234.....................
-39 01234567890123......................
-38 90123456789012345....................
-37 89012345678901234567890...............
-36 78901234567890123456789................
-35 67890123456.............................
-34 5678901234567............................
-33 4567890123456.............................
-32 3456789012.................................
-31 23456789012345..............................
-30 12345678901234...............................
-29 01234567890123................................
-28 90123456789012.................................
-27 89012345678901..................................
-26 78901234567890...................................
-25 6789012345678901234...............................
-24 5678901234567890123................................
-23 4567890123456789012.................................
-22 34567890123456789012345..............................
-21 23456789012345678901234...............................
-20 1234567890123456.......................................
-19 0123456789012345........................................
-18 90123456789012345678.....................................
-17 89012345678901234567......................................
-16 7890123456789012345678.....................................
-15 6789012345678901234567......................................
-14 56789012345678901234567890...................................
-13 45678901234567890123456789....................................
-12 345678901234567890123..........................................
-11 23456789012345678901............................................
-10 12345678901234567890.............................................
-9 01234567890123456789..............................................
-8 90123456789012345678901............................................
-7 890123456789012345678901............................................
-6 7890123456789012345678901234567......................................
-5 6789012345678901234567890123456.......................................
-4 56789012345678901234567890123456789012345678901234567890123456789012345
-3 456789012345678901234567890123456789012345678901234567890123456789012345
-2 3456789012345678901234567890123456789012345678901234567890123456789012345
-1 23456789012345678901234567890123456789012345678901234567890123456789012345
0 123456789012345678901234567890123456789012345678901234567890123456789012345
1 23456789012345678901234567890123456789012345678901234567890123456789012345
2 3456789012345678901234567890123456789012345678901234567890123456789012345
3 456789012345678901234567890123456789012345678901234567890123456789012345
4 56789012345678901234567890123456789012345678901234567890123456789012345
5 6789012345678901234567890123456789012345678901234567890123456789012345
6 78901234567890123456789012345.7.9.1.3.5.7.9.1.3.5.7.9.1.3.5.7.9.1.3.5
7 89012345678901234567.....34.........................................
8 90123456789012345.78...............................................
9 01234567890123456.89..............................................
10 12345678901234567.90.............................................
11 23456789012345678.01............................................
12 34567890123456789.12...........................................
13 45678901234567890.23..........................................
14 56789012345678901.34.........................................
15 67890123456789012.45........................................
16 78901234567890123.56.......................................
17 89012345678901234.67......................................
18 90123456789012345.78.....................................
19 01234567890123456.89....................................
20 12345678901234567.90...................................
21 23456789012345678.01..................................
22 34567890123456789.12.................................
23 45678901234567890.23................................
24 56789012345678901.34...............................
25 67890123456789012.45..............................
26 78901234567890123.56.............................
27 89012345678901234.67............................
28 90123456789012345.78...........................
29 01234567890123456.89..........................
30 12345678901234567.90.........................
31 23456789012345678.01........................
32 34567890123456789.12.......................
33 45678901234567890.23......................
34 56789012345678901.34.....................
35 67890123456789012.45....................
36 78901234567890123.56...................
37 89012345678901234.67..................
38 90123456789012345.78.................
39 01234567890123456.89................
40 12345678901234567.90...............
41 23456789012345678.01..............
42 34567890123456789.12.............
43 45678901234567890.23............
44 56789012345678901.34...........
45 67890123456789012.45..........
46 78901234567890123.56.........
47 89012345678901234.67........
48 90123456789012345.78.......
49 01234567890123456.89......
50 12345678901234567.90.....
51 23456789012345678.01....
52 34567890123456789.12...
53 45678901234567890.23..
54 56789012345678901.34.
55 67890123456789012.45
56 78901234567890123.5
57 89012345678901234.
58 90123456789012345
59 0123456789012345
60 123456789012345
61 23456789012345
62 3456789012345
63 456789012345
64 56789012345
65 6789012345
66 789012345
67 89012345
68 9012345
69 012345
70 12345
71 2345
72 345
73 45
74 5
75
-9,30,51 -10,31,52 -19,36,53 -11,32,53 -9,31,53 -32,43,54 -20,37,54 -10,32,54 -19,37,55 -11,33,55 -9,32,55