home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / ai / neuraln / 3216 < prev    next >
Encoding:
Internet Message Format  |  1992-08-18  |  2.1 KB
  1. Xref: sparky comp.ai.neural-nets:3216 comp.ai:3131 comp.theory:1774
  2. Newsgroups: comp.ai.neural-nets,comp.ai,comp.theory
  3. Path: sparky!uunet!wupost!gumby!destroyer!ubc-cs!fornax!jamie
  4. From: jamie@cs.sfu.ca (Jamie Andrews)
  5. Subject: Re: measuring complexity (was Re: Kolmogorov Complexity)
  6. Message-ID: <1992Aug17.171934.9364@cs.sfu.ca>
  7. Organization: CSS, Simon Fraser University, Burnaby, B.C., Canada
  8. References: <1992Aug12.150857.219@access.digex.com> <BsxH2n.Ks4@math.uwaterloo.ca> <1992Aug14.183256.20441@access.digex.com>
  9. Date: Mon, 17 Aug 1992 17:19:34 GMT
  10. Lines: 32
  11.  
  12.      As far as I can tell, there is no mathematical reason why
  13. K-complexity for learning applications should be based on any
  14. one computational formalism (Turing machines, assembler code, C,
  15. etc).  However, for the sake of consistency of notation, it
  16. might be better to base it on some programming language with a
  17. simple and standard semantics, such as pure LISP or pure Prolog.
  18.  
  19.      So, for instance, the K-complexity of a given list of
  20. numbers might be defined as:  the length of the shortest program
  21. in pure LISP such that the value of the s-expression "(result)"
  22. is that list.  (Well, I guess it would have to be pure LISP plus
  23. some arithmetic functions.)  The "length" of a program might be
  24. defined as the total number of atoms plus the total number of
  25. sets of parentheses, to give a more realistic idea of the
  26. storage space needed by the program.
  27.  
  28.      A measure of K-complexity relative to some standard suite
  29. of function definitions could be given, too.  The relative
  30. K-complexity would be the length of the shortest pure LISP
  31. program containing that suite of definitions, _minus_ the length
  32. of those definitions.  The minimal program could then make use
  33. of the "knowledge" in the standard functions without having to
  34. derive it.
  35.  
  36.      By the way, I asked about K-complexity here a few years
  37. ago, and was given convincing arguments that finding the
  38. K-complexity of a given string is in general undecidable.
  39. I don't know about randomized algorithms, though.
  40.  
  41. --Jamie.
  42.   jamie@cs.sfu.ca
  43. "Every \item command in item_list must have an optional argument." LaTeX pg.168
  44.