home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / ai / neuraln / 3192 < prev    next >
Encoding:
Internet Message Format  |  1992-08-14  |  1.4 KB
  1. Xref: sparky comp.ai.neural-nets:3192 comp.ai:3094 comp.compression:3013 comp.theory:1763
  2. Newsgroups: comp.ai.neural-nets,comp.ai,comp.compression,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: <1992Aug14.170429.13981@fid.morgan.com>
  7. Organization: Morgan Stanley & Co., New York, NY
  8. References: <1992Aug11.124142@sees.bangor.ac.uk> <arms.713549466@spedden> <1992Aug12.173546.3298@access.usask.ca>
  9. Date: Fri, 14 Aug 1992 17:04:29 GMT
  10. Lines: 19
  11.  
  12. In article <1992Aug12.173546.3298@access.usask.ca>
  13. choy@skorpio.usask.ca (I am a terminator.) writes:
  14. >In article <arms.713549466@spedden>, arms@cs.UAlberta.CA (Bill Armstrong) writes:
  15. >|> mather@sees.bangor.ac.uk (Paul Mather) writes:
  16.  
  17. >|> The trouble is that all you need to define any function is a
  18. >|> (complete) table of input-output pairs.  If you allow this table as
  19. >|> (part of) the "instruction set", all of computability theory becomes
  20. >|> uninteresting.  So yes, normally algorithms have to be finite.
  21. >
  22. >Why would computability theory become uninteresting?
  23.  
  24. A function is (can be viewed as) the set of input-output pairs.  If
  25. you allow all such sets as part of the instruction set of a machine,
  26. then all functions are computable.  If all functions are computable,
  27. then the theory about which functions are not computable becomes
  28. rather small.
  29.  
  30. Seth        sethb@fid.morgan.com
  31.