Re: infinite state automaton

Article View: sci.logic

Article #151

#151

From: Koen Versmissen
Date: Tue, 08 Sep 1992 11:48

19 lines
1303 bytes

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 
all and only the states corresponding to words of the language as 
accepting ones. This gives you a deterministic ISA with a countable
number of states for any language, in particular for non r.e. ones.
So Turing machines are strictly weaker than ISAs.

Koen Versmissen
--
OTS, Universiteit Utrecht, Trans 10, 3512 JK  Utrecht, NL
E-mail: Koen.Versmissen@let.ruu.nl - Tel: (+31) 30-536057

Technical Details

Message-ID: <versmiss.715952911@ruulo3>

Path: arc1-ca.pugleaf.net!sparky!uunet!mcsun!sun4nl!alchemy!ruulch!ruulo3!versmiss

References: <UedH4ge00WB80CdOB6@andrew.cmu.edu> <1992Sep8.081401.18506@nntp.nta.no>

Show Full Headers

Complete Article Headers

Newsgroups: sci.logic
Path: arc1-ca.pugleaf.net!sparky!uunet!mcsun!sun4nl!alchemy!ruulch!ruulo3!versmiss
From: versmiss@let.ruu.nl (Koen Versmissen)
Subject: Re: infinite state automaton
Message-ID: <versmiss.715952911@ruulo3>
Organization: Faculty of Arts, Utrecht University, The Netherlands
References: <UedH4ge00WB80CdOB6@andrew.cmu.edu> <1992Sep8.081401.18506@nntp.nta.no>
Date:  8 Sep 92 11:48:31 GMT
Lines: 19

Reply to Parent Message