Google suggests that the picture left – forest fire – is the product of a cellular automaton, and there are plenty of similar pictures about. Not least in the fat book about the things by Stephen Wolfram, a book which I started but never got very far into, despite the claims made for the powers of these automata.
My musings concerned the information content of such a picture. On the one hand, to get reasonable resolution from an array of pixels you might need more than a quarter of a million bytes. Maybe you can get that down a bit if you apply jpeg algorithms which filter out any obvious regularities.
But you can really get it down if you have access to the input to the cellular automaton which produced it. I have no idea how much input was need to generate this picture, but Wolfram shows pictures of similar complexity generated by just a few tens of bits of input. To which you have to add however many bits are needed to specify the automaton itself. Maybe you only start to see serious savings when you have lots of such pictures.
Another example of the same sort of thing might be the not very many instructions which are needed to generate as many digits of (the transcendental number) pi as you want. Millions of the things. Millions which would occupy lots of bytes if the best you could do was just copy them down into a data array.
From where I associate to the small black disc on a white ground used as an example by Giulio Tononi in his book called ‘Phi’. A picture also involving a few tens of bits of input to some suitable drawing package, but on the face of it containing a lot less information. But with there being lots in the drawing package and lots more in the display software.
From all of which one might deduce that quantifying the information content of a picture is a tricky business. Perhaps it is all relative, depending on your point of view. Perhaps the chaps who do Kolmogorov complexity have all the answers – with Li & Vitányi’s substantial book on the subject being yet another book I have not got as far into as I would have liked. This despite the start of the wikipedia entry looking innocuous enough: ‘In algorithmic information theory ... the Kolmogorov complexity of an object, such as a piece of text, is the length of the shortest computer program (in a predetermined programming language) that produces the object as output. It is a measure of the computational resources needed to specify the object, and is also known as descriptive complexity... The notion of Kolmogorov complexity can be used to state and prove impossibility results akin to Cantor's diagonal argument, Gödel's incompleteness theorem, and Turing's halting problem’.
PS: I notice that the forest fire flickers in an odd way when you scroll it slowly up (or down) the screen, using the chevron at the bottom right of the display rather than clicking around the brick. Presumably some artefact of the display software, rather than of the underlying image.
No comments:
Post a Comment