home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / logic / 1364 < prev    next >
Encoding:
Internet Message Format  |  1992-09-08  |  1.1 KB

  1. Path: sparky!uunet!gatech!news.byu.edu!news.mtholyoke.edu!nic.umass.edu!dime!chelm.cs.umass.edu!yodaiken
  2. From: yodaiken@chelm.cs.umass.edu (victor yodaiken)
  3. Newsgroups: sci.logic
  4. Subject: Re: infinite state automaton
  5. Message-ID: <53082@dime.cs.umass.edu>
  6. Date: 8 Sep 92 17:30:12 GMT
  7. References: <UedH4ge00WB80CdOB6@andrew.cmu.edu> <1992Sep8.081401.18506@nntp.nta.no> <versmiss.715952911@ruulo3>
  8. Sender: news@dime.cs.umass.edu
  9. Organization: University of Massachusetts, Amherst
  10. Lines: 20
  11.  
  12. In article <versmiss.715952911@ruulo3> versmiss@let.ruu.nl (Koen Versmissen) writes:
  13. >klaus@hal.nta.no (Klaus Gaarder FNI) writes:
  14. >
  15. >>A Turing machine can be considered to have an infinite number of states if you 
  16. >>define each state by including the contents of the tape in addition to each of
  17. >>the finite number of states, thus giving a countable number of states.
  18. >
  19. >But that doesn't imply that Turing machines are equivalent to ISAs
  20. >(Infinite State Automata). After all, assuming a two-letter alphabet,
  21. >just construct an infinite binary branching tree of states and mark 
  22.      ^^^^^^^^^^^
  23.  
  24. By a non-constructive process, no doubt. 
  25.  
  26.  
  27. -- 
  28.  
  29.  
  30. yodaiken@chelm.cs.umass.edu
  31.  
  32.