home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / ai / neuraln / 3369 < prev    next >
Encoding:
Internet Message Format  |  1992-09-01  |  1.8 KB
  1. Xref: sparky comp.ai.neural-nets:3369 comp.ai:3295 comp.theory:1854
  2. Newsgroups: comp.ai.neural-nets,comp.ai,comp.theory
  3. Path: sparky!uunet!secapl!Cookie!frank
  4. From: frank@Cookie.secapl.com (Frank Adams)
  5. Subject: Re: measuring complexity (was Re: Kolmogorov Complexity)
  6. Message-ID: <1992Sep01.221808.40967@Cookie.secapl.com>
  7. Date: Tue, 01 Sep 1992 22:18:08 GMT
  8. References: <1992Aug27.181810.7249@cs.sfu.ca> <1992Aug28.164941.2028@fid.morgan.com> <1992Aug31.211753.13335@cs.sfu.ca>
  9. Organization: Security APL, Inc.
  10. Lines: 23
  11.  
  12. In article <1992Aug31.211753.13335@cs.sfu.ca> jamie@cs.sfu.ca (Jamie Andrews) writes:
  13. >In article <1992Aug28.164941.2028@fid.morgan.com> sethb@fid.morgan.com (Seth Breidbart) writes:
  14. >>What do you mean by probability?  If you mean, for any string S, with
  15. >>probability > (1-delta) P is within epsilon of the shortest program
  16. >>for S, then A will lead to a probabilistic solution to the busy beaver
  17. >>problem.
  18. >
  19. For any given problem X, there is a number K and a probability psi>0, such
  20. that for any length N > K, the probability that a string S of length N is a
  21. program easily recognizable as having a halting problem equivalent to X, is
  22. greater than psi.  So if X is an unsolvable problem, you will never be able
  23. to get delta less than psi.
  24.  
  25. >     I'm just throwing out ideas, really, trying to come up with
  26. >a formulation of a problem that is interesting and non-trivial.
  27. >You're welcome to your view that the problems I've stated so far
  28. >are trivial, but that doesn't convince me that the whole area is
  29. >trivial (though it may convince me to stop talking about it on
  30. >the net :-)).
  31.  
  32. In general, this kind of problem does not admit of *any* sort of general
  33. solution.  You may learn something by trying things and figuring out why
  34. they don't work, but don't expect to find anything.
  35.