home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / ai / neuraln / 3363 < prev    next >
Encoding:
Internet Message Format  |  1992-08-31  |  2.0 KB
  1. Xref: sparky comp.ai.neural-nets:3363 comp.ai:3286 comp.theory:1849
  2. Newsgroups: comp.ai.neural-nets,comp.ai,comp.theory
  3. Path: sparky!uunet!usc!sol.ctr.columbia.edu!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: <1992Aug31.211753.13335@cs.sfu.ca>
  7. Organization: CSS, Simon Fraser University, Burnaby, B.C., Canada
  8. References: <1992Aug27.010147.16422@fid.morgan.com> <1992Aug27.181810.7249@cs.sfu.ca> <1992Aug28.164941.2028@fid.morgan.com>
  9. Date: Mon, 31 Aug 1992 21:17:53 GMT
  10. Lines: 31
  11.  
  12. In article <1992Aug28.164941.2028@fid.morgan.com> sethb@fid.morgan.com (Seth Breidbart) writes:
  13. >What do you mean by probability?  If you mean, for any string S, with
  14. >probability > (1-delta) P is within epsilon of the shortest program
  15. >for S, then A will lead to a probabilistic solution to the busy beaver
  16. >problem.
  17.  
  18.      What do you mean by a "probabilistic solution"?  It won't
  19. solve the busy beaver problem, it will just give an approximate
  20. solution.  If we set epsilon and delta to 0, presumably the
  21. algorithm will no longer terminate.
  22.  
  23. >If you say "for all k, assigning equal probabilities to all strings of
  24. >length bounded by k and 0 to all others", then you avoid the last
  25. >problem I raise, but once again the trivial program works almost
  26. >everywhere (and a finite correction to it works everywhere).
  27.  
  28.      That's why I suggested something which you seem to have
  29. skipped over completely, namely that we assign equal
  30. probabilities to all strings generated by programs of length k
  31. or less.
  32.  
  33.      I'm just throwing out ideas, really, trying to come up with
  34. a formulation of a problem that is interesting and non-trivial.
  35. You're welcome to your view that the problems I've stated so far
  36. are trivial, but that doesn't convince me that the whole area is
  37. trivial (though it may convince me to stop talking about it on
  38. the net :-)).
  39.  
  40. --Jamie.
  41.   jamie@cs.sfu.ca
  42. "Every \item command in item_list must have an optional argument." LaTeX pg.168
  43.