home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / ai / neuraln / 3186 < prev    next >
Encoding:
Internet Message Format  |  1992-08-13  |  1.7 KB
  1. Xref: sparky comp.ai.neural-nets:3186 comp.ai:3087 comp.compression:3008 comp.theory:1759
  2. Path: sparky!uunet!mcsun!uknet!axion!micromuse!exnet!dhd
  3. From: dhd@exnet.co.uk (Damon)
  4. Newsgroups: comp.ai.neural-nets,comp.ai,comp.compression,comp.theory
  5. Subject: Re: measuring complexity (was Re: Kolmogorov Complexity)
  6. Message-ID: <BsxrAq.5y7@exnet.co.uk>
  7. Date: 13 Aug 92 18:56:49 GMT
  8. References: <1992Aug10.163725.26986@julian.uwo.ca> <1992Aug10.115352.1@acad3.alaska.edu> <1992Aug12.150857.219@access.digex.com>
  9. Organization: ExNet Systems Ltd Public Access News, London, UK
  10. Lines: 24
  11.  
  12. In article <1992Aug12.150857.219@access.digex.com> dzik@access.digex.com (Joseph Dzikiewicz) writes:
  13. >In article <1992Aug10.115352.1@acad3.alaska.edu> fxsdb@acad3.alaska.edu (Scott D. Berry) writes:
  14. >>an
  15. >>assembly language program, for example, may have an infinite number of states.
  16. >
  17. >Actually, unless you have an assembly language that allows addressing
  18. >infinite memory, even an assembly language program has a finite
  19. >number of states (a large number, admittedly, but still finite).
  20. >
  21. >This lack of infinite memory is why digital computers are of equal 
  22. >computing power to a finite state machine and considerably less powerful
  23. >than a Turing machine.  Admittedly, a computer with megabytes of memory
  24.         ^^^^^^^^^^^^^^
  25.         with an infinite tape (else the computer and the finite TM are equiv).
  26.  
  27. >is a finite state machine with a lot of states, but it's still not
  28. >Turing-equivalent.
  29.  
  30. Damon
  31. -- 
  32. Damon Hart-Davis | Tel/Fax: +44 81 755 0077 |1.22|| ALL MAIL FREE.
  33. Internet: dhd@exnet.co.uk | Also: Damon@ed.ac.uk || US hotrod motor groups.
  34. --------------------------+----------------------++ >12 mail&news polls / day.
  35. Public access UNIX (Suns), news and mail for #5 per month.  FIRST MONTH FREE.
  36.