home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / logic / 1378 < prev    next >
Encoding:
Internet Message Format  |  1992-09-10  |  1.0 KB
  1. Path: sparky!uunet!gossip.pyramid.com!decwrl!decwrl!atha!aupair.cs.athabascau.ca!burt
  2. From: burt@aupair.cs.athabascau.ca (Burt Voorhees)
  3. Newsgroups: sci.logic
  4. Subject: Re: infinite state automaton
  5. Message-ID: <burt.716156347@aupair.cs.athabascau.ca>
  6. Date: 10 Sep 92 20:19:07 GMT
  7. References: <UedH4ge00WB80CdOB6@andrew.cmu.edu>
  8. Sender: news@cs.athabascau.ca
  9. Lines: 16
  10.  
  11. lb0q+@andrew.cmu.edu (Leslie Burkholder) writes:
  12.  
  13. >>Suppose we allow an automaton to have an infinite rather than a finite
  14. >>number of states. Is that (equivalent to) a Turing machine? References,
  15. >>please.
  16. >>Thanks,
  17. >>Leslie Burkholder
  18.  
  19.   This occurs in cellular automata if you have an infinite state space;
  20. e.g., if you state space is the set of all right half infinite 0,1
  21. sequences (this is my favorite), and it is known that some cellular
  22. automata are equivalent to Turing machines.
  23.   Lots of references abound, but you might check Physica D 45 (1990)
  24. where the entire issue is devoted to CA's.  It gives lots of good
  25. references to past literature as well.
  26. burt
  27.