home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / logic / 1362 < prev    next >
Encoding:
Text File  |  1992-09-08  |  1.2 KB  |  30 lines
  1. Newsgroups: sci.logic
  2. Path: sparky!uunet!mcsun!sun4nl!alchemy!ruulch!ruulo3!versmiss
  3. From: versmiss@let.ruu.nl (Koen Versmissen)
  4. Subject: Re: infinite state automaton
  5. Message-ID: <versmiss.715952911@ruulo3>
  6. Organization: Faculty of Arts, Utrecht University, The Netherlands
  7. References: <UedH4ge00WB80CdOB6@andrew.cmu.edu> <1992Sep8.081401.18506@nntp.nta.no>
  8. Date:  8 Sep 92 11:48:31 GMT
  9. Lines: 19
  10.  
  11. klaus@hal.nta.no (Klaus Gaarder FNI) writes:
  12.  
  13. >A Turing machine can be considered to have an infinite number of states if you 
  14. >define each state by including the contents of the tape in addition to each of
  15. >the finite number of states, thus giving a countable number of states.
  16.  
  17. But that doesn't imply that Turing machines are equivalent to ISAs
  18. (Infinite State Automata). After all, assuming a two-letter alphabet,
  19. just construct an infinite binary branching tree of states and mark 
  20. all and only the states corresponding to words of the language as 
  21. accepting ones. This gives you a deterministic ISA with a countable
  22. number of states for any language, in particular for non r.e. ones.
  23. So Turing machines are strictly weaker than ISAs.
  24.  
  25.  
  26. Koen Versmissen
  27. --
  28. OTS, Universiteit Utrecht, Trans 10, 3512 JK  Utrecht, NL
  29. E-mail: Koen.Versmissen@let.ruu.nl - Tel: (+31) 30-536057
  30.