home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / ai / neuraln / 3321 < prev    next >
Encoding:
Internet Message Format  |  1992-08-26  |  2.3 KB
  1. Xref: sparky comp.ai.neural-nets:3321 comp.ai:3232 comp.theory:1831
  2. Newsgroups: comp.ai.neural-nets,comp.ai,comp.theory
  3. Path: sparky!uunet!s5!sethb
  4. From: sethb@fid.morgan.com (Seth Breidbart)
  5. Subject: Re: measuring complexity (was Re: Kolmogorov Complexity)
  6. Message-ID: <1992Aug27.010147.16422@fid.morgan.com>
  7. Organization: my opinions only
  8. References: <BsxH2n.Ks4@math.uwaterloo.ca> <1992Aug14.183256.20441@access.digex.com> <1992Aug17.171934.9364@cs.sfu.ca>
  9. Date: Thu, 27 Aug 1992 01:01:47 GMT
  10. Lines: 43
  11.  
  12. In article <1992Aug17.171934.9364@cs.sfu.ca> jamie@cs.sfu.ca
  13. (Jamie Andrews) writes:
  14.  
  15. >     So, for instance, the K-complexity of a given list of
  16. >numbers might be defined as:  the length of the shortest program
  17. >in pure LISP such that the value of the s-expression "(result)"
  18. >is that list.  (Well, I guess it would have to be pure LISP plus
  19. >some arithmetic functions.)  The "length" of a program might be
  20. >defined as the total number of atoms plus the total number of
  21. >sets of parentheses, to give a more realistic idea of the
  22. >storage space needed by the program.
  23.  
  24. If any number will fit in one atom, then all strings have complexity
  25. bounded above by some small number.
  26.  
  27. >     A measure of K-complexity relative to some standard suite
  28. >of function definitions could be given, too.  The relative
  29. >K-complexity would be the length of the shortest pure LISP
  30. >program containing that suite of definitions, _minus_ the length
  31. >of those definitions.  The minimal program could then make use
  32. >of the "knowledge" in the standard functions without having to
  33. >derive it.
  34.  
  35. Since the answer is almost always undecidable, I doubt you could get
  36. any interesting results.
  37.  
  38. >     By the way, I asked about K-complexity here a few years
  39. >ago, and was given convincing arguments that finding the
  40. >K-complexity of a given string is in general undecidable.
  41.  
  42. Since no string can be shown to have complexity greater than C (for
  43. some constant C), and all except a finite number of strings have
  44. complexity greather than C, ...
  45.  
  46. >I don't know about randomized algorithms, though.
  47.  
  48. If a randomized algorithm is any that _can_ output the string, a
  49. trivial one exists: (output random bit; maybe loop).  If it _must_
  50. output the string, or can only output the string (or die), or outputs
  51. the string with some minimal probability, then you haven't gained
  52. anything from randomness.
  53.  
  54. Seth        sethb@fid.morgan.com
  55.