3 ms·
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 enter
by 1-more 7y ago
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 https://www.conwaylife.com/wiki/R-pentomino
- ALittleLight 7y agoThat'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.
- 1-more 7y agooh 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.