home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / physics / 21206 < prev    next >
Encoding:
Internet Message Format  |  1992-12-15  |  2.2 KB
  1. Xref: sparky sci.physics:21206 sci.math:16953
  2. Path: sparky!uunet!think.com!news!columbus
  3. From: columbus@strident.think.com (Michael Weiss)
  4. Newsgroups: sci.physics,sci.math
  5. Subject: Re: Chaitin's Omega and QM (was: Bayes' theorem and QM)
  6. Date: 15 Dec 92 10:20:22
  7. Organization: Thinking Machines Corporation, Cambridge MA, USA
  8. Lines: 34
  9. Message-ID: <COLUMBUS.92Dec15102022@strident.think.com>
  10. References: <1gh518INN9eo@chnews.intel.com>
  11.     <SRCTRAN.92Dec14122532@world.std.com>
  12.     <COLUMBUS.92Dec14142145@strident.think.com>
  13.     <1992Dec14.223229.22348@galois.mit.edu>
  14. NNTP-Posting-Host: strident.think.com
  15. In-reply-to: jbaez@riesz.mit.edu's message of Mon, 14 Dec 92 22:32:29 GMT
  16.  
  17. In article <1992Dec14.223229.22348@galois.mit.edu> jbaez@riesz.mit.edu
  18. (John C. Baez) writes: 
  19.  
  20.    I quote DeMers:
  21.  
  22.    For Kolmogorov Complexity in general, the best place to
  23.    start would be with
  24.    an introduction to the notions of Kolmogorov Complexity and
  25.    its application to a number of different problems which can
  26.    be found in:
  27.  
  28.    Li, M.  and Paul Vitanyi, Kolmogorov Complexity and Its
  29.    Applications, in
  30.    Handbook of Theoretical Computer Science, (J. van Leeuwen, Ed.)
  31.    North-Holland, 1989.
  32.  
  33. I might add that Li and Vitanyi do a meticulous job recounting the history
  34. of the subject (about as tangled as usual).  If you want to know who proved
  35. what when, this is the place to look.  Besides Solomonoff, Kolmorgorov,
  36. Chaitin, and Martin-Loef, already mentioned in this thread, Leonid Levin,
  37. Peter Gacs, and Robert Solovay also made important contributions.
  38.  
  39. According to Li and Vitanyi, priority for the concept of algorithmic
  40. entropy (or information) should go to Solomonoff, with independent
  41. rediscovery by Kolmorgorov and by Chaitin.  Somewhat ironically they use
  42. the term Kolmogorov complexity throughout!  (I used the term
  43. Chaitin entropy in my last post.)  Probably the best term is "algorithmic
  44. entropy" or "algorithmic information content", which Zurek uses.
  45.  
  46. Oh well.  The cubic formula was discovered by Scipio del Ferro,
  47. independently rediscovered by Tartaglia, and first published by Cardano who
  48. gave credit to Tartaglia (I don't remember if he also credited del Ferro).
  49. So of course it is almost universally referred to as Cardano's formula.
  50. (Look up the history of L'Hospital's rule sometime...)
  51.