From: minsky@media.mit.edu (Marvin Minsky)
Subject: Re: Algorithmic Information
Cc: minsky
Organization: MIT Media Laboratory
Date: Sun, 20 Dec 1992 15:53:28 GMT

In article <105076@bu.edu> Lnd@cs.bu.edu writes:
>In article <COLUMBUS.92Dec15102022@strident.think.com>
>			columbus@strident.think.com (Michael Weiss) writes:
> > According to Li and Vitanyi, priority for the concept of algorithmic
> > entropy (or information) should go to Solomonoff, with independent
> > rediscovery by Kolmogorov and by Chaitin.  Somewhat ironically they use
> > the term Kolmogorov complexity throughout!  (I used the term Chaitin
> > entropy in my last post.)  Probably the best term is "algorithmic
> > entropy" or "algorithmic information content", which Zurek uses.
>
>Kolmogorov's paper (Jan. 1965) is a few months later than Solomonoff's but both
>of them made talks years earlier (and did not know of each other).  Solomonoff
>had crucial insights, but did not introduce the complexity function explicitly.
>The functions he did introduce were ill defined (limits diverged, etc.).
>Both proved the crucial theorem of invariance within +/- O(1). 

>Also, each had important ideas not found by the other. So, I think, the
>use of Kolmogorov's name is well justified (as well as Solomonoff's).
>
>	Chaitin published a partial (un-invariant, not far from Shannon's)
>result in 1966 and more important things in 1969 and 1975. It is hard to judge
>how independent he was, since he does not cite his predecessors even in those
>cases when he certainly knows about them (his 1987 complexity book, does not
>mention even names of Kolmogorov and Solomonoff; see the review in
>{\em J. of Symbolic Logic} 54(2) pp. 624-627, 1989.)

Solomonoff's work influenced me quite early, certainly from 1955 on,
and I lectured about it in my course M61 at MIT starting in 1959.
For example, here is a passage from my 1961 paper, "Steps Toward
Artificial Intelligence."

"The problem of finding an efficient grammar is much the same as that
of finding efficient encodings, or programs, for machines; in each
case, one needs to discover the important regularities in the data,
and exploit the regularities by making shrewd abbreviations.  The
possible importance of Solomonoff's work [18] is that, despite some
obvious defects, it may point the way toward' systematic mathematical
ways to explore this discovery problem.  He considers the class of all
programs (for a given general-purpose computer) which will produce a
certain given output (the body of data in question).  Most such
programs, if allowed to continue, will add to that body of data.  By
properly weighting these programs, perhaps by length, we can obtain
corresponding weights for the different possible continuations, and
thus a basis for prediction."

Solomonoff wrote several memos by 1956, on inductive inference, one of
which was presented at the notorious 1956 Dartmouth Conference -- no
proceedings was published about this.  The following were really published.

[16] R. J. Solomonoff, "The Mechanization of Linguistic Learning,"
Zator Co., Cambridge, Mass., Zator Tech. Bull. No. 125, presented at
the Second Internatl. Congress on Cybernetics Namur, Belgium-
September, 1958 

[17]R. J. Solomonoff "A new method for discovering the grammars of
phrase structure languages," Proc. Internatl. Conf. on Information
Processing, UNESCO -- House,-Paris, France, 1959

[18] R.  J. Solomonoff, "A Preliminary Report on a General Theory of
Inductive Inference," Zator Co., Cambridge, Mass., Zator Tech. Bull.
V-131; February 1960.