home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / ai / neuraln / 3160 < prev    next >
Encoding:
Internet Message Format  |  1992-08-12  |  2.1 KB
  1. Xref: sparky comp.ai.neural-nets:3160 comp.ai:3061 comp.compression:2990 comp.theory:1745
  2. Newsgroups: comp.ai.neural-nets,comp.ai,comp.compression,comp.theory
  3. Path: sparky!uunet!paladin.american.edu!darwin.sura.net!jvnc.net!yale.edu!yale!gumby!destroyer!ubc-cs!unixg.ubc.ca!kakwa.ucs.ualberta.ca!access.usask.ca!skorpio!choy
  4. From: choy@skorpio.usask.ca (I am a terminator.)
  5. Subject: Re: measuring complexity (was Re: Kolmogorov Complexity)
  6. Message-ID: <1992Aug12.173546.3298@access.usask.ca>
  7. Sender: choy@skorpio (I am a terminator.)
  8. Nntp-Posting-Host: skorpio.usask.ca
  9. Organization: University of Saskatchewan, Saskatoon, Canada
  10. References: <1992Aug10.104156.25017@julian.uwo.ca> <arms.713457373@spedden> <1992Aug10.163725.26986@julian.uwo.ca> <1992Aug10.115352.1@acad3.alaska.edu> <1992Aug11.124142@sees.bangor.ac.uk> <arms.713549466@spedden>
  11. Date: Wed, 12 Aug 1992 17:35:46 GMT
  12. Lines: 28
  13.  
  14. In article <arms.713549466@spedden>, arms@cs.UAlberta.CA (Bill Armstrong) writes:
  15. |> mather@sees.bangor.ac.uk (Paul Mather) writes:
  16. |> 
  17. |>  ... lots of stuff I agree with ...
  18. |> 
  19. |> >(*) PS (for the comp.theory people): Does an algorithm have to be finite?
  20. |> >Consider an infinite set of random instructions spat out by some other algorithm
  21. |> >running continuously on a Turing machine, say.  Would the infinite stream of
  22. |> >executable instructions be classed as an algorithm?
  23. |> 
  24. |> The trouble is that all you need to define any function is a
  25. |> (complete) table of input-output pairs.  If you allow this table as
  26. |> (part of) the "instruction set", all of computability theory becomes
  27. |> uninteresting.  So yes, normally algorithms have to be finite.
  28.  
  29. Why would computability theory become uninteresting?
  30.  
  31. |> That having been said, my gut feel is that mathematicians must have
  32. |> looked at various transfinite numbers of "instructions" to get
  33. |> functions on even larger spaces.
  34. |> --
  35. |> ***************************************************
  36. |> Prof. William W. Armstrong, Computing Science Dept.
  37. |> University of Alberta; Edmonton, Alberta, Canada T6G 2H1
  38. |> arms@cs.ualberta.ca Tel(403)492 2374 FAX 492 1071
  39.  
  40. Henry Choy
  41. choy@cs.usask.ca
  42.