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.
Received on Sun Jan 25 2004 - 03:48:45 PST