[LeBleu]

I wonder if this would be explorable for some much tinier subset of the space of images. Like maybe 32 x 32 greyscale JPEG images with some limit on compressed size that keeps it to interesting images.

I'm specifically suggesting JPEG because it is a compression method based on human perception, so if we focus only on easily JPEG compressed images, we should eliminate a lot of the image that look like snow on a TV, and restrict more to images that look vaguely like something.

Unfortunately, I don't remember enough details of how JPEG compression works to make a reasonable guess how many possible JPEGs this is, and whether we are getting into numbers small enough to be feasible.

[LeBleu]

A very quick approximation seems to indicate it still isn't feasible. I saved 2 32x32 JPEGs using Gimp at quality 30. One is a cutout of a face from a photo, the other is random noise generated using the filter in Gimp. The resulting JPEG files were 427 bytes for the face, and 525 for completely random.

Now, I have no idea how much of that is the header. So, to help guess that, I saved a solid white 32px image with the same settings, and it was 164 bytes.

Worst case, generating every possible 427 byte file at one hundred per second, would take ~ 4.8×10^1008 × universe age (per http://www.wolframalpha.com/input/?i=2^%28427*8%29+%2F+100+p...)

Even if we figure all 164 bytes of the white file is header info, that leaves 263 bytes of image data in the face image, which would take ~ 5.4×10^613 × universe age. (Per http://www.wolframalpha.com/input/?i=2^%28263*8%29+%2F+100+p...)

If we got down to an 8 by 8 pixel black and white image, and generating 1 billion per second, it would still take 6 centuries. (per http://www.wolframalpha.com/input/?i=2^%288*8%29+%2F+1000000...)

So even a massively reduced version of the problem is still ridiculously impossible to explore.