home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / virus / 4998 < prev    next >
Encoding:
Internet Message Format  |  1993-01-28  |  1.5 KB
  1. Path: sparky!uunet!ukma!cs.widener.edu!dsinc!netnews.upenn.edu!netnews.cc.lehigh.edu!news
  2. From: chess@watson.ibm.com (David M. Chess)
  3. Newsgroups: comp.virus
  4. Subject: Re: How to measure polymorphism
  5. Message-ID: <0002.9301281842.AA17847@barnabas.cert.org>
  6. Date: 18 Jan 93 21:03:05 GMT
  7. Sender: virus-l@lehigh.edu
  8. Lines: 24
  9. Approved: news@netnews.cc.lehigh.edu
  10.  
  11. >From:    Declan Malone <maloned@ul.ie>
  12.  
  13. >                            Now how do you measure randomness in an
  14. >objective way?  You can't really, and the irony of it is that the more
  15. >you try, and the more objective/detailed your description becomes...
  16.  
  17. Grep Chaitin has done some excellent work on this (he had a general-
  18. audience paper in a reasonably recent Scientific American, I think),
  19. and has perfectly objective measures of randomness that also seem to
  20. jibe very nicely with intuition.  The basic idea is that you can
  21. measure the randomness of a string of bits by finding the smallest
  22. program for some standard Turing Machine that produces those bits.
  23. For a very random bitstring, of course, the smallest program simply
  24. contains the string itself as data, and prints it out.  For very
  25. non-random strings (0000000...), the corresponding program is
  26. obviously simpler.  (This is a very rough description; if it seems
  27. wrong to you, it probably is, and you're best off finding the original
  28. papers rather than arguing with me about it!)
  29.  
  30. This agrees rather nicely with Bill Arnold's suggestion that we
  31. measure polymorphism by how many lines of code we have to add to make
  32. a detector...  *8)
  33.  
  34. DC
  35.