On Sat, Jan 24, 2004 at 07:31:50PM -0800, Eric Hawthorne wrote: > I took some small smattering of that stuff in comp sci undergrad, but
Algorithmic information theory is generally not taught in undergrad courses. At least I didn't see it during my CS undergrad years. (Which is too bad because it's really interesting and I would have had a lot of fun learning it in school. Instead I had to learn about compilers and graphics. A lot of good those courses did me...) > essentially > what it lets met understand is that some algorithms are O(1), O(n), > O(nlogn),O(n^2) O(e^n) etc. The complexity that you're talking about is resource complexity, whereas I'm talking about information complexity. > I'm also generally familiar with Turing Machine concepts, but I'm > rusty on the details. > I'm a bit confused as to what is meant by a string having a lower > algorithmic complexity. Again, I really suggest that you read the book. It's very good and will explain all this for you. If you don't have ready access to the book, there are some online introductions to algorithmic information theory that you could try (see http://www.idsia.ch/~marcus/kolmo.htm#tutorials) but the book will review all of the prerequisites (such as Turing machines) for you and give a much more complete overview of the field.
