home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / compress / research / 292 < prev    next >
Encoding:
Internet Message Format  |  1992-11-20  |  2.2 KB
  1. Path: sparky!uunet!cis.ohio-state.edu!zaphod.mps.ohio-state.edu!cs.utexas.edu!uwm.edu!rpi!utcsri!relay.cs.toronto.edu!neuron.ai.toronto.edu!ai.toronto.edu!radford
  2. Newsgroups: comp.compression.research
  3. From: radford@cs.toronto.edu (Radford Neal)
  4. Subject: Re: C source for Fractal compression, huh !
  5. Message-ID: <92Nov20.145206edt.589@neuron.ai.toronto.edu>
  6. Organization: Department of Computer Science, University of Toronto
  7. References: <MICHAEL.92Nov13144140@pullet.lanl.gov> <1992Nov16.184754.3170@maths.tcd.ie> <Bxu712.LvA@metaflow.com> <1992Nov18.024912.24072@maths.tcd.ie>
  8. Date: 20 Nov 92 19:53:03 GMT
  9. Lines: 30
  10.  
  11. In article <1992Nov18.024912.24072@maths.tcd.ie> tim@maths.tcd.ie (Timothy Murphy) writes:
  12.  
  13. >>...information theory does not set an absolute limit on maximum compression 
  14.  
  15. > As I understand it, Chaitin/Kolmogorov Algorithmic Information Theory
  16. > does set an absolute limit to the degree to which any given data can
  17. > be compressed... subject only to the choice of a particular universal 
  18. > Turing machine. (This last proviso would not have any effect in practice.)
  19.  
  20. When people talk about an "absolute limit on maximum compression", they
  21. are referring to an ABSOLUTE theoretical limit on maximum compression.
  22.  
  23. Chaitin/Kolmogorov Algorithmic Information Theory does not give such
  24. a limit, for the very reason you note - it depends on a particular 
  25. choice of universal Turing machine. By chosing the Turing machine 
  26. appropriately, I can make any string have any complexity whatsoever.
  27. Saying that it's not an issue in practice is not germaine - we aren't
  28. talking about PRACTICAL limits, but about ABSOLUTE, THEORETICAL limits.
  29.  
  30. In any case, none of this has anything to do with the original topic,
  31. which was fractal compresion. The claims made for this technique do
  32. indeed seem rather dubious, given their coyness about releasing hard
  33. information, but they certainly can't be ruled out on theoretical
  34. grounds, even allowing for some additional "practical" constraints.
  35. There's not enough known about the psychology of human vision to tell
  36. how much information can be deleted from images without harm, and
  37. there's not enough known about the universe of images to say how
  38. redundant they are.
  39.  
  40.     Radford Neal
  41.