home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / ai / neuraln / 3174 < prev    next >
Encoding:
Internet Message Format  |  1992-08-13  |  1.4 KB
  1. Xref: sparky comp.ai.neural-nets:3174 comp.ai:3077 comp.theory:1752
  2. Newsgroups: comp.ai.neural-nets,comp.ai,comp.theory
  3. Path: sparky!uunet!elroy.jpl.nasa.gov!usc!cs.utexas.edu!torn!watserv2.uwaterloo.ca!watmath!jfbuss
  4. From: jfbuss@math.uwaterloo.ca (Jonathan Buss)
  5. Subject: Re: measuring complexity (was Re: Kolmogorov Complexity)
  6. Message-ID: <BsxH2n.Ks4@math.uwaterloo.ca>
  7. Organization: University of Waterloo
  8. References: <1992Aug10.163725.26986@julian.uwo.ca> <1992Aug10.115352.1@acad3.alaska.edu> <1992Aug12.150857.219@access.digex.com>
  9. Date: Thu, 13 Aug 1992 15:15:58 GMT
  10. Lines: 25
  11.  
  12. In article <1992Aug12.150857.219@access.digex.com> dzik@access.digex.com (Joseph Dzikiewicz) writes:
  13.  
  14. >This lack of infinite memory is why digital computers are of equal 
  15. >computing power to a finite state machine and considerably less powerful
  16. >than a Turing machine.  Admittedly, a computer with megabytes of memory
  17. >is a finite state machine with a lot of states, but it's still not
  18. >Turing-equivalent.
  19. >
  20.  
  21. This observation begs the question, why are digital computers modelled
  22. as infinite-state machines?  Can one obtain more realistic results by
  23. using finite-state machines as the model?
  24.  
  25. To particularize, do results like the following have finite-state
  26. analogues?
  27.  
  28.    (1) Mergesort has time complexity O(n log n).
  29.  
  30.    (2) The Satisfiability problem is NP-complete.
  31.  
  32. These seem to be useful results, but their statement implicitly uses
  33. an infinite-state model.
  34.  
  35.  
  36. Jonathan Buss
  37.