Hacker News Reader

Comment by waltbosz | Hacker News Reader

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.

View on HN

This is addressed since forever in the comp.compression faq 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

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?

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) . 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.

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#Limitatio...

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.

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

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.

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.

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/

In reality though, searching through Pi to find that offset - especially for bigger files, can take a while.

Is the offset of an arbitrary sequence in PI really shorter than the actual sequence?

Nailed it

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

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-c... on the surface doesn't seem to address your scene, if you think about it for long enough, you'll find it does.

It wouldn't be practical even if I were right, but I see the issue with my logic.

My reasoning amounted to "there are infinite repetitions of any sequence in Pi, therefore for any given sequence there must exist one occurrence with a compressible index."

Which, after consideration, I acknowledge is incorrect :)

Same problem. The amount of information that you need to specify a compressible offset plus the compressibility of said offset adds up to at least the amount of information you were trying to encode, and no compression happens.

If you ignore either half of the information problem, you can get what looks like compression but really isn't.

See https://www.patrickcraig.co.uk/other/compression.php for a fun story about "data hiding" to show exactly how sneaky the data hiding can be.

Indeed, I see that problem now.

Very interesting story as well, thank you.

So on average this offset is going to take as many bytes as the output data

Agreed, I overlooked this obvious fact.

Or you could just be extremely finicky about the numbers you choose to compress.

This 100%

Given first 500 digits: 3.1415926535897932384626433832795028841971 6939937510582097494459230781640628620899 8628034825342117067982148086513282306647 0938446095505822317253594081284811174502 8410270193852110555964462294895493038196 4428810975665933446128475648233786783165 2712019091456485669234603486104543266482 1339360726024914127372458700660631558817 4881520920962829254091715364367892590360 0113305305488204665213841469519415116094 3305727036575959195309218611738193261179 3105118548074462379962749567351885752724 89122793818301194912

Let's encode: 10,72,7

//index, length

48,2|139,2|13,1

Even with a fixed length we run into the same issue.

Sounds very similar to 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.

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.

Reply on news.ycombinator.com