home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / compress / research / 289 < prev    next >
Encoding:
Text File  |  1992-11-19  |  1.4 KB  |  40 lines
  1. Newsgroups: comp.compression.research
  2. Path: sparky!uunet!mcsun!ieunet!tcdcs!maths.tcd.ie!tim
  3. From: tim@maths.tcd.ie (Timothy Murphy)
  4. Subject: Re: C source for Fractal compression, huh !
  5. Message-ID: <1992Nov20.033432.18247@maths.tcd.ie>
  6. Organization: Dept. of Maths, Trinity College, Dublin, Ireland.
  7. References: <1992Nov16.184754.3170@maths.tcd.ie> <Bxu712.LvA@metaflow.com> <1992Nov18.024912.24072@maths.tcd.ie> <1992Nov18.083335.18739@adobe.com>
  8. Date: Fri, 20 Nov 1992 03:34:32 GMT
  9. Lines: 29
  10.  
  11. wtyler@adobe.com (William Tyler) writes:
  12.  
  13. >In article <1992Nov18.024912.24072@maths.tcd.ie> tim@maths.tcd.ie (Timothy Murphy) writes:
  14.  
  15. >>Chaitin/Kolmogorov Algorithmic Information Theory
  16. >>does set an absolute limit to the degree to which
  17. >>any given data can be compressed:
  18. >>the string s cannot be compressed 
  19. >>beyond its entropy (or informational content) H(s).
  20. >>H(s) is precisely defined,
  21.  
  22. >Ah, there's the rub. H(s) is only precisely defined with respect to
  23. >some particular model of the information source s, expressed in the
  24. >form of probabilities. 
  25.  
  26. I'm afraid this is completely wrong.
  27. Algorithmic Information Theory
  28. has nothing to do with probability.
  29.  
  30. The informational content H(s) of a string
  31. is the length of the shortest program
  32. which will output the string
  33. when fed into the universal Turing machine U.
  34.  
  35. -- 
  36. Timothy Murphy  
  37. e-mail: tim@maths.tcd.ie
  38. tel: +353-1-2842366
  39. s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland
  40.