From: "r.e.s." <rs.1@mindspring.com>
Subject: Re: Algorithmic Complexity
Date: Sun, 12 Dec 1999 00:13:14 -0800
Newsgroups: sci.math
Keywords: algorithmic information theory 

"Peter L. Montgomery" <pmontgom@cwi.nl> wrote ...
: Rajarshi Ray <rajarshi@home.com> writes:
[...]
: >I'm no expert on algorithmic complexity. I just know it's about
: >measuring complexity of something as the shortest program that can
: >produce it.
[...]
:     _Complexity_ refers to the cost of executing the program,
: not the number of instructions in the program.

Not for G. J. Chaitin, in _Complexity_ 1:1 (1995), pp. 26-30:
http://www.cs.auckland.ac.nz/CDMTCS/chaitin/unm2.html

"... define the program-size complexity of something to be
the size in bits of the smallest program that calculates it.
I have developed a general theory dealing with program-size
complexity that I call algorithmic information theory (AIT)."

--
r.e.s.
rs.1@mindspring.com