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.

Reply via email to