Knuth's conjecture about CGoL

For general discussion about Conway's Game of Life.
Post Reply
User avatar
Scorbie
Posts: 1692
Joined: December 7th, 2013, 1:05 am

Knuth's conjecture about CGoL

Post by Scorbie » April 29th, 2015, 8:39 am

Bill Gosper wrote:Knuth expressed strong interest in
(dis)proving his conjectural formula f(i,j)
(http://www-cs-faculty.stanford.edu/~uno/fasc6a.ps.gz
(seems to be deliberately crIPpled).
page122 "116" example 88
for the soonest cell i,j can turn on
if initially, all cells with a non-negative coordinate are off.
Also, although this fascicle is very preliminary, he offers his
usual monetary bounty on detected bugs.
No need to download the postscript file. Here's the question. (Knuth's conjecture is #88)

87. [22] (Light speed.) Imagine Life on an infinite plane, with all cells dead at time 0 except in the lower left quadrant. More precisely, suppose X_t = (x_tij) is defined for all t >= 0 and all integers -infinity< i, j < +infinity, and that x_0ij = 0 whenever i > 0 or j > 0.
a) Prove that x_tij = 0 whenever 0 <= t < max(I, j).
b) Furthermore x_tij = 0 when 0 <=-i <= j and 0<= t < i + 2j.
c) And x_tij = 0 for 0 <= t < 2i + 2j, if i >= 0 and j >= 0. Hint: If x_tij = 0 whenever i >=-j, prove that x_tij = 0 whenever i >-j.

88. [21] According to the previous exercise, the earliest possible time that cell (i, j) can become alive, if all initial life is confined to the lower left quadrant of the plane, is at least
f(i, j) = i[i>=0] + j [j >=0] + (i + j)[i + j >=0].
For example, when abs(i)<=_ 5 and abs(j)<= 5 the values of f(i, j)
are shown at the right.

Code: Select all

5  6  7  8  9 10 12 14 16 18 20
4  4  5  6  7  8 10 12 14 16 18
3  3  3  4  5  6  8 10 12 14 16
2  2  2  2  3  4  6  8 10 12 14
1  1  1  1  1  2  4  6  8 10 12
0  0  0  0  0  0  2  4  6  8 10
0  0  0  0  0  0  1  3  5  7  9
0  0  0  0  0  0  1  2  4  6  8
0  0  0  0  0  0  1  2  3  5  7
0  0  0  0  0  0  1  2  3  4  6
0  0  0  0  0  0  1  2  3  4  5
Let f*(i, j) be the actual minimum time at which cell (I, j) can be alive, for some such initial state. Devise a set of clauses by which a SAT solver can test whether or not f*(i0, j0) = f(i0, j0), given i0 and j0. (Such clauses make interesting benchmark tests.)

So, anyone care for tackling the problem?

User avatar
Tropylium
Posts: 421
Joined: May 31st, 2011, 7:12 pm
Location: Finland

Re: Knuth's conjecture about CGoL

Post by Tropylium » November 16th, 2015, 1:05 pm

The two SW-most octants (including the diagonal (x+y = 1) are trivial; everything sufficiently far away NE, starting with (1, 1) being 4, follows from the c/4 diagonal speed limit theorem. That doesn't seem to leave a whole lot of edge cases really.

rokicki
Posts: 80
Joined: August 6th, 2009, 12:26 pm

Re: Knuth's conjecture about CGoL

Post by rokicki » January 9th, 2024, 5:25 pm

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

Post Reply