6 ms·

For years I'm been thinking about something like this in terms of data compression: Would it be possible to have some sort of cellular automata program that ge

For years I'm been thinking about something like this in terms of data compression: Would it be possible to have some sort of cellular automata program that generates the uncompressed data after so many generations. The compressed data would be the start state of the game field, which over several generations would produce the uncompressed data. For it to work, you would have to start with the uncompressed data and work backwards. Which is what the author of this article is trying to do with these pictures. Based on what I can understand from the article, there is no hope for my data compression scheme.

ALittleLight 7y ago
How does this compress data though even if you could easily find parent states? Don't you have to have at least one bit per cell (alive or dead) for your whole grid? You have some information which is X bits long, so you turn it into a game of life board. Then you find a parent state which is still X bits long. How does that help with compression?
- waltbosz 7y ago
  I should explain ... the extent of my knowledge of data compression is pretty nil. I could tell you how run length encoding works, but that's about it. More than anything, it's a fantasy compression scheme. I was originally inspired by rainbow tables (https://en.wikipedia.org/wiki/Rainbow_table https://en.wikipedia.org/wiki/Rainbow_table) . The idea would be some sort of compression where there would be a table of uncompressed data blobs that map to some sort of hash key. The compressed file would be a sequence of the key. If you're reading this and you have a working knowledge of data compression, I imagine this is throwing off all sorts of red flags in your head. Feel free to explain why it wouldn't work.
  - gus_massa 7y ago
    Wikipedia is always is good start and it is better written than what I can type just now. Take a look specially at the "limitations" section. https://en.wikipedia.org/wiki/Lossless_compression#Limitations https://en.wikipedia.org/wiki/Lossless_compression#Limitatio...
  - ALittleLight 7y ago
    I could see Game of Life as part of a DIY steganography scheme. E.g. I tweet a picture and have some numerals in my tweet called N. You download the picture and convert it via an agreed on protocol to a game of life board, then advance the board by N times. Then you convert the board back to bits and then to text, and find somewhere in the text a "Message begins: XXX. Message ends." Sequence. I wonder if you would be able to hide messages in superficially normal pictures like that.
- 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 ago
    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.
    - 1-more 7y ago
      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.
BuildTheRobots 7y ago
I couldn't read this without thinking of πfs (Pi FS). Pi being an irrational number contains all other numbers. Therefor rather than sending someone a file (eg a video) all you need to do is search the never-ending π and send people the offset instead. 100% compression here we go. https://github.com/philipl/pifs/ https://github.com/philipl/pifs/ In reality though, searching through Pi to find that offset - especially for bigger files, can take a while.
- noiv 7y ago
  Is the offset of an arbitrary sequence in PI really shorter than the actual sequence?
  - anoother 7y ago
    No
  - rytill 7y ago
    Nailed it
  - Cpoll 7y ago
    There are an infinite number of valid offsets, so you just keep looking until you find one that's sufficiently compressible, e.g. 10^10^10+42
    - jerf 7y ago
      That does not work. Given the looooooooong history of people on the internet not believing that, I preemptively invite you to implement it. If you could make it work there's big money to be made. More constructively and with less effort, while https://cs.stackexchange.com/questions/42464/are-there-any-compression-algorithms-based-on-pi https://cs.stackexchange.com/questions/42464/are-there-any-c... on the surface doesn't seem to address your scene, if you think about it for long enough, you'll find it does.
      - 7y ago
tobias3 7y ago
This is addressed since forever in the comp.compression faq http://www.faqs.org/faqs/compression-faq/part1/ http://www.faqs.org/faqs/compression-faq/part1/ see "9.2 The counting argument" and the link there to http://www.dogma.net/markn/FAQ.html#Q19 http://www.dogma.net/markn/FAQ.html#Q19
bawolff 7y ago
Cellular automata are turing complete, so in principle you can implement any algorithm if you control the start state (albeit with massive overhead). So probably the answer is technically yes, but probably not in the way you are thinking of.
drdrey 7y ago
Sounds very similar to KolmogoroV Complexity: https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity In this case your starting automata is acting as a program you want to find the smallest one that produces your object as output. It is in general undecidable to know if you found the smallest possible program that produces a given output.

ALittleLight 7y ago

How does this compress data though even if you could easily find parent states? Don't you have to have at least one bit per cell (alive or dead) for your whole grid? You have some information which is X bits long, so you turn it into a game of life board. Then you find a parent state which is still X bits long. How does that help with compression?

waltbosz 7y ago
I should explain ... the extent of my knowledge of data compression is pretty nil. I could tell you how run length encoding works, but that's about it. More than anything, it's a fantasy compression scheme. I was originally inspired by rainbow tables (https://en.wikipedia.org/wiki/Rainbow_table https://en.wikipedia.org/wiki/Rainbow_table) . The idea would be some sort of compression where there would be a table of uncompressed data blobs that map to some sort of hash key. The compressed file would be a sequence of the key. If you're reading this and you have a working knowledge of data compression, I imagine this is throwing off all sorts of red flags in your head. Feel free to explain why it wouldn't work.
- gus_massa 7y ago
  Wikipedia is always is good start and it is better written than what I can type just now. Take a look specially at the "limitations" section. https://en.wikipedia.org/wiki/Lossless_compression#Limitations https://en.wikipedia.org/wiki/Lossless_compression#Limitatio...
- ALittleLight 7y ago
  I could see Game of Life as part of a DIY steganography scheme. E.g. I tweet a picture and have some numerals in my tweet called N. You download the picture and convert it via an agreed on protocol to a game of life board, then advance the board by N times. Then you convert the board back to bits and then to text, and find somewhere in the text a "Message begins: XXX. Message ends." Sequence. I wonder if you would be able to hide messages in superficially normal pictures like that.
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 ago
  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.
  - 1-more 7y ago
    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.

BuildTheRobots 7y ago

I couldn't read this without thinking of πfs (Pi FS). Pi being an irrational number contains all other numbers. Therefor rather than sending someone a file (eg a video) all you need to do is search the never-ending π and send people the offset instead. 100% compression here we go. https://github.com/philipl/pifs/ https://github.com/philipl/pifs/ In reality though, searching through Pi to find that offset - especially for bigger files, can take a while.

noiv 7y ago
Is the offset of an arbitrary sequence in PI really shorter than the actual sequence?
- anoother 7y ago
  No
- rytill 7y ago
  Nailed it
- Cpoll 7y ago
  There are an infinite number of valid offsets, so you just keep looking until you find one that's sufficiently compressible, e.g. 10^10^10+42
  - jerf 7y ago
    That does not work. Given the looooooooong history of people on the internet not believing that, I preemptively invite you to implement it. If you could make it work there's big money to be made. More constructively and with less effort, while https://cs.stackexchange.com/questions/42464/are-there-any-compression-algorithms-based-on-pi https://cs.stackexchange.com/questions/42464/are-there-any-c... on the surface doesn't seem to address your scene, if you think about it for long enough, you'll find it does.
    - 7y ago

tobias3 7y ago

This is addressed since forever in the comp.compression faq http://www.faqs.org/faqs/compression-faq/part1/ http://www.faqs.org/faqs/compression-faq/part1/ see "9.2 The counting argument" and the link there to http://www.dogma.net/markn/FAQ.html#Q19 http://www.dogma.net/markn/FAQ.html#Q19

bawolff 7y ago

Cellular automata are turing complete, so in principle you can implement any algorithm if you control the start state (albeit with massive overhead). So probably the answer is technically yes, but probably not in the way you are thinking of.

drdrey 7y ago

Sounds very similar to KolmogoroV Complexity: https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity In this case your starting automata is acting as a program you want to find the smallest one that produces your object as output. It is in general undecidable to know if you found the smallest possible program that produces a given output.