News for hackers. Stuff that matters.
Re:Finding Mona Lisa in the Game of Life by 1-more on Friday March 13, 2020 @04:07PM (#22570449)
You might be able to start with a much smaller starting state. Like the R pentomino starts with a tiny starting state and runs for a very long time before entering a quiescent state. So your encoding scheme could be just enough info to say "a grid with dimensions h_0 by w_0 filled with bit pattern b_0, run for n generations, then take the bit pattern b_n from the cells in the rectangle with dimensions h_n by w_n with top left corner at x_n y_n from our initial top left corner." As long as h_0 times w_0 is pretty small compared to h_n by w_n you'll come out with compression.

https://www.conwaylife.com/wiki/R-pentomino

Re:Finding Mona Lisa in the Game of Life by ALittleLight on Friday March 13, 2020 @06:50PM (#22571565)
That's really interesting and seems like it could (in theory) work, though it would be challenging and time consuming to actually compress data this way.
Re:Finding Mona Lisa in the Game of Life by 1-more on Saturday March 14, 2020 @06:16PM (#22579134)
oh yeah like the paper says it's doing SAT a lot of times. Nearest I can tell the time complexity for each bit of the output is O(n!) where n is the size of the (unknown and you are solving for it) input bit pattern. So total time complexity is something like O(n! * w_n * h_n) which is BIG and stupid and might make this actually not a way to beat the optimum compression ratio dictated by entropy.