Re: Subjective measure and turing machine terminology

From: Wei Dai <>
Date: Sun, 25 Jan 2004 03:47:04 -0500

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 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

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:09 PST