home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / ai / neuraln / 3168 < prev    next >
Encoding:
Internet Message Format  |  1992-08-12  |  1.3 KB
  1. Xref: sparky comp.ai.neural-nets:3168 comp.ai:3069 comp.compression:2992 comp.theory:1749
  2. Newsgroups: comp.ai.neural-nets,comp.ai,comp.compression,comp.theory
  3. Path: sparky!uunet!psinntp!digex!dzik
  4. From: dzik@access.digex.com (Joseph Dzikiewicz)
  5. Subject: Re: measuring complexity (was Re: Kolmogorov Complexity)
  6. Message-ID: <1992Aug12.150857.219@access.digex.com>
  7. Organization: Express Access Online Communications, Greenbelt, MD USA
  8. References: <arms.713457373@spedden> <1992Aug10.163725.26986@julian.uwo.ca> <1992Aug10.115352.1@acad3.alaska.edu>
  9. Date: Wed, 12 Aug 1992 15:08:57 GMT
  10. Lines: 17
  11.  
  12. In article <1992Aug10.115352.1@acad3.alaska.edu> fxsdb@acad3.alaska.edu (Scott D. Berry) writes:
  13. >an
  14. >assembly language program, for example, may have an infinite number of states.
  15.  
  16. Actually, unless you have an assembly language that allows addressing
  17. infinite memory, even an assembly language program has a finite
  18. number of states (a large number, admittedly, but still finite).
  19.  
  20. This lack of infinite memory is why digital computers are of equal 
  21. computing power to a finite state machine and considerably less powerful
  22. than a Turing machine.  Admittedly, a computer with megabytes of memory
  23. is a finite state machine with a lot of states, but it's still not
  24. Turing-equivalent.
  25.  
  26. Joe Dzikiewicz
  27.  
  28.  
  29.