home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / compress / research / 294 < prev    next >
Encoding:
Text File  |  1992-11-21  |  2.9 KB  |  77 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: <1992Nov21.151212.20315@maths.tcd.ie>
  6. Organization: Dept. of Maths, Trinity College, Dublin, Ireland.
  7. References: <MICHAEL.92Nov13144140@pullet.lanl.gov> <1992Nov16.184754.3170@maths.tcd.ie> <Bxu712.LvA@metaflow.com> <1992Nov18.024912.24072@maths.tcd.ie> <92Nov20.145206edt.589@neuron.ai.toronto.edu>
  8. Date: Sat, 21 Nov 1992 15:12:12 GMT
  9. Lines: 66
  10.  
  11. radford@cs.toronto.edu (Radford Neal) writes:
  12.  
  13. >In article <1992Nov18.024912.24072@maths.tcd.ie> tim@maths.tcd.ie (Timothy Murphy) writes:
  14.  
  15. >>>...information theory does not set an absolute limit on maximum compression 
  16.  
  17. >> As I understand it, Chaitin/Kolmogorov Algorithmic Information Theory
  18. >> does set an absolute limit to the degree to which any given data can
  19. >> be compressed... subject only to the choice of a particular universal 
  20. >> Turing machine. (This last proviso would not have any effect in practice.)
  21.  
  22. >When people talk about an "absolute limit on maximum compression", they
  23. >are referring to an ABSOLUTE theoretical limit on maximum compression.
  24.  
  25. >Chaitin/Kolmogorov Algorithmic Information Theory does not give such
  26. >a limit, for the very reason you note - it depends on a particular 
  27. >choice of universal Turing machine. By chosing the Turing machine 
  28. >appropriately, I can make any string have any complexity whatsoever.
  29. >Saying that it's not an issue in practice is not germaine - we aren't
  30. >talking about PRACTICAL limits, but about ABSOLUTE, THEORETICAL limits.
  31.  
  32. This is a complete red herring.
  33. All right, let us agree to take the universal machine
  34. defined in
  35.  
  36. @book{davis73
  37. author = " Davis, M.",
  38. title = "Computability and unsolvability",
  39. publisher = "Dover",
  40. year = 1973,
  41. isbn = 0486614719
  42. }
  43.  
  44. Now there is no doubt about it.
  45. (The choice is irrelevant,
  46. because if you insisted on the definition
  47. in Marvin Minsky, "Finite and Infinite Machines",
  48. you would reach exactly the same conclusion.)
  49.  
  50. >In any case, none of this has anything to do with the original topic,
  51. >which was fractal compresion.
  52.  
  53. It has everything to do with this.
  54. It shows beyond the slightest doubt
  55. that it is not possible to reach the kind of compression
  56. Barnsley speaks (or spoke) of,
  57. without loss of information (ie reversibility).
  58.  
  59. >how much information can be deleted from images without harm, and
  60. >there's not enough known about the universe of images to say how
  61. >redundant they are.
  62.  
  63. If this is meant to be in response to my posting,
  64. I said explicitly that this compression was not possible
  65. _without loss of information_.
  66. If you now accept that some information is lost,
  67. but argue that it wasn't very valuable information anyway,
  68. you are into a completely different realm,
  69. where I have no intention of following you.
  70.  
  71.  
  72. -- 
  73. Timothy Murphy  
  74. e-mail: tim@maths.tcd.ie
  75. tel: +353-1-2842366
  76. s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland
  77.