home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / compress / 2988 next >
Encoding:
Internet Message Format  |  1992-08-12  |  1.6 KB
  1. Xref: sparky comp.compression:2988 comp.theory:1744
  2. Newsgroups: comp.compression,comp.theory
  3. Path: sparky!uunet!mcsun!ieunet!tcdcs!maths.tcd.ie!tim
  4. From: tim@maths.tcd.ie (Timothy Murphy)
  5. Subject: Re: Kolmogorov Complexity
  6. Message-ID: <1992Aug12.115317.13558@maths.tcd.ie>
  7. Organization: Dept. of Maths, Trinity College, Dublin, Ireland.
  8. References: <1992Aug11.164651.1328@kronos.arc.nasa.gov>
  9. Date: Wed, 12 Aug 1992 11:53:17 GMT
  10. Lines: 30
  11.  
  12. wray@kronos.arc.nasa.gov (Wray Buntine) writes:
  13.  
  14. >Kolmogorov Complexity is one of a family of methods for handling the
  15. >induction problem.  As pointed out, a Turing machine can be used as the
  16. >reference system because all others will only differ by a
  17. >constant.   The main point to realise is that Kolmogorov Complexity stuff
  18. >is asymptotic,  i.e.  it holds as your sample sizes for learning
  19. >approach infinity.   My learning problems unfortunately have
  20. >finite sample sizes, so I need to choose a reference for which I think
  21. >the constant in question will be small.   
  22.  
  23. Does this make sense?
  24. You imply that there is some optimal choice of universal machine.
  25. But the constant is for one machine relative to another.
  26. In other words, one machine may do well with one set of strings,
  27. and another machine with a different set.
  28.  
  29. At the same time, it is conceivable that there is some absolute criterion.
  30. I wonder if anything is known about this?
  31.  
  32. Incidentally, it is not quite the same to say
  33. that something is defined asymptotically,
  34. and that it is defined up to a constant.
  35. The latter is stronger.
  36.  
  37. -- 
  38. Timothy Murphy  
  39. e-mail: tim@maths.tcd.ie
  40. tel: +353-1-2842366
  41. s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland
  42.