home *** CD-ROM | disk | FTP | other *** search
- Path: sparky!uunet!gatech!news.byu.edu!news.mtholyoke.edu!nic.umass.edu!dime!chelm.cs.umass.edu!yodaiken
- From: yodaiken@chelm.cs.umass.edu (victor yodaiken)
- Newsgroups: sci.logic
- Subject: Re: infinite state automaton
- Message-ID: <53082@dime.cs.umass.edu>
- Date: 8 Sep 92 17:30:12 GMT
- References: <UedH4ge00WB80CdOB6@andrew.cmu.edu> <1992Sep8.081401.18506@nntp.nta.no> <versmiss.715952911@ruulo3>
- Sender: news@dime.cs.umass.edu
- Organization: University of Massachusetts, Amherst
- Lines: 20
-
- In article <versmiss.715952911@ruulo3> versmiss@let.ruu.nl (Koen Versmissen) writes:
- >klaus@hal.nta.no (Klaus Gaarder FNI) writes:
- >
- >>A Turing machine can be considered to have an infinite number of states if you
- >>define each state by including the contents of the tape in addition to each of
- >>the finite number of states, thus giving a countable number of states.
- >
- >But that doesn't imply that Turing machines are equivalent to ISAs
- >(Infinite State Automata). After all, assuming a two-letter alphabet,
- >just construct an infinite binary branching tree of states and mark
- ^^^^^^^^^^^
-
- By a non-constructive process, no doubt.
-
-
- --
-
-
- yodaiken@chelm.cs.umass.edu
-
-