Article View: sci.logic
Article #153Re: infinite state automaton
From: victor yodaiken
Date: Tue, 08 Sep 1992 17:30
Date: Tue, 08 Sep 1992 17:30
19 lines
1194 bytes
1194 bytes
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
Technical Details
Message-ID:
<53082@dime.cs.umass.edu>Path:
arc1-ca.pugleaf.net!sparky!uunet!gatech!news.byu.edu!news.mtholyoke.edu!nic.umass.edu!dime!chelm.cs.umass.edu!yodaikenReferences:
<UedH4ge00WB80CdOB6@andrew.cmu.edu> <1992Sep8.081401.18506@nntp.nta.no> <versmiss.715952911@ruulo3>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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