home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / physics / 21306 < prev    next >
Encoding:
Internet Message Format  |  1992-12-16  |  1.9 KB

  1. Xref: sparky sci.physics:21306 sci.math:17031
  2. Path: sparky!uunet!olivea!bu.edu!csd!lnd
  3. From: lnd@csd.bu.edu (Levin)
  4. Newsgroups: sci.physics,sci.math
  5. Subject: Algorithmic Information
  6. Message-ID: <105076@bu.edu>
  7. Date: 16 Dec 92 17:59:29 GMT
  8. References: <COLUMBUS.92Dec14142145@strident.think.com> <1992Dec14.223229.22348@galois.mit.edu> <COLUMBUS.92Dec15102022@strident.think.com>
  9. Sender: news@bu.edu
  10. Reply-To: Lnd@cs.bu.edu
  11. Followup-To: sci.physics
  12. Lines: 23
  13.  
  14. In article <COLUMBUS.92Dec15102022@strident.think.com>
  15.             columbus@strident.think.com (Michael Weiss) writes:
  16.  > According to Li and Vitanyi, priority for the concept of algorithmic
  17.  > entropy (or information) should go to Solomonoff, with independent
  18.  > rediscovery by Kolmogorov and by Chaitin.  Somewhat ironically they use
  19.  > the term Kolmogorov complexity throughout!  (I used the term Chaitin
  20.  > entropy in my last post.)  Probably the best term is "algorithmic
  21.  > entropy" or "algorithmic information content", which Zurek uses.
  22.  
  23. Kolmogorov's paper (Jan. 1965) is a few months later than Solomonoff's but both
  24. of them made talks years earlier (and did not know of each other).  Solomonoff
  25. had crucial insights, but did not introduce the complexity function explicitly.
  26. The functions he did introduce were ill defined (limits diverged, etc.).
  27. Both proved the crucial theorem of invariance within +/- O(1). 
  28. Also, each had important ideas not found by the other. So, I think, the
  29. use of Kolmogorov's name is well justified (as well as Solomonoff's).
  30.  
  31.     Chaitin published a partial (un-invariant, not far from Shannon's)
  32. result in 1966 and more important things in 1969 and 1975. It is hard to judge
  33. how independent he was, since he does not cite his predecessors even in those
  34. cases when he certainly knows about them (his 1987 complexity book, does not
  35. mention even names of Kolmogorov and Solomonoff; see the review in
  36. {\em J. of Symbolic Logic} 54(2) pp. 624-627, 1989.)
  37.