Hacker News Reader

Comment by jpalomaki | Hacker News Reader

As a next step: how simple can you make the initial state. Can you have something that occupies much less space, but then grows to something that resembles the target image.

View on HN

Isn't this the goal of an image compression tool? Can we have efficient lossless compression with GoL? That would work with any data. Would it be better than bzip2 or png?

The problem in general with this approach is that the amount of bits it takes to identify the correct decoded value exceeds the amount of bits it takes to simply write down the correct encoded value.

People have been proposing similar algorithms for the last few decades. It's really become the "Free energy is being suppressed by the man!" of compression algorithms. One of the more popular is "just identify where your value is in pi!", which fails for that reason.

One problem is that in order to analyze such algorithms you really need to count your bits carefully. For instance in the pi case people sometimes think "well, I just need two numbers, the distance into pi and the length", but those "two numbers" may need arbitrarily unbounded numbers of bits to represent.

GoL has its own problem which is that if you construct a "random" state that didn't start "naturally" the odds of it being a Garden of Eden state are essentially 1. Can you even call it an "image compression" tool when it can't represent an image of any pure color at all, let alone in a compressed format?

Exactly, I know first hand that it's easy to believe in such admittedly creative ideas. But thinking it through was fun and cleared up my misunderstanding; in the end the information itself cannot be compressed, one can only reduce redundancies. And an arbitrarily chosen algorithm tends to do a really bad job with that on average.

Haha that's really creative though. Makes me wonder if there is anything useful "stored" in pi that could be represented with, say, 2 64-bit integers.

Further "compression" -- you only want the index of the first occurrence of a given string. Thus, you create a table of offsets for each string length, where index 0 is the first unique string of length n, index 1 is the second, etc. This allows you to elide the issue that indices can be arbitrarily large. Of course, the table is hard to compute for large n, and the resulting "compression" has indices at worst the size of the original data... so it's gonna be super efficient at compressing the bits of pi, and no worse than unity on average.

I've often thought of that, a compression thing that says "start with this small board state, run for so many generations, go sample this area of the board, and maybe apply this run-length-encoded binary patch" but computing that initial state is, uhhhhh, a lot. A huge amount. Too freaky. But maybe there's a cellular automaton that is easier to run in reverse to find such a thing? This becomes a question for the real computer scientists.

This is a fascinating idea. Using some kind of sufficiently chaotic (and deterministic) process shared among two people, one could simply reference a time and region of the state of that process that contains the data to be sent.

Imagine the "sufficiently chaotic process" is simply listing out all the possible data sequences in order, for example 0 1 10 11 100 etc.

Then, "referencing a region" of the state is basically the same as just giving the value. The nth value is just n itself.

So clearly that doesn't give you any advantage. Why would randomizing the data sequences make it any more efficient on average?

Although if you specifically choose the ordering of the sequences so that common sequences are easy to represent and uncommon sequences are hard to represent, then you basically have Huffman coding/arithmetic coding.

Because you can bias the process to be more likely to represent data relevant to your domain.

Note: I'm not in any way a compression expert, so while it may be obvious to you/others, it's a little interesting for me to think of compression in this way (sending parameters to a shared process, instead of sharing the raw data).

This is part of modern encryption. To be more specific, we have blocks and a deterministic cryptographically secure rng, we seed the rng with a public key that is broadcasted, we then encrypt blocks and then combine them together with the number produced by the rng and create the next block of encrypted data.

You may be wondering, why do we even do this? The answer is simple, "the image is encrypted, but everyone can see the penguin". In a less cryptic manner, encrypting blocks simply maps them from one space to another, but is a reversible operation and, as any function does, is deterministic and returns the exact same value every time. The consequence of this determinism, is that identical blocks will always produce the same value and thus, the content is still somewhat visible and in some cases it could leak information. By combining blocks together along with a PRNG, we hide the mapping by requiring that the recipient solves the first block before decrypting further data and we don't end up leaking information.

This is same as giving starting digit in π, right? Not usable for compression, and encryption folks would file it under security-by-obscurity.

This is I think what cryptographic hashes are meant to achieve.

The approach described here is very lossy, and very inefficient since you have to search a huge number of permutations to find reasonable results.

It would be an interesting experiment to implement lossless compression, but it likely wouldn't achieve high compression ratios or be nearly as efficient as a purpose built algorithm.

Reply on news.ycombinator.com