Search for complexity measure and where it took me...

Well, I got very interested in complex systems lately. So, I decided to write a paper for a local conference in which I tried to join information security with complexity. A part of this endeavor made me to Google for a paper that describes complexity measure. Well, I found many interesting things, but not what I was looking for, at least not yet. Still, I wanted to preserve some of those interesting pages and materials for a later reference.

The first page, and indeed it was the first page in google search, I stumbled upon Cosma Shalizi's page about Complexity Measures. Well, I have to say that he seems to have very good pages. What generated my next interest was his critique of Wolfram's book A New Kind of a Science. Actually, on the page about Complexity Measures there is a list of Disrecommended stuff, part of which is aforementioned book.

This also took me briefly to Wikipedia's page about  Jacques Derrida and then to the page about Slavoj Žižek. But the only thing that made me go to Slavoj's page on Wikipedia was the fact that his name sounds like he's from some former Yugoslavia republic, which turned out to be true; he's from Slovenia. But, let me go back to Derrida. Derrida was obviously philosopher that developed critical theory of deconstruction. To be honest, I don't understand yet what it is about, at least not enough to write something meaningful, so I'll try again later.

Still, Derrida wasn't the end of my wondering, since, while reading critique of Wolfram's book, I took a detour into tag system, then to more broad models of computation, and finally to Turing machine. Well, Wikipedia, as usual, has very good text about it and it is now also on my todo list.

Somewhere along the way I also checked the Wikipedia page about Kolmogorov, and subsequently about Per_Martin-Löf because he's mentioned as extending Kolmogorov complexity measure into very interesting direction. Also, I checked page about randomness. Supposedly, on this page truly random data can be obtained which is collected from some atmospheric measurements, but again, I'm not certain that it is the truth. Cosma Shalizi has many other interesting pages, one of which is his critique of using gzip for complexity measure. Last, but not least, I also stumbled on Cellular automata FAQ because Wolfram's book claims that universe is certain kind of CA and that the existing approach of using complex formulas to describe it is wrong.

I wrote this blog entry for two reasons. First one is to save links in order to check them again. And the second reason is that I wasn't aware of the controversy surrounding Wolfram's book.