home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / ai / neuraln / 3200 < prev    next >
Encoding:
Internet Message Format  |  1992-08-15  |  1.4 KB
  1. Xref: sparky comp.ai.neural-nets:3200 comp.ai:3104 comp.theory:1767
  2. Newsgroups: comp.ai.neural-nets,comp.ai,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: <1992Aug14.183256.20441@access.digex.com>
  7. Organization: Express Access Online Communications, Greenbelt, MD USA
  8. References: <1992Aug10.115352.1@acad3.alaska.edu> <1992Aug12.150857.219@access.digex.com> <BsxH2n.Ks4@math.uwaterloo.ca>
  9. Date: Fri, 14 Aug 1992 18:32:56 GMT
  10. Lines: 21
  11.  
  12. In article <BsxH2n.Ks4@math.uwaterloo.ca> jfbuss@math.uwaterloo.ca (Jonathan Buss) writes:
  13. >In article <1992Aug12.150857.219@access.digex.com> dzik@access.digex.com (Joseph Dzikiewicz) writes:
  14. >
  15. >>This lack of infinite memory is why digital computers are of equal 
  16. >>computing power to a finite state machine and considerably less powerful
  17. >>than a Turing machine.
  18. >>
  19. >
  20. >This observation begs the question, why are digital computers modelled
  21. >as infinite-state machines?  Can one obtain more realistic results by
  22. >using finite-state machines as the model?
  23. >
  24. I suspect it is because of the difficulties of dealing with finite-state
  25. machines with really large numbers of states.  Analysis of algorithms
  26. usually ignores the fact that any existing computer can only deal with
  27. some finitely large input. 
  28.  
  29. Joe Dzikiewicz
  30.  
  31.  
  32. >
  33.